因此，有人在较早之前发布了此question，但基本上没有付出任何努力，它的标签标记不当，然后关闭。尽管如此，我认为这可能是一个很好的问题。我发布信息是因为根据OP，我的答案(发表在评论中)与解决方案不同。所以，我试图找出我做错了什么(假设他的回答确实正确):
我们有:
T(N) = T(N-1) + T(N-2) + T(N-3)
其中N>3。他没有列出基本案例，但是由于N> 3，我假设
T(3)，T(2)和T(1)大概有3个基本案例。要计算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个 child ，然后是9个 child ，然后是27个 child ，...，直到达到基本案例为止。因此，算法为
O(3^(N-3))，那里的N-3用来说明三个基本情况，即在T(4)之后，我们只能有基本情况，没有更多分支。从未提供过实际的解决方案，但是就像我说的那样，我被告知这是不正确的。任何帮助，将不胜感激。
最佳答案
您设置的重复周期如下:
我认为基本情况可能是
如果您开始扩展此重复发生的条款，您将获得
这里似乎没有明显的模式。幸运的是，我们可以转到整数序列在线百科全书，并在术语1、1、1、3、5、9、17中打洞，您会发现这是Tribonacci sequence，其前三个术语为1。
如果查看有关Tribonacci编号的信息，则会看到以下内容:
(此处，a(n)是网站用于我的T(n)的符号)。由于Tribonacci序列的连续项之比趋向于大约1.839286755，因此我们知道Tribonacci序列必须呈指数增长，并且它以大约Θ(1.839286755n)的速率呈指数增长。 (将其与斐波那契数列进行比较，已知斐波那契数列以Θ(φn)增长，其中φ是黄金比例)。进一步阅读Wikipedia可以得出Tribonacci常数的公式:
并确认指数增长率。
因此，我们可以得出结论，运行时间为Θ(1.839286755n)。
那么...您将如何自己计算呢？最简单的方法(我认为知道这些值的方法)是使用generating functions。您可以尝试为您在此处写出的重复次数派生一个生成函数，然后尝试以封闭形式重写该生成函数以获取确切的值。这是获取Fibonacci数闭式形式的一种方法，应该在此处进行概括(尽管可能会通过令人不快的数学进行大量测试。)或者，如@tmyklebu指出的那样，您可以写出此矩阵:
| 0 1 0 |
M = | 0 0 1 |
| 1 1 1 |
并计算其特征值，其中最大的将成为Tribonacci常数。 (请注意，此矩阵具有
| 0 1 0 | |a| | b |
| 0 0 1 | x |b| = | c |
| 1 1 1 | |c| |a + b + c|
因此，如果将递归中的三个连续值放入列向量v中并计算Mv，则会获得一个新列向量，其中包含递归中的后两个值以及递归中的下一个值。这样，您可以通过计算Mkv并查看向量的第一个分量来计算递归的第k个值。)
希望这可以帮助!
关于algorithm - 分析具有递归T(n)= T(n-1)+ T(n-2)+ T(n -3)的算法吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17244323/