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...

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