c - 以下两个 C 程序(迭代和归纳)中哪一个对于查找第 n 个斐波那契数更有效？

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 6 年前。

Improve this question

如上所述，尝试找出以下两个程序中哪一个对于查找第 n 个斐波那契数最有效以及原因。

斐波那契数是按以下顺序排列的数字:1、1、2、3、5、8...，其中前两个数字之后的每个数字都是前两个数字的总和。

////迭代////

int main()
{
int n;
int t1 = 0;
int t2 = 1;
int i;
int new_term;
printf("Enter N :");
scanf("%d", &n);
if (n == 1)
    new_term = 0;
else if (n == 2)
    new_term = 1;
else
{
    for (i = 3; i <= n; i++)
    {
        new_term = t1 + t2;
        t1 = t2;
        t2 = new_term;
    }
}
printf("%dth term of the series is %d", n, new_term);
return 0;
}

////归纳///

int fibo(int n);

int main() {
      int n;
    printf("Enter n : ");
    scanf("%d", &n);
    printf("The %dth term of Fibonacci sequence is %d", n, fibo(n));
    return 0;
}

int fibo(int n)
{
    if (n == 1) return 0;
    if (n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

Answer 1

这是一个算法问题，必须被视为一个算法问题。

迭代版本将在 O(n) 步内找到结果。

对于递归版本，由于您不使用记忆化，因此每个项将被计算多次。

假设 N(n) 是产生第 n 个数字的步骤数。您需要计算 fibo(n-1) 和 fib0(n-2) 并对它们求和。所以你需要 N(n-1) + N(n-2) + 1 步骤。忽略最后的总和，N(n) 与 fibo(n) 处于相同的数量级，而 fibo(n) 已知是指数的。

优化的递归算法可以在 O(n) 步中计算 fibo(n)，但代价是将数字存储在数组中(它们的效率仍然低于迭代方式)，但你的幼稚算法将具有糟糕的性能。

递归通常允许非常简单的算法，但性能却很差。