渐近上限

Question

嗨，我用递归树方法解决了一个问题。然后我得出了下面的方程式。 n ∑ 3^(i-1)(n - (i - 1)) i=1

我需要找到该方程的渐近上限。任何帮助，将不胜感激。

Answer 1

令u(n) = 3^(n-1) + 2*3^(n-2) + ... + n，则
u(n+1) = (3^n + 3^(n-1) + ... + 1) + 3^(n-1) + 2*3^(n-2) + ... + n = (3^(n+1)-1)/2 + u(n) = 3*u(n) + n + 1 u(n) = (3^(n+1) - 2n - 3) / 4.

Answer 2

Wolfram Alpha 是一个很好的工具：https://www.wolframalpha.com/input/?i=sum(3%5E(i-1)(n+-+i+%2B+1)+for+i+%3D+1..n)

该工具将总和简化为：(-2n + 3^(n+1) - 3)/4。

用大 O 来说就是 O(3^n)。