你如何計算第二循環的複雜性？

Question

對於這個for循環中的Python：

for(int a = 1 ; a < N ; a*=2) 
     for(int b =1 ; b <N ; b++) 

我知道代碼中O(n*log(n))完成，但如果循環是：

For(int a = 1 ; a <N ; a*=2) 
    for(int b = 1 ; b < a ; b++) 

還會否在O(n*log(n))完成？

Answer 1

是（和否）。嚴格按照Big O的定義，我們將在下面看到第二個算法是O(n*log(n))，但是具有更好的界限。

首先，讓我們回顧第一個循環的想法。如果我們將每個循環迭代稱爲一個計算單位，則可以說總計算量爲sum(sum(1 from 0 to N) from 0 to log2(N))，這只是N log2(N)（可能是一個）。這個結果表明第一組循環是O(N log(N))。

現在爲第二套。重複上述過程，我們有sum(sum(1 from 0 to *a*) from 0 to log2(N)) = (log2(2 N) log2(4 N)) <= k [log(N)]^2，所以第二個算法是O(log^2(N))（被稱爲多對數）。

請注意，k N log(N)（對於某些k）仍然是第二個算法的上限，所以嚴格來說它仍然是O(N log(N)。

這裏是運行時的預期增長的圖像：

紅色是第一套循環，綠色是第二組環，藍色爲2N log(N)。