嵌套循环的时间复杂度

Question

下面是嵌套的for循环。我计算出它的时间复杂度是nlg(n)。

 int sum = 0;
 for(int k = 1; k < n; k*=2){
     for(int i = 1; i < n; i++){
            sum++;
     }
 }

我的想法如下。

1. 外部for循环：k将取值1，2，4，8，.因此，它将进行lg(n)迭代。
2. 内部for循环：i将进行n次迭代。

因此，所采取的整体行动将是nlg(n)。

我说的对吗？

Answer 1

是的，你建议的增长顺序是正确的。您可以如下所示：

​

​