您好,我用递归树方法解决了一个问题。然后我得出了下面的方程式。
n
∑ 3^(i-1)(n - (i - 1))
i=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)。
关于algorithm - 渐近上限,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42955946/