Big O - 嵌套環

Question

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代表內部）？

Answer 1

如果這樣做

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 

Answer 2

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