算法复发T（n）的分析= T（N - 1）+ T（N - 2）+ T（N -3）？ [英] Analyzing an algorithm with recurrence T(n) = T(n - 1) + T(n - 2) + T(n -3)?

问题描述

所以，有人张贴了这个<一href="http://stackoverflow.com/questions/17239861/how-would-i-get-the-order-of-algorithm-tn-tn-1tn-2-tn-3#comment24985291_17239861">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）
 

等等... 这里有一棵树，再presentation：

  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名儿童，...，直到我们打我们的基本情况。因此，该算法是 0（3 ^（N-3））的 N-3 有交代三个基地的情况下，即T（4）后，我们只能有基础的情况下，没有更多的分支。

实际的解决方案是从来没有提供，但就像我说的，有人告诉我，这是不正确。任何帮助将是AP preciated。

解决方案

您已经设置了复发如下：

  

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，你会发现，这是<一href="http://oeis.org/search?q=1,%201,%201,%203,%205,%209,%2017&sort=&language=english&go=Search"相对=nofollow> Tribonacci序列的前三个条件是1。

如果你看一下有关Tribonacci号的信息，你会看到以下内容：

  

一（正）/一个（N-1）趋于tribonacci恒定，1.839286755 ...

（在此，一个（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，你回到一个新的列向量来自再现性保持后两者的值，加在复发的下一个值。通过这种方式，你可以通过计算中号计算复发的第k值 ^K V和观察向量的第一个组件。）

希望这有助于！

So, someone posted this question earlier, but essentially no effort was put into it, it was poorly tagged and then closed. Nonetheless, I think it could have been a good question. I'm posting because according to the OP, my answer (posted in a comment) did not agree with the solution. So, I'm trying to figure out what I'm doing incorrectly (assuming that the answer that he has in indeed correct):

We have:

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

where N > 3. He didn't have a base case listed, but since N > 3, I assumed that there are probably 3 base cases for T(3), T(2) and T(1) . To calculate T(K), we do the following:

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

Then we must calculate:

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)

and so on... Here's a tree-representation:

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)    
                 ...                                ...                                ...

So we have 3 children, then 9 children, then 27 children,..., until we hit our base cases. Hence, the algorithm is O(3^(N-3)), the N-3 is there to account for the three base cases, ie after T(4), we can only have bases cases, no more branching.

The actual solution was never provided, but like I said, I'm told that this is incorrect. Any help would be appreciated.

解决方案

The recurrence you have set up is the following:

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

I assume the base cases are probably

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

If you start to expand out the terms of this recurrence, you get

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

There doesn't seem to be an obvious pattern here. Fortunately, we can go to the Online Encyclopedia of Integer Sequences and punch in the terms 1, 1, 1, 3, 5, 9, 17 and you'll find that this is the Tribonacci sequence whose first three terms are 1.

If you look at the information about the Tribonacci numbers, you'll see the following:

a(n)/a(n-1) tends to the tribonacci constant, 1.839286755...

(here, a(n) is the notation the site uses for my T(n)). Since the ratio of consecutive terms of the Tribonacci sequence tends to approximately 1.839286755, we know that the Tribonacci sequence must be exponentially growing, and it grows exponentially at a rate that is approximately Θ(1.839286755ⁿ). (Compare this to the Fibonacci sequence, which is known to grow at Θ(φⁿ), where φ is the golden ratio). Doing some further reading on Wikipedia gives this formula for the Tribonacci constant:

and confirms the exponential growth rate.

Consequently, we can conclude that the runtime is Θ(1.839286755ⁿ).

So... how would you compute this on your own? The easiest way to do this (and I think the way that these values are known) is to use generating functions. You can try to derive a generating function for the recurrence you have written out here, then try to rewrite the generating function in a closed-form to get the exact value. This is one way to get the closed-form for Fibonacci numbers, and it should generalize here (though it might be a lot of slogging through unpleasant math.) Alternatively, as @tmyklebu points out, you could write out this matrix:

     | 0 1 0 |
 M = | 0 0 1 |
     | 1 1 1 |

and compute its eigenvalues, the largest of which will come out to the Tribonacci constant. (Note that this matrix has the property that

 | 0 1 0 |   |a|   |    b    |
 | 0 0 1 | x |b| = |    c    |
 | 1 1 1 |   |c|   |a + b + c|

Consequently, if you put three consecutive values from the recurrence into a column vector v and compute Mv, you get back a new column vector holding the latter two values from the recurrence, plus the next value in the recurrence. In this way, you can compute the kth value of the recurrence by computing M^kv and looking at the first component of the vector.)

Hope this helps!

这篇关于算法复发T（n）的分析= T（N - 1）+ T（N - 2）+ T（N -3）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！