库存算法运行时的大O符号

为了安全起见，我可能无法发布我们的任何文件代码，但我可以描述发生了什么。基本上，我们有独立的项目和其他由较小部分组成的项目。我们现有的系统就是这样工作的。假设我们对每个工具包有n个项目和m个部分，其中m不是常数，在所有情况下都小于n。库存算法运行时的大O符号

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包，一般中号范围在3到8个部分之间。这会发生什么？我测试了几次，感觉它没有优化。

来源

2015-12-14 user3521737

如果套件中的部件的最大值可以忽略不计（如10），则认为该值不变。大O符号是关于当你有几百万个零件时会发生什么 - 当零件数以百万计时，那么10是微不足道的。如果套件中的最大零件数为10，那么它将是O（n） –

从您发布的伪代码可以很容易地计算出成本。你有一个循环n项（因此这是O（n）），并且在这个循环内有另一个O（m）循环。当你制定出嵌套循环时，意味着订单是相乘的：如果它们都是订单n，那么这会给出O（n^2）;相反，它是O（mn）。

这假设您提到的处理在恒定时间内运行（即独立于输入的大小）。如果这些描述隐藏了其他一些处理时间，那么这种分析将会不正确。

来源

2015-12-15 00:40:00 dave

我认为它需要这么长时间的原因是因为数据库访问。它从表中读取每个项目的信息，并从结果数组中读取循环。在编写这个脚本之前，我创建了一个新表，并且在每次运行它的开始时删除所有记录。之后插入更新的记录。这可能只是需要一段时间的数据库过程。 – user3521737

将每个项目存储在数据库中可能会很慢，但将项目数量加倍会使速度降低一倍（而不是O（n^2）的4倍）。 – dave

库存算法运行时的大O符号

回答

相关问题