本文介绍了算法复发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)
 

等等...这里有一棵树,再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(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,你会发现,这是。你可以尝试推导出生成函数你写在这里再次发生,然后尝试重写生成函数在一个封闭的形式得到确切的价值。这是获得封闭形式的斐波那契数的一种方式,它应该在这里推广(虽然它可能有很多不愉快的,通过苦读数学的)。另一方面,作为@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值 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:

I assume the base cases are probably

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:

(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 Mv and looking at the first component of the vector.)

Hope this helps!

这篇关于算法复发T(n)的分析= T(N - 1)+ T(N - 2)+ T(N -3)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 10:29
查看更多