7

所以，有人早些时候发布了这个问题，但基本上没有付出任何努力，它的标签很差，然后就关闭了。尽管如此，我认为这可能是一个很好的问题。我发布是因为根据 OP，我的回答（发表在评论中）不同意该解决方案。所以，我试图弄清楚我做错了什么（假设他的答案确实正确）：

我们有：

T(N) = T(N-1) + T(N-2) + T(N-3)

其中 N > 3。他没有列出基本情况，但由于 N > 3，我假设 和 可能有 3 个基本T(3)情况。要计算，我们执行以下操作：T(2)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))，N-3是为了解释三个基本情况，即在 T(4) 之后，我们只能有基本情况，没有更多的分支。

从未提供过实际的解决方案，但就像我说的那样，有人告诉我这是不正确的。任何帮助，将不胜感激。

4

3 回答 3

11

这是我学到的一个很酷的方法，所以我想我会与你分享。估计时间复杂度真的很简单。查看递归，我们猜测时间复杂度是指数级的。

让我们说：

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

你可以在这里找到它的三次方根。

这个三次方程有一个实根（1.8392867552141612）和两个复根（大小为 0.7373527）。

因此，我们算法的运行时间渐近地以T(N)=1.839^n为界。

于 2013-06-22T09:59:48.930 回答
9

您设置的重复周期如下：

T(n) = T(n - 1) + T(n - 2) + T(n - 3)

我认为基本情况可能是

T(0) = T(1) = T(2) = 1

如果您开始扩展此重复的条款，您会得到

  • T(0) = 1
  • T(1) = 1
  • T(2) = 1
  • T(3) = 3
  • T(4) = 5
  • T(5) = 9
  • T(6) = 17
  • T(7) = 31
  • ...

这里似乎没有明显的模式。幸运的是，我们可以去整数序列在线百科全书，输入 1、1、1、3、5、9、17 项，你会发现这是前三个项为 1的Tribonacci 序列。

如果您查看有关 Tribonacci 数字的信息，您将看到以下内容：

a(n)/a(n-1) 趋向于 tribonacci 常数，1.839286755...

（这里，a(n) 是网站用于我的 T(n) 的符号）。由于 Tribonacci 序列的连续项的比率趋向于大约 1.839286755，我们知道 Tribonacci 序列必须呈指数增长，并且它以大约 Θ(1.839286755 n ) 的速率呈指数增长。（将此与斐波那契数列进行比较，已知其在 Θ(φ n ) 处增长，其中 φ 是黄金比例）。在维基百科上做一些进一步的阅读给出了 Tribonacci 常数的这个公式：

在此处输入图像描述

并确认指数增长率。

因此，我们可以得出结论，运行时间是 Θ(1.839286755 n )。

那么......你将如何自己计算呢？最简单的方法（我认为这些值是已知的）是使用生成函数。您可以尝试为您在此处写出的递归推导生成函数，然后尝试以封闭形式重写生成函数以获得确切值。这是获得斐波那契数的封闭形式的一种方法，它应该在这里概括（尽管它可能会通过令人不快的数学来进行大量的努力。）或者，正如@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，您将返回一个新的列向量，其中包含循环中的后两个值，以及循环中的下一个值。这样，您可以通过计算 M k v 并查看向量的第一个分量来计算递归的第 k 个值。）

希望这可以帮助！

于 2013-06-21T21:18:39.713 回答
0

正如一些人所注意到的，这种重复与原来的重复不同T(N) = T(N-1) + T(N-2) - T(N-3)。我更喜欢T(N)=x^N@Aravind 给出的假设方法。通过这个递归，你得到了特征方程x^3-x^2-x+1=(x-1)^2(x+1)。（这将是@templatetypedef 的矩阵方法的特征方程，如果您采用这种方法，则是生成函数的分母。）

重复的根源导致各种困难。矩阵不可对角化。当你分解它时，生成函数有一个重复的分母。当您假设 时T(N)=x^N，您只会得到两个线性独立的解决方案，并且需要第三个。

一般来说，当你假设T(N)=x^N并得到一个双根r时，这意味着线性独立的解决方案是r^N和N*r^N（三根会引入N^2*r^N）。所以在我们的例子中，递归的三个线性独立解是(-1)^N、1^N=1和N*1^N=N。这意味着通解是T(N)=A(-1)^N+B+C*N，并且您使用初始条件来确定A、B和C。如果C!=0，那么T(N)=Θ(N)，否则T(N)=Θ(1)。对于算法来说，这可能不太现实。

于 2013-06-23T01:42:12.240 回答