使用递归公式 T(n) = T(n - 1) + T(n - 2) + c 分析算法？

Question

使用递归公式 T(n) = T(n - 1) + T(n - 2) + c 分析算法？

algorithmrecursiontime-complexitybig-oasymptotic-complexity

4

我知道这种类型的方程可以用许多方法来解决，但我想使用递归树方法来解决这个方程。有人能向我展示如何使用递归树方法吗？

- Natsu

3

你应该先尝试，然后我们可以帮你修正。 - BlackBear

1

isT(n)保证为非负数吗？ - wildplasser

可能是 https://dev59.com/1XRC5IYBdhLWcg3wP-n5 的重复问题。 - Codor

1

是否有锚点？例如T(0)=0和T(1)=0？ - fafl

可能是斐波那契数列的计算复杂度的重复问题。 - user4668606

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jayson Boubin · Accepted Answer

递归树用于绘制递归算法的执行过程。您所描述的这个递归问题基本上与递归斐波那契算法相同，其中使用以下方程式：

F(n) = F(n-1) + F(n-2)

使用类似以下算法的递归求解：

int fib(int x) {
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2); //Does this recurrence look familiar?
}

对于输入5，它会产生以下树形结构：

                    5
                   / \
                  /   \
                 /     \ 
                /       \     
               /         \
              /           \
             /             \
            4               3
           / \             / \
          /   \           /   1
         /     \         2
        3       2       / \
       / \     / \     1   0
      /   \   /   \  
     2     1 1     0
    / \
   /   \
  1     0

上面，我画了一个非常简单的斐波那契数列递归树。我只是插入了第一个数字（5），并继续从其后续的递归调用中产生一个简单的树形结构。你可以看到树的高度是N，分支因子是2，因此我们的上限必须是O(2^n)。你可以通过推广这个方法来得到你想要找到的特定问题的答案以及任何其他递归关系式。