大哦嵌套，而

我有一些大oh問題的挑戰。這些不是家庭作業問題。我寫這些問題是爲了更好地理解這裏的概念。大哦嵌套，而

function func(n) 
{ 
    int k,i = 0; 
    while(k < n){ < --- Guessing this outer loop is O(n/2) 
     k = n + 2 
     i = 0; 
     while(i < k){ <--- Not sure what this is? 
      i ++; 
      i = i * i; 
     } 
     }   
}

我真的喜歡它，如果你能向我解釋什麼是在內環怎麼回事，怎麼你的邏輯在大O符號，你終於在最後結束。

來源

2012-10-30 bluejamesbond

'k = n + 2'不應該是：'k = k + 2'還是類似的東西？現在你的外層循環不會迭代多次。 – Joost

我估計時間複雜度仍然停留在O（n * m）。內部循環是O（m），外部循環，就像你提到的那樣，是O（n/2）。總結它是O（n * m）/ 2。 2是一個常數，隨着投入量的增加，它將與比率無關。我正在學習自己。所以，我可能是錯的。 –

您可能對[此問題]感興趣（http://cs.stackexchange.com/questions/4800/the-order-of-growth-analysis-of-simple-for-loop）[cs.se]和這些問題與Raphael的評論有關。 – Gilles

雖然@alestanis提供什麼樣子對我來說，這個問題比那些評論的多少更準確的分析，我仍然不認爲這是完全正確的。

讓我們創建一個打印出由內循環產生i值的小測試程序：

#include <iostream> 

void inner(double k) { 
    double i; 

    i = 0.0; 
    while(i < k) { 
     i ++; 
     i = i * i; 
     std::cout << i << "\n"; 
    } 
} 

int main() { 
    inner(1e200); 
    return 0; 
}

當我運行它，結果我得到的是：

1 
4 
25 
676 
458329 
2.10066e+011 
4.41279e+022 
1.94727e+045 
3.79186e+090 
1.43782e+181 
1.#INF

如果迭代次數是對數的，那麼達到特定數字的迭代次數應該與限制中的位數成正比。例如，如果它是對數的，則應該花費大約180次迭代才能達到1e181，給出或採取一些（相當小的）恆定因子。這顯然不是這種情況 - 通過用科學計數法查看結果的指數可以很容易地看出，這大約是每次迭代的數字數量的兩倍，其中對數表示每次迭代大致增加一位數字。

我不是絕對的確定，但我相信把內部循環放在類似O（log log N）而不是O（log N）的東西上。我認爲可以很容易地認同外部循環可能是O（N）（儘管它目前只寫入一次），總體複雜度爲O(N log log N)。

我覺得有必要補充一點，從實用的角度來看，O(log log N)通常可以被視爲基本常量 - 如上所示，只有11次迭代才能達到您可以用一個典型雙精度浮點數指定的最高限制。因此，對於大多數實際目的而言，整體複雜度可以被視爲O(N)。

[糟糕 - 沒有注意到他在我寫這篇文章時已經回答了，但是看起來@ jwpat7已經達到了我所做的相同的結論。對他/她的稱讚。]

來源

2012-10-30 17:25:30

我同意內部循環的複雜度是O（log log N）。由於（...（（（1 + 1）^ 2 + 1）^ 2 + 1）^ 2 + ...）^ 2增長速度顯着快於exp，我不知道它是否是θ（log log N）（exp（p/2））p –

@ jwpat7：是的，我想過試圖更徹底地分析它，但結果是迭代次數接近常數，我很難真正關心它。 .. –

第二個循環的值爲i，直到達到k。如果我們忽略常量項，則此循環運行時間爲O(log k)。

爲什麼？因爲如果你解決i^m = k你得到m = constant * log(k)。

正如你所說，外層循環運行在O(n)時間。

由於k的較大值取決於n，因此可以說內循環在O(log n)中運行，這會使您的總體複雜度爲O(n log n)。

來源

2012-10-30 16:34:51 alestanis

外循環及其測試(k < n)及其步驟k = n + 2將運行一次，提供O（1）複雜度因子。

內環具有測試(i < k)這就是說(i < n+2)，且具有步驟i++; i=i*i;最後，

i = (...(((1+1)^2+1)^2+1)^2+ ...)^2 > n+2`

這使得i超指數的值。也就是說，i在p遍中比exp（exp（p））增長得快，因此總體複雜度小於O（log log n）。這是比前面提到的O（log n）更緊的界限，它也是一個上限但不是很緊。

來源

2012-10-30 17:15:34

大哦嵌套，而

回答

相關問題