使用记忆化(Memoization)的递归斐波那契程序的时间复杂度证明-java教程-PHP中文网

使用记忆化(Memoization)的递归斐波那契程序的时间复杂度证明

花韻仙語

发布： 2025-11-16 11:08:01

原创

330人浏览过

使用记忆化(memoization)的递归斐波那契程序的时间复杂度证明

本文旨在通过数学方法证明使用记忆化技巧优化的递归斐波那契程序的O(n)时间复杂度。我们将通过分析递归调用树的结构变化，展示记忆化如何将重复计算转化为常数时间查找，从而显著降低整体时间复杂度，并给出推导过程。

斐波那契数列与递归实现

斐波那契数列是一个经典的数列，定义如下：

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

最直接的实现方式是使用递归。然而，未经优化的递归实现效率非常低下。

public class Fibonacci {

    public static long fibonacciRecursive(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fibonacciRecursive(n));
    }
}

登录后复制

原始递归的时间复杂度分析

未优化的递归实现中，计算fibonacciRecursive(n)需要计算fibonacciRecursive(n-1)和fibonacciRecursive(n-2)，而计算fibonacciRecursive(n-1)又需要计算fibonacciRecursive(n-2)和fibonacciRecursive(n-3)，以此类推。可以看到存在大量的重复计算。

递归调用树呈指数级增长，时间复杂度为O(2ⁿ)。具体推导如下：

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

假设 T(n-1) ≈ T(n-2)，则：

T(n) ≈ 2T(n-1) + c

= 4T(n-2) + 3c

= 8T(n-3) + 7c

= 2^kT(n-k) + (2^k - 1)c

当 n - k = 0，即 k = n 时：

T(n) = 2ⁿT(0) + (2ⁿ - 1)c

T(n) = (1 + c) * 2ⁿ - c

T(n) <= 2ⁿ

因此，时间复杂度为 O(2ⁿ)。

使用记忆化优化递归

记忆化是一种动态规划的优化技巧，通过存储已经计算过的结果，避免重复计算。

喵记多

喵记多 - 自带助理的 AI 笔记

查看详情

import java.util.Arrays;

public class FibonacciMemoization {

    private static long[] memo;

    public static long fibonacciMemoization(int n) {
        memo = new long[n + 1];
        Arrays.fill(memo, 0);
        return fib(n);
    }

    private static long fib(int n) {
        if (n <= 1) return n;

        if (memo[n] != 0) {
            return memo[n];
        }

        long result = fib(n - 1) + fib(n - 2);
        memo[n] = result;

        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fibonacciMemoization(n));
    }
}

登录后复制