基于列表实现的Python斐波那契代码的时间与空间复杂度确认及解释

First, let's start with a typical version of the code you're describing (aligning with the behavior you outlined):

def fibonacci(n):
    if n <= 0:
        return "Please enter a positive integer"
    # Initialize with the first two Fibonacci numbers
    fib_sequence = [0, 1]
    # Append new values until we reach the nth term
    for i in range(2, n):
        next_num = fib_sequence[i-1] + fib_sequence[i-2]
        fib_sequence.append(next_num)
    # Return the nth term
    return fib_sequence[-1]

Time Complexity: O(n) (Your Guess Was Correct!) #

Let's break this down clearly:

• append() Amortized O(1): You’re right that append() runs in amortized constant time. Python lists pre-allocate extra space to avoid resizing with every addition. When the list hits its capacity limit, it doubles its size (a one-time O(k) cost where k is the current length), but this happens so rarely that the average cost per append() stays O(1).
• Loop Execution: The loop runs roughly n-2 times (for n >= 2). Each iteration includes:
  • Accessing list elements (fib_sequence[i-1], fib_sequence[i-2]): List index access is always O(1) in Python.
  • Adding two integers: A constant-time operation, O(1).
  • Calling append(): Amortized O(1), as explained.
• Total Cost: Adding up all these constant-time operations across ~n iterations gives an overall time complexity of O(n). This is far more efficient than naive recursive Fibonacci implementations, which have a brutal O(2^n) time cost.

Space Complexity: O(n) #

Your approach stores every Fibonacci number up to the nth term in the fib_sequence list. For input n, the list will hold n elements (assuming n >= 2). Each integer takes a fixed amount of memory, so total space scales linearly with n—hence O(n) space complexity.

Why This Isn't the Optimal Approach (Space-wise) #

While your code has solid time complexity, we can drastically optimize space usage. Instead of storing the entire sequence, we only need to track the last two numbers to compute the next one. Here's an optimized version:

def fibonacci_optimized(n):
    if n <= 0:
        return "Please enter a positive integer"
    elif n == 1:
        return 0
    # Only track the last two terms
    prev_prev, prev = 0, 1
    for _ in range(2, n):
        current = prev_prev + prev
        prev_prev, prev = prev, current
    return prev

This optimized version still runs in O(n) time (same as your list approach) but cuts space complexity to O(1)—constant space, since we only use a fixed number of variables no matter how large n gets.

Keep experimenting with different implementations and analyzing their complexity—it’s the best way to solidify your grasp of Big O notation!

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