java - for循环算法的Big-O分析

Question

我在分析以下 for 循环算法时遇到问题:

for (int i = 1; i < n; i = i * C)
    for (int j = 0; j < i; j++)
        Sum[i] += j * Sum[i];

我知道第一行的复杂度为 O(logn)(只要 C > 1)，但让我难过的是第二行。我相信我了解它正在发生的事情的基础知识:

例如，

if n=20, the inner loop will do 1+2+4+8+16 "work".

但是我不知道怎么写出来。我几乎可以肯定循环中完成的总工作量是 O(n)，第一行是 O(logn)，但我如何更具体地指定中间行的作用？

Answer 1

i 将具有以下形式的值:

C^0, C^1, C^2, ...., C^ log_c(n)

因此内部循环将运行C^0 + C^1 + C^2 + ... + C^log_c(n) 次。这是一个几何级数，总结为:

所以用 C 代替 r，用 log_c(n) 代替 n 我们得到:

(1-C^log_c(n))/(1-C) = (1-n)/(1-C)，对于任何 C > 1 都是正的 并与 n 成正比。因此，复杂度确实是 O(n)。

(公式图片取自Wikipedia)