Big O - 嵌套環

big-o

2013-06-23 62 views 5 likes

void bar(int N){ 
    int c=0; 
    for (int i=0; i<N*N; i++) 
    for (int j= i; j< N; j++) 
     c++; 
}

上面的外層（和內層）循環永遠不會通過N.這是否意味着大O是N * N（N代表外部，N代表內部）？Big O - 嵌套環

來源

2013-06-23 RobotRock

你爲什麼在外環使用'N * N'？只需在循環結束後顯示'c';這會告訴你你需要知道什麼。 –

複雜性是BigO（N^3） –

@Tudor Vintilescu你能解釋一下你的理由嗎？ – RobotRock

回答

如果這樣做

for (int i = 0; i < N; i++) 
    for (int j = i; j < N; j++) 
    …

你會在內部循環迭代第一N次，則N-1，則N-2，等，這些總計爲N（N-1）/ 2 。該循環以O（N²）運行，即外環的平方。

在你的情況，你的代碼就相當於

for (int i = 0; i < N; i++) 
    for (int j = i; j < N; j++) 
    c++;

因爲對於每一個正整數我們有N²≥N和編譯器應該足夠聰明，發現它是沒有意義的繼續運行外環如果我大於N.那麼複雜度確實是O（N²）。

如果您打印程序運行後N和c，你會發現，當N得到翻倍，c幾乎被4（2 2）乘以：

N = 1, c = 1 
N = 2, c = 3 
N = 4, c = 10 
N = 8, c = 36 
N = 16, c = 136 
N = 32, c = 528 
N = 64, c = 2080 
N = 128, c = 8256 
N = 256, c = 32896 
N = 512, c = 131328 
N = 1024, c = 524800 
N = 2048, c = 2098176

來源

2013-06-23 11:06:34

感謝您的透明解釋！ – RobotRock

要正式地知道迭代次數和爲了增長：

enter image description here

來源

2014-03-17 22:05:43

相關問題

11. 嵌套的for循環僅O（n）
12. 大O帶獨立嵌套環
13. 3個嵌套for循環的大O？
14. Big-O算法
15. Matrix Big O Notation
16. Complexity and Big-O
17. 確定此循環的BIg O符號
18. 計算計算複雜度（Big-O）
19. 嵌套循環的大O，有不同的迭代？
20. Sorted array Big o notation
21. 大O嵌套循環分解循環循環
22. Tricky Big-O複雜性
23. 嵌套循環
24. 任意嵌套循環的大O分析？
25. Redux/ImmutableJS嵌套狀態+ Big-o不可變集合的複雜性
26. 用於使用散列表查找的四嵌套循環的big theta
27. C++嵌套循環
28. 如何計算Big-O？
29. Big-O和常數除
30. BIG-O /大哦符號