C语言中如何将斐波那契数列时间复杂度降至O(n)？

Great question! Since you already understand how Python uses dictionaries for memoization to cut Fibonacci's time complexity down to O(n), let's walk through the equivalent (and even more efficient) approaches in C.

1. Iterative Approach (Most Efficient, O(n) Time, O(1) Space) #

The simplest way to get O(n) time in C is to ditch recursion entirely and compute Fibonacci numbers iteratively, starting from the bottom up. This avoids all the repeated calculations that plague naive recursive solutions, and uses almost no extra space—just a few variables to track previous values.

Here's a code example:

#include <stdio.h>

long long fib(int n) {
    // Base cases: fib(0) = 0, fib(1) = 1
    if (n <= 1) return n;
    
    long long prev_prev = 0; // Holds fib(i-2)
    long long prev = 1;      // Holds fib(i-1)
    long long current;       // Holds fib(i)
    
    for (int i = 2; i <= n; i++) {
        current = prev_prev + prev;
        // Shift values for next iteration
        prev_prev = prev;
        prev = current;
    }
    
    return prev;
}

int main() {
    printf("fib(10) = %lld\n", fib(10)); // Outputs 55
    return 0;
}

This approach runs in exactly O(n) time (we loop from 2 to n once) and uses constant O(1) space—no extra arrays or dynamic memory needed. It's the go-to solution for most practical use cases because it avoids recursion's stack overhead.

2. Memoization (Recursive with Caching, O(n) Time, O(n) Space) #

If you want a direct equivalent to Python's dictionary-based memoization, C doesn't have built-in dictionaries, but we can use an array (since Fibonacci indices are sequential integers) to cache computed values. Arrays offer O(1) access time, which is even faster than dictionary lookups.

Here's how to implement memoized recursion:

#include <stdio.h>
#include <stdlib.h>

long long* memo;

long long fib_memo(int n) {
    if (n <= 1) return n;
    // Check if we've already calculated this value
    if (memo[n] != -1) return memo[n];
    // Compute and store the result in the memo array
    memo[n] = fib_memo(n-1) + fib_memo(n-2);
    return memo[n];
}

int main() {
    int n = 10;
    // Allocate memory for memoization array
    memo = (long long*)malloc((n+1)*sizeof(long long));
    if (memo == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }
    // Initialize all entries to -1 (uncomputed state)
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    // Set base cases
    memo[0] = 0;
    memo[1] = 1;
    
    printf("fib(10) = %lld\n", fib_memo(n)); // Outputs 55
    
    // Clean up allocated memory
    free(memo);
    return 0;
}

How this works: #

• We allocate an array memo where memo[i] stores the value of fib(i) once computed.
• Before calculating fib(n), we check if memo[n] is already set (not -1). If yes, we return the cached value instead of recalculating.
• This ensures each Fibonacci number is computed exactly once, leading to O(n) time complexity. The space complexity is O(n) to store the memo array.

Alternatively, you can use a static array if you know the maximum n in advance (avoids dynamic memory allocation), but dynamic allocation is more flexible for arbitrary n.

Key Takeaway #

Yes, C absolutely has equivalent optimization methods to Python's dictionary approach:

• The iterative method is the most efficient (O(n) time, O(1) space).
• Memoization with arrays mirrors Python's dictionary caching, with even faster access times thanks to direct indexing.

Both approaches eliminate the exponential time complexity of naive recursion, bringing it down to linear O(n).

内容的提问来源于stack exchange，提问作者Aman Garg