尾递归如何改变大O？

Question

尾部未优化：

(define (my-length lst)
  (cond
   [(empty? lst) 0]
   [else (+ 1 (my-length (rest lst)))]))

结果：

(my-length (list "a" "b" "c"))
= (+ 1 (my-length (list "b" "c")))
= (+ 1 (+ 1 (my-length (list "c"))))
= (+ 1 (+ 1 (+ 1 (my-length (list)))))
= (+ 1 (+ 1 (+ 1 0)))
= (+ 1 (+ 1 1))
= (+ 1 2)
= 3

尾部优化：

(define (my-length lst)
  ; local function iter:
  (define (iter lst len)
    (cond
     [(empty? lst) len]
     [else (iter (rest lst) (+ len 1))]))
  ; body of my-length calls iter:
  (iter lst 0))

结果：

(my-length (list "a" "b" "c"))
= (iter (list "a" "b" "c") 0)
= (iter (list "b" "c") 1)
= (iter (list "c") 2)
= (iter (list) 3)
3

big-O 有何改进？ Racket's docs 说第一个是 O(n) 但第二个是运行常量 space.

Answer 1

我想我现在明白了。它是关于 space (RAM) 复杂度而不是时间复杂度。

Answer 2

你是对的。尾递归实现不能保证节省 time，而是保证节省 space - 堆栈不会增长

另请注意，Racket 具有 named let 允许您更好地编写尾递归形式

(define (length xs)
  (let loop ((xs xs) (len 0))
    (if (empty? xs)
        len
        (loop (cdr xs) (+ 1 len)))))

Racket 还支持通过 match

进行模式匹配

(define (length xs)
  (let loop ((xs xs) (len 0))
    (match xs
      ((cons _ rest) (loop rest (+ 1 len)))
      (empty len))))

尾递归如何改变大O？

How does tail recursion change big O?

scheme

time-complexity

big-o

racket

tail-recursion