time-complexity - 为什么像 i=i*2 这样的代码在循环中被认为是 O(logN)？

Question

为什么因为 i=i*2，下面循环的运行时间被认为是 O(logN)？

for (int i = 1; i <= N;) {
  code with O(1);
  i = i * 2;
}

Answer 1

看看 1024 = 2¹⁰。您需要将数字 1 加倍多少次才能得到 1024？

Times    1   2   3   4    5    6    7    8     9      10
Result   2   4   8   16   32   64  128  256   512    1024

所以你必须运行你的加倍循环十次才能得到 2¹⁰ 通常，你必须运行你的加倍循环 n 次才能得到 2ⁿ。但是n是什么？它是 log₂ 2ⁿ，所以通常如果 n 是 2 的某个次方，循环必须运行 log₂n 次才能到达