lisp - 如何生成一系列 Pell 数而不是 Lisp 中的特定数

Question

如何使用 cons 或其他方式打印 Pell numbers 的列表直到第 N 个数？

(defun pellse (k)
   (if (or (zerop k) (= k 1))
       k
   (+ (* 2 (pellse (- k 1)))
      (pellse (- k 2)))))
 (print (pellse 7))

Answer 1

以下是如何以一种不会呈指数增长的方式做到这一点:

(defun pells (n)
  (loop repeat n
    for current = 0 then next
    and next = 1 then (+ (* 2 next) current)
    collect current))

给定前两个元素，计算第 n 个元素的时间复杂度为 O(log(P_n)) 其中 P_n 为第n个佩尔数；您需要 log(P_n) 位的答案和 log(P_n) 操作的加法。我们实际上不需要计算出 P_n 是什么:它是由一个简单的线性递推关系定义的，所以解必须是指数的，所以 log(P _n) = O(n)。因此计算第一个 n 佩尔数的复杂度是 O(n*n) = O(n² ).

不能^[*] 比 O(n²) 做得更好，因为必须写 O( n²) 位来表示所有这些数字。

^[*] 虽然我非常怀疑这一点，但从理论上讲，它可能通过某种方式共享数据以某种更紧凑的方式表示列表。