algorithm - lisp函数的空间和时间复杂度

Question

这里有两个lisp的函数

(defun fact (x &optional (acc 1))
  (if (zerop x) acc
      (fatt (- 1 x) (* x acc))))

(defun fatt (x)
  (if (zerop x) 1
      (* x (fatt (- x 1)))))

如何找到此函数的空间和时间复杂度？

Answer 1

第一个函数的(更正版本)

(defun fact (x &optional (acc 1))
  (if (zerop x) 
      acc
      (fact (- x 1) (* x acc))))

当使用 (fact N) 调用时，时间复杂度为 O(N)，因为每个递归级别的步骤相同，并且有 N 次递归调用。空间复杂度取决于编译器。

每个体面的 LISP 编译器都会进行尾递归优化，因此 fact 的递归调用被替换为“跳转”到带有参数的 fact 函数的开头被新的取代。所以你只有一组变量 x 和 acc，这意味着 O(1)。

当然，对于一个愚蠢的编译器，你最终会得到 N 个调用堆栈帧，每个调用堆栈帧都有自己的一组变量 x 和 acc，这意味着 O( N).

第二个函数

(defun fatt (x)
  (if (zerop x) 
      1
      (* x (fatt (- x 1)))))

不允许(通常 - 也许周围有一些非常聪明的编译器......)允许尾递归优化，因此，当使用 (fatt N) 调用时，你最终会得到两个时间和空间是 O(N)。

吹毛求疵:

如果您使用较大的 N 值，计算将不再适合 fixnum 数字范围，而是使用 bignums，然后违反所有递归调用执行相同步骤的假设。事实上，乘法和减法等操作的执行时间会随着数字的长度而增加。对于适合计算机内存的阶乘，它可能是 O(log(x)) 而不是每一步的 O(1)。因此对于大数，我们将观察到 O(NlogN) 而不是 O(N)。