complexity-theory - 这个等式的大O？

 for (int j=0,k=0; j<n; j++)
   for (double m=1; m<n; m*=2)
      k++;

我认为是 O(n^2) 但我不确定。我正在解决一个练习问题，我有以下选择:

O(n^2)

O(2^n)

O(n!)

O(n log(n))

最佳答案

它的 O(nlog2n) 。代码块运行 n*log2n 次。

假设 n=16 ;然后第一个循环运行 16 (=n) 次。第二个循环运行 4(=log2n) 次 (m=1,2,4,8)。所以内部语句 k++ 运行了 64 次 = (n*log2n) 次。

关于complexity-theory - 这个等式的大O？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8815797/