algorithm - 库存算法运行时的大O表示法

为了安全起见，我可能不能发布任何文件的代码，但我可以描述发生了什么。基本上，我们有独立的项目和其他组成较小的部分我们现有的系统是这样工作的。假设每个套件有n个项目和m个零件，其中m不是常数，在所有情况下都小于n。

for(all items){
    if(standalone){
        process item, record available quantity and associated costs
        write to database
    }
    if(kit){
        process item, get number of pre-assembled kits
        for(each part){
            determine how many are used to produce one kit
            divide total number of this specific part by number required, keep track of smallest result
            add cost of this item to total production cost of item
        }
        use smallest resulting number to determine total available quantity for this kit
        write record to database
    }
}

起初，我想说的是，这项工作所需的总时间是o（n^2），但我不认为这是正确的，因为所有物品中约有n/3是工具包，m的范围通常在3到8个部分之间。这会是什么结果？我已经测试过几次了，感觉好像没有优化。

最佳答案

从你发布的伪代码来看，计算成本是相当容易的在n个项上有一个循环（因此这是o（n）），在这个循环中有另一个o（m）循环。当您计算出嵌套循环时，意味着这些顺序是相乘的：如果它们都是n级的，那么这将给出o（n^2）；而不是o（mn）。
这假设您提到的处理在恒定时间内运行（即，与输入的大小无关）如果这些描述隐藏了一些其他处理时间，则此分析将不正确。

关于algorithm - 库存算法运行时的大O表示法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34278543/