Scheme中下述reversee函数实现的时间复杂度为何是O(n²)？

Great question! Let's break down both parts clearly, since they're closely linked.

1. Why can some Scheme reverse implementations have O(n²) time complexity? #

First, it's important to note that not all Scheme reverse functions are O(n²)—this only applies to naive recursive implementations that rely on the append procedure. Here's the key:

• The append function takes two lists and returns a new list with all elements of the first followed by the second. To do this, it has to traverse the entire first list to reach its end before attaching the second list. That means append has a time complexity of O(k), where k is the length of the first input list.

When a reverse implementation uses append recursively, each recursive call ends up triggering an append that processes a list of increasing length. The total number of operations adds up to a sum that scales with n², which we'll break down with your specific function next.

2. Why your reversee function is O(n²) #

Let's start by restating your code for clarity:

(define (reversee lst)
  (if (null? lst)
      '()
      (append (reversee (cdr lst)) (list (car lst)))))

Let's walk through a concrete example with a list of 4 elements: (a b c d) to see the steps:

• To reverse (a b c d), we first reverse (b c d) to get (d c b), then append that to (list a) (which is (a)). This append call has to traverse all 3 elements of (d c b) to attach (a)—that's 3 operations.
• To reverse (b c d), we reverse (c d) to get (d c), then append to (list b). This append traverses 2 elements—2 operations.
• To reverse (c d), we reverse (d) to get (d), append to (list c)—1 operation.
• Reversing (d) just returns (d) (since reversing a single element is trivial), and reversing the empty list returns ().

Adding those up: 3 + 2 + 1 = 6 operations. For a list of length n, this sum becomes 1 + 2 + ... + (n-1) = n(n-1)/2, which simplifies to O(n²) time complexity.

A faster alternative: O(n) reverse #

If you want a linear-time reverse, use a tail-recursive implementation with an accumulator. This avoids append entirely by building the reversed list incrementally with cons (which is O(1)):

(define (fast-reverse lst)
  (define (helper remaining acc)
    (if (null? remaining)
        acc
        (helper (cdr remaining) (cons (car remaining) acc))))
  (helper lst '()))

Here, each recursive step does a constant-time cons and moves to the next element, so it runs in O(n) time.

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