当内部循环的长度可变时，嵌套循环的大 O 是什么？

Question

这个的时间复杂度是多少？

外层循环是O(log n)。但是我不确定内循环？也是 O(log n) 吗？这会使整个算法成为 O(n log n) 吗？

while (n > 0) {
   for (let i = 0; i < n; i++) {
      /* O(1) code */
   }
   n = n / 2;
}

Answer 1

不内循环是O(n)

内部循环在 while 的每一步减少到 n/2。

所以这段代码在 O(2n - 1) 中运行，即 n + n/2 + n/4 + n/ 8 + 1 = 2*n - 1

while (n > 0) {  // O(logn)
  for (let i = 0; i < n; i++) { // O(n)
     /* O(1) code */
  }
  n = n / 2;

}