算法分析（big-O）算法

我試圖幫助朋友分析他的算法的複雜性，但我對Big-O符號的理解是相當有限的。算法分析（big-O）算法

的代碼是這樣的：

int SAMPLES = 2000; 
int K_SAMPLES = 5000; 

int i = 0; // initial index position  
while (i < SAMPLES) 
{ 
    enumerate();      // Complexity: O(SAMPLES) 
    int neighbors = find_neighbors(i); // Complexity: O(1) 

    // Worst case scenario, neighbors is the same number of SAMPLES 
    int f = 0; 
    while (f < neighbors) // This loop is probably O(SAMPLES) as well. 
    { 
     int k = 0; // counter variable 
     while (k < K_SAMPLES) // Not sure how to express the complexity of this loop. 
     {      // Worst case scenario K_SAMPLES might be bigger than SAMPLES. 

      // do something! 

      k++; 
     } 
     f++; 
    } 

    i++; 
}

有裏面的代碼2層的功能，但我能，因爲它們易於識別的複雜性。但是，我無法表達內部循環的複雜性，但即使在測量之後，我仍然需要幫助將所有這些複雜性組合成代表該算法的計算複雜度的公式。

我在這件事上非常需要幫助。謝謝！

來源

2013-03-05 karlphillip

'while（i nhahtdh 2013-03-05 20:50:24

這裏有什麼變數？ N是唯一的變量嗎？我猜N代表所有鄰居的集合。你是否認爲SAMPLES和K_SAMPLES是固定的？因爲那時他們在計算big-O時就不會考慮。 – 2013-03-05 20:53:26

是的。修復了這個問題，謝謝@nhahtdh – karlphillip 2013-03-05 20:58:50

最壞情況分析會從最內圈到最外圈（with mild abuse of the "=" sign）：

-> O(K_SAMPLES)     -- complexity of just the k-loop 

-> neighbors * O(K_SAMPLES)   -- complexity of f-loop accounted for 
= SAMPLES * O(K_SAMPLES)   -- since neighbors = SAMPLES in worst case 
= O(SAMPLES * K_SAMPLES) 

-> O(SAMPLES) + O(SAMPLES * K_SAMPLES) -- adding complexity of enumerate() 
= O(SAMPLES + SAMPLES * K_SAMPLES) 
= O(SAMPLES * K_SAMPLES)

SAMPLES由於SAMPLES * K_SAMPLES增長漸近較快，因此該項下降。更正式地，

When C >= 2, SAMPLES >= 1, K_SAMPLES >= 1 then 

SAMPLES + SAMPLES * K_SAMPLES <= C(SAMPLES * K_SAMPLES) 
SAMPLES * (K_SAMPLES + 1) <= SAMPLES * C * K_SAMPLES 
K_SAMPLES + 1 <= C * K_SAMPLES

有關具有多個變量的big-O的更多信息，請參見here。繼續與最後的循環，我們有：

-> SAMPLES * O(SAMPLES * K_SAMPLES) -- complexity of i-loop accounted for 
= O(SAMPLES^2 * K_SAMPLES)

請注意，根據由find_neighbors(i)返回的平均數，它可以使普通大O不同。

來源

2013-03-06 06:39:11 DPenner1

+1濫用。開玩笑，答案看起來不錯。我希望其他人也可以評估它，所以我可以關閉該線程。 – karlphillip 2013-03-06 13:31:33

O（鄰居* K_SAMPLES）

如果鄰居< < 10k，則這是更接近在K_SAMPLES到線狀

如果鄰居上K_SAMPLES的順序，這是二次在K_SAMPLES

來源

2013-03-05 20:52:10 javadba

算法分析（big-O）算法

回答

相關問題