algorithm - 渐近上界

Question

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

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

Answer 1

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)。

Answer 2

设 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。