-2

这个程序计算斐波那契数。我想使用递归关系找出它的时间复杂度。

Fib(n)
if n<=1
  return n
else
  x= Fib(n-1)
  y= Fib(n-2)
  return x+y

该程序的递推方程为 T(n)=T(n-1)+T(n-2)+c

我试图消耗它，但找不到解决方案。

 =2T(n-1)+T(n-3)+c+c
 =3T(n-3)+2T(n-4)+c+c+3c
 =5T(n-4)+3T(n-3)+c+c+3c+5c
 -------------------------
 -------------------------
 -------------------------
4

3 回答 3

1

您需要考虑对函数进行了多少次调用。每次调用都会产生 2，因此它会产生一棵二叉树：

n

(n-1)-------------(n-2)

(n-2)--(n-3)------(n-3)---(n-4)

等等。

当你第一次达到 1 时考虑树的级别并忽略下面的所有内容。这发生在第 n/2 级（因为每个级别的最小数字是最右边的，并且它总是减少 2）。很明显，直到 n/2 的每一层上的节点总是是前一层的两倍。

因此节点总数为 1 + 2 + 2^2 + ... + 2^(n/2) = 2^(n/2+1) - 1 = O(2^(n/2))

这意味着时间复杂度至少是指数级的。

您可能可以更准确地计算它，但出于所有实际目的，这应该足以避免这种实现。

于 2013-04-03T09:11:42.940 回答
1

给定的递归关系是，

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

1-2 -> T(n) = 2T(n-1) - T(n-3) ----- 3
T(n) - 2T(n-1) + T(n-3) = 0 ----- 4

4的特征方程为x 3 - 2x 2 + 1 = 0 ---- 5

求解方程 5，

解决方案x = 1是x = (1 + √5)/2和x = (1 −√5)/2

一般解决方案是 T n = a((1 + √5)/2) n + b((1 - √5)/2) n + c 。1个

T n = a((1 + √5)/2) n + b((1 - √5)/2) n + c

让我们假设T(0) = 0，从等式 1 我们得到T(1) = c和T(2) = 2c

其中， T(0) = a + b + c = 0 ---- 6

T(1) = a((1 + √5)/2) + b((1 - √5)/2) + c = c

有a((1 + √5)/2) + b((1 - √5)/2) = 0 ----- 7

T(2) = a((1 + √5)/2) 2 + b((1 - √5)/2) 2 + c = 2c

有a((1 + √5)/2) 2 + b((1 - √5)/2) 2 = c ---- 8

求解 6、7 和 8，得到 a、b 和 c 的值。

一般的解决方案是，

T n = a((1 + √5)/2) n + b((1 - √5)/2) n + c

因为(1 + √5)/2 < 2 ,

T(n) = O( 2n )。

于 2013-04-03T14:35:34.427 回答
0

关于您的递归关系需要注意的是，它与 Fibonacci 递归本身相同。这意味着c无论您计算的是什么斐波那契数，您都在做工作时间单位。您可以从您计算的前几个步骤中自己看到它。开始像斐波那c契数列一样增长。

基本上你的复发归结为 O(Fib(n))。斐波那契数在 中是指数的n，所以你要做指数工作。

一个更好的方法是记住其中一个数字。像这样：

Fib(n):
    if n <= 2:
        return 1,0
    else:
        x,y = Fib(n-1)
        return x+y,x

因此，当您调用 时Fib(n)，您会得到两个值，Fib(n) 和 Fib(n-1)。您返回的额外x内容“记住”了 Fib(n-2)，因此您不必计算两次。这种递归归结为T(n) = T(n-1) + c，即 O(n)。

一旦你有了它，你可以把它减少到一个不错的小 for 循环：

x = 1, y = 0
for i from 3 to n:
    x,y = x+y,x
于 2013-04-03T09:27:49.513 回答