我在分析以下 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)，但我如何更具体地指定中间行的作用？
最佳答案
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)
关于java - for循环算法的Big-O分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48466483/