algorithm - 最坏情况下的时间复杂度是多少？

Question

for(int i = 1 ; i < n ; i* = 2)
for(int j = 1 ; j < i ; j* = 2)

谁能给我解释一下？我认为是log(n)*log(i)。对吗？

Answer 1

假设

for (i = 1; i < n; i *= 2)
   for (j = 1; j < i; j *= 2)
      ...stuff...

“东西”将运行 1 + 2 + 3 + ... + log(n)-1 次。由于整数 1 到 N 的总和为 N * (N + 1) / 2，因此最坏情况的运行时间为 O(log(n) ^ 2)。