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²)。 是真的吗？
最佳答案
如您所见，循环运行如下。
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)
关于algorithm - 这个算法的复杂度是多少，我可以把它加到无穷大吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34318891/