于是，有人发了这个question https://stackoverflow.com/questions/17239861/how-would-i-get-the-order-of-algorithm-tn-tn-1tn-2-tn-3#comment24985291_17239861早些时候，但基本上没有付出任何努力，它的标签很差，然后被关闭。尽管如此，我认为这可能是一个很好的问题。我发帖是因为根据OP，我的答案（发布在评论中）不同意该解决方案。所以，我试图找出我做错了什么（假设他的答案确实正确）：
We have:
T(N) = T(N-1) + T(N-2) + T(N-3)
其中 N > 3。他没有列出基本情况，但由于 N > 3，我假设可能有 3 个基本情况T(3), T(2) and T(1)。计算T(K)，我们执行以下操作：
T(K) = T(K-1) + T(K-2) + T(K-3)
那么我们必须计算：
T(K-1) = T((K-1)-1) + T((K-1)-2) + T((K-1)-3)
T(K-2) = T((K-2)-1) + T((K-2)-2) + T((K-2)-3)
T(K-3) = T((K-3)-1) + T((K-3)-2) + T((K-3)-3)
等等...
这是一个树表示：
L0 T(K)
/ | \
L1 T(K-1) T(K-2) T(K-3)
/ | \ / | \ / | \
L2 T((K-1)-1) T((K-1)-2) T((K-1)-3) T((K-2)-1) T((K-2)-2) T((K-2)-3) T((K-3)-1) T((K-3)-2) T((K-3)-3)
... ... ...
所以我们有 3 个孩子，然后是 9 个孩子，然后是 27 个孩子，......，直到达到我们的基本情况。因此，算法是O(3^(N-3)), the N-3是否要考虑三个基本情况，即在 T(4) 之后，我们只能有基本情况，不再有分支。
从未提供实际的解决方案，但正如我所说，我被告知这是不正确的。任何帮助，将不胜感激。
这是我学到的一个很酷的方法，所以我想我会与你分享。估计时间复杂度非常简单。
从递归来看，我们猜测时间复杂度是指数级的。
可以说：
T(N)=x^n
给定的递归是
T(N) = T(N-1) + T(N-2) + T(N-3)
替代
x^n = x^n-1 + x^n-2 + x^n-3
Dividing throughout by x^n-3
x^3 = x^2 + x^1 + 1
Rearranging
x^3 - x^2 - x - 1=0
你可以找出它的立方根here http://www.1728.org/cubic.htm.
该三次方程有一个实根（1.8392867552141612）和两个复根（数量级为0.7373527）。
因此，我们算法的运行时间渐进地受到以下限制：T(N)=1.839^n.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
