为什么这个算法是O(nlogn)？

Question

我正在读一本关于算法分析的书,并且已经找到了一种我不知道如何获得时间复杂度的算法,尽管该书说它是O(nlogn).

这是算法:

sum1=0; 
for(k=1; k<=n; k*=2) 
  for(j=1; j<=n; j++) 
    sum1++;

Answer 1

在你的第一个循环for(k=1; k<=n; k*=2),可变k达到的值n的log n步骤,因为你加倍每个步骤中的价值.

第二个循环for(j=1; j<=n; j++)只是一个线性循环,因此需要n步骤.

因此,总O(nlogn)循环时间是嵌套的.

Answer 2

也许说服自己O(n*lgn)运行时间的最简单方法是在一张纸上运行算法.考虑当n为64时会发生什么.然后外部循环变量k将采用以下值:

1 2 4 8 16 32 64

的log_2(64)是6,其是上面加一个术语的数目.您可以继续这一推理,得出外循环将占用O(lgn)运行时间的结论.

内环完全独立于外环,是O(n).将这两个术语相乘得出O(lgn*n).