这个等式的大O？

Question

 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 log(n))

Answer 1

嗯......好吧,把它分解吧.

外环似乎很明显是O(n).每次迭代增加1.然而,内环增加2的幂.指数肯定与对数相关(实际上是反向).

你为什么要来O(n ^ 2)解决方案？证明给我看.