0

我以两种不同的方式计算斐波那契行。为什么 fib1 的执行时间比 fib2 长得多？

public class RecursionTest {

    @Test
    public void fib1() {
        long t = System.currentTimeMillis();

        long fib = fib1(47);

        System.out.println(fib + "  Completed fib1 in:" + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();

        fib = fib2(47);

        System.out.println(fib + "  Completed fib2 in:" + (System.currentTimeMillis() - t));

    }


    long fib1(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }


    long fib2(int n) {
        return n == 0 ? 0 : fib2x(n, 0, 1);
    }

    long fib2x(int n, long p0, long p1) {
        return n == 1 ? p1 : fib2x(n - 1, p1, p0 + p1);
    }
}

输出：

2971215073  Completed fib1 in:17414
2971215073  Completed fib2 in:0
4

4 回答 4

6

因为两种算法的工作方式完全不同。让我用 fib(5) 向你展示这个。

如果你调用 fib1(5)，它会在内部调用 fib1(4) 和 fib1(3)，让我们用一棵树来可视化它：

    纤维（5）
  / \
fib(4) fib(3)

现在，fib(4) 在内部调用 fib(3) 和 fib(2)。

所以现在我们有了这个：

           纤维（5）
          / \
    fib(4) fib(3)
    / \ / \
fib(3) fib(2) fib(2) fib(1)

我认为到现在为止，这是非常明显的，你应该能够填写其余部分。

编辑：您应该注意的另一件事是，它实际上必须多次执行相同的计算。在这张图片中，fib(2) 和 fib(3) 都被多次调用。如果起始数字更大，情况会变得更糟。/编辑

现在，让我们看一下 fib2(5)。如果你用 0 调用它，它返回 0。否则，它调用 fib2x(n, 0,1) 所以，我们调用了 fib2x(5,0,1)。fib2x(n, 0,1) 现在在内部调用 fib2x(n-1, p1, p0+p1) 等等。那么，让我们看看：

        
fib2x(5, 0,1) => fib2x(4, 1,1) => fib2x(3, 1, 2) => fib2x(2, 2, 3) => fib2x(1, 3, 5)

至此，已经达到返回条件，返回5。

因此，您的算法工作方式完全不同。第一个递归地从上到下工作。第二个从 1 开始，一直向上。实际上，它比递归更迭代（它可能被写成递归让你失望）。它保留已经计算的值而不是丢弃它们，因此需要调用的计算要少得多。

于 2012-06-07T17:30:50.860 回答
5

原因是两种算法具有不同的运行时复杂性：

于 2012-06-07T17:15:39.290 回答
3

最终，这是因为fib2只使用尾端递归。它最后只进行一次递归调用。因此，没有与递归相关的任何“分支”，并导致线性时间解决方案。它是尾调用的事实也导致某些编译器/VM 优化，其中递归可以转换为具有较低开销的迭代过程。

fib1除了导致运行时间呈指数增长的尾部调用之外，它还使用另一个递归调用。

于 2012-06-07T17:37:12.180 回答
2

fib1 是一种运行时间为 O(2^n) 的算法。fib2 是一种运行时间为 O(n) 的算法。

这样做的原因很酷——这是一种称为记忆的技术。程序所做的工作在每一步都保存下来，避免了任何无关的计算。

您可以通过将循环展开几个步骤来看到它：

long fib2(int n) {
    return n == 0 ? 0 : fib2x(n, 0, 1);
}
long fib2x(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xy(n - 1, 1, 1);
}
long fib2xy(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xyz(n - 1, 1, 2);
}
long fib2xyz(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xyz(n - 1, p1, p0 + p1);
}

您可以将此循环展开为斐波那契数列中的任意数字；每个步骤都建立在先前存储在堆栈中的计算之上，直到 n 耗尽。这与第一个算法形成对比，第一个算法必须在每一步都重做这项工作。漂亮！

于 2012-06-07T17:33:19.080 回答