这个算法的复杂性是什么，我能把它加到无穷大吗？(what is the complexity of this algorithm , can i sum it to infinity?)

这个算法的复杂性是什么，我能把它加到无穷大吗？(what is the complexity of this algorithm , can i sum it to infinity?) Func(n) { i = n while(i>=1) g(i); i = i/3; }

这个算法的复杂性是什么？ （虽然g（n）的复杂度是theta（n²））我假设更大的n你说复杂性是

n 2 +（n / 3）2 +（n / 3 2）2 +（n / 3 3）2 ......到无穷大。

答案是theta（n²）。 真的吗？

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

what is the complexity of this algorithm? (while the complexity of g(n) is theta(n²)) I assumed for bigger n's you say that the complexity is

n² + (n/3)² + (n/3²)² + (n/3³)²..... to infinity.

And the answer is theta(n²). Is that true?

最满意答案

让我们看看我们掌握的系列。

=> 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³)²..... ]在下面。

Lets look at the series that we have got in our hands.

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

As [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ] is a decreasing series, it is equal to 1.

Thus the answer is O(n²)

---

EDIT 1:

Prove for the sum of series [ 1 + (1/3) + (1/3)² + (1/3²)² + (1/3³)²..... ], is below.