这个算法的复杂度是多少，我可以把它加到无穷大吗？

Question

Func(n)
{
   i = n
   while(i>=1)
      g(i);
      i = i/3;
}

这个算法的复杂度是多少？（而 g(n) 的复杂度是 theta(n²)）我假设对于更大的 n 你说复杂度是

n² + (n/3)² + (n/3²)² + (n/3³)²..... 到无穷大。

答案是 theta(n²)。是真的吗？

Answer 1

让我们看看我们拿到手的这个系列

=> n² + (n²/3) + (n/3)² + (n/3²)² + (n/3³)²..... 
taking n² common
=> n² * [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ]

因为[ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ]是递减级数，所以等于1.

所以答案是O(n²)

编辑 1：

证明级数[ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ]的总和如下。

Answer 2

如您所见，循环运行如下。

Iteration 1: n^2 = n^2/3^0
Iteration 2: (n/3)^2 = n^2/3^2
Iteration 3: (n/3^2)^2 = n^2/3^4
Iteration 4: (n/3^3)^2 = n^2/3^6
...
Iteration k: (n/3^(k-1))^2 = n^2/3^(2*(k-1))

使用等比级数求和公式，我们得到总耗时为

T(iteration1) + T(iteration2) + ... + T(Iterationk)

term 1 = n^2
ratio = 1/9
sum = 9 * n^2 / 8

当K是一个可以假定为无穷大的大数时。

由于大 O 符号忽略常量，

O( 9* n^2 /8) = O(n^2)

Answer 3

严格来说，i是一个整数，它很快就会变成正好0（在floor(log3(n)）次迭代之后），所以没有理由去无穷大。

无论如何，将 i 视为有理数会导致真实公式的近似值不会改变渐近行为，仍然是 O(n²)。近似值以两种方式出现

i/3 可能与 floor(i/3);
一个可以加到无穷；小于 1 的项加起来只有 4/3 更差，完全可以忽略不计。

这个算法的复杂度是多少，我可以把它加到无穷大吗？

what is the complexity of this algorithm , can i sum it to infinity?

algorithm

loops

while-loop

time-complexity

logarithm