嵌套for循環的運行時間是O（n^2）？

Question

我有這些嵌套循環

int sum = 0; 
for (int n = N; n > 0; n = n/2) { 
    for (int i = 0; i < n; i++) { 
     sum++; 
    } 
} 

外環拋出我從一點點。 運行時仍然是O（n^2）還是別的？

Answer 1

這裏內循環執行1 + 2 + ... + n/2 + n次。 它在這個序列中有lg個術語，這意味着int i = 0執行lg n次，

內部循環中語句的總和是2n。所以我們得到O（n + lg n）= O（n）