algorithm - 我怎样才能找到这个代码段的复杂度？

Question

这是我正在谈论的代码段的伪代码，

temp = 1

repeat
  for i = 1 to n
    temp = temp+1;

  n = n/2;
until n<=1

我知道外层循环(repeat)执行了 n 次。 for循环呢？可以将其视为 n/2 的递归调用吗？我如何在这里应用主定理？

Answer 1

在外循环的第一次迭代中，内循环将执行n 次。在下一次迭代中，内部循环将执行 n/2 次，依此类推...

因此，我们有几何级数的和 n + n/2 + n/4 + ... 即 2*n 或 O(n )。