3

有点类似于斐波那契数列

算法的运行时间由下式给出

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

= n 否则这个算法的顺序是？

如果用归纳法计算那么

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

让我们假设 T(n) 是某个函数 aⁿ<br> 然后 aⁿ = a n-1 + a n-2 + a n-3
=> a³ = a² + a + 1

根据我的计算，它给出了复杂的解决方案也是上述方程的根

a = 1.839286755
a = 0.419643 - i ( 0.606291) 
a = 0.419643 + i ( 0.606291)

现在，我该如何进一步进行，或者还有其他方法吗？

4

3 回答 3

3

如果我没记错的话，当你确定了特征方程的根时，那么 T(n) 可以是这些根的幂的线性组合

T(n)=A1*root1^n+A2*root2^n+A3*root3^n

所以我猜这里的最大复杂度将是 (maxroot)^n 其中 maxroot 是你的根的最大绝对值。所以对于你的情况，它是 ~ 1.83^n

于 2012-09-27T13:21:18.603 回答
0

对程序的运行时间进行了渐近分析，这让我们知道运行时间将如何随着输入而增长。

对于重复关系（就像您提到的那样），我们使用两步过程：

  1. 使用递归树方法估计运行时间。
  2. 使用替代方法验证（确认）估计。

您可以在任何算法文本（例如 Cormen）中找到这些方法的解释。

于 2012-09-27T18:52:12.180 回答
0

它可以近似为 3+9+27+......3^n 即 O(3^n)

于 2015-01-27T17:27:01.403 回答