Scheme中为什么是reverse O(n^2)的表现？

Question

假设我在 Scheme 中的反向函数是按以下方式编码的：

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

为什么这个程序的性能是O(n^2)？

Answer 1

好吧，考虑一下函数要做什么：

对于 zero-element 列表，它只是 returns 列表。
对于 1 元素列表，它附加零元素列表和第一个元素的反向。
对于 2 元素列表，它附加 1 元素列表的反向和第一个元素
...等等。

很明显，为了反转一个 n-element 列表，它递归地调用了自己 n 次。所以这看起来时间复杂度是O(n)，对吧？

没那么快：对于每个递归调用，它追加两个列表。所以我们需要担心append的复杂度。好吧，让我们写出最好的append：

(define (my-append l1 l2)
  (if (null? l1)
      l2
      (cons (car l1) (my-append (cdr l1) l2))))

好的，这有什么复杂性？首先，只取决于l1的长度，所以我们只需要担心：

如果 l1 是 zero-element 列出它 returns l2
如果 l2 是一个单元素列表，则将其第一个元素放在将其余元素附加到 l2
...等等

因此，要将 n-element 列表附加到其他列表，需要 n 个步骤。那么每个步骤的时间复杂度是多少？嗯，它是常数：cons 和 cdr 和 car 需要常数时间。所以append的时间复杂度就是第一个列表的长度。

所以这意味着你的反向函数的时间复杂度是

n + n-1 + n-2 + ... + 1

这样的和的值为 n(n+1)/2 是一个著名的结果（您可以通过将其写为 ((n + 1) + (n - 1 + 2) + ... (1 + n))/2 = ((n + 1) + ... (n + 1))/2 总和中有 n 项。所以复杂度为 n(n+1)，即渐近等于 n^2.

当然有reverse更好的版本。

Answer 2

更具可读性和可理解性的 O(N) reverse.....

(define (reverse lst)
  (let reverser ((lst lst)
                 (reversed '()))
    (if (null? lst)
        reversed
        (reverser (cdr lst) (cons (car lst) reversed)))))

(reverse '(1 2 3))

通过使用tail-recursive方法构建反向列表，它只需要遍历一次列表。

Scheme中为什么是reverse O(n^2)的表现？

Why is the performance of reverse O(n^2) in Scheme?

lisp

scheme

list