嵌套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）