庫存算法運行時的大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符號

回答

相關問題