时间复杂度(嵌套循环)

Question

你如何解决这个时间的复杂性？

int count=0;

for (int i=1 ; i < n; i*=4)

     for (int j=1;j<=n;j++)

              count++;

Answer 1

tl; dr:发布代码的复杂性是: O(nlogn)

让我们从内到外分析它.n对于每个值,内循环重复自己的时间i.

外环重复自身i < n,并且每次i都相乘4.这意味着,在第一次迭代之后i=1,然后i=4, i=16, i=64, ....在k'th迭代之后i = 4^(k-1).
这意味着,您在以下时间停止:

i >= n
4^(k-1) >= n
log_4(4^(k-1)) >= log_4(n)
k-1 >= log_4(n).

这意味着外循环将重复log_4(n) + 1.

将它们汇总在一起可以得到n*(log_4(n)+1)内循环重复的次数O(nlogn)