分析具有递推的算法T(n)= T(n-1)+ T(n-2)+ T(n -3)？

Question

所以,有人早些时候发布了这个问题,但基本上没有付出任何努力,它标记很差,然后关闭.尽管如此,我认为这可能是个好问题.我发帖是因为根据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)之后,我们只能有基础情况,不再有分支.

实际的解决方案从未提供,但就像我说的,我被告知这是不正确的.任何帮助,将不胜感激.

Answer 1

您设置的重复发生如下:

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这两个术语进行操作,你会发现这是Tribonacci序列,前三个术语是1.

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

a(n)/ a(n-1)倾向于tribonacci常数,1.839286755 ......

(这里,a(n)是网站用于我的T(n)的符号).由于Tribonacci序列的连续项的比率倾向于约1.839286755,我们知道Tribonacci序列必须呈指数增长,并且它以大约Θ(1.839286755 ⁿ)的速率指数增长.(比较这对Fibonacci序列,其被称为在Θ(φ生长^Ñ),其中φ是黄金比例).在维基百科上做一些进一步的阅读,给出了Tribonacci常数的这个公式:

并确认指数增长率.

因此,我们可以得出结论,运行时是Θ(1.839286755 ⁿ).

那么......你将如何自己计算？最简单的方法(我认为这些值的已知方式)是使用生成函数.您可以尝试为此处写出的重复导出生成函数,然后尝试以封闭形式重写生成函数以获取精确值.这是获得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,则会返回一个新的列向量,其中包含重复的后两个值,以及重复中的下一个值.通过这种方式,您可以通过计算M ^k v并查看向量的第一个分量来计算递归的第k个值.)

希望这可以帮助!

Answer 2

这是我学到的一种很酷的方法,所以我想我会和你分享.估计时间复杂度真的很简单.看看复发,我们猜测时间复杂度是指数级的.

让我们说:

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的限制.