algorithm - 对 Lisp 程序的算法分析的建议？

Question

Common Lisp 程序中的哪些操作被认为是足够原始的，以便计入算法分析中的单个“步骤”？现代 lisp 的实现差异有多大？

当然，小整数算术算作一个步骤，但大数字呢？考虑一下 reverse 和 nreverse 之间的区别又如何呢？具体来说，nreverse 是 reverse 的 theta 吗？那么所有的数组和序列操作呢？另外，宏是如何发挥作用的——在分析复杂性时我应该如何考虑宏？

Answer 1

• 不要试图找到统一“单步”的底层，只要知道什么是 O(1) 什么不是。
• 添加“更大的数字”(bignum s)应该是 O(log n)，其中 n 是整数中的较大者。有许多不同的乘法算法；我不是该领域的专家，这可能是特定于实现的。
• reverse 和 nreverse 都可以实现 O(n) (reverse 通过 cdr-input-and-cons-output 策略； nreverse 通过在 cdring 时交换指针)。如果我正确理解陌生术语“theta of”，那么是的。但是请注意，CL 标准不对时间复杂度做出任何保证。
• 内置序列操作通常是通过根据参数类型选择特定于数组或列表的实现来实现的，因此应该是该数据类型的普通高效算法。
• 宏只是扩展成其他代码。您可以查看它们的扩展，或者查看它们被记录为要执行的操作，或者对它们的扩展使用的算法进行有根据的猜测。宏扩展器的复杂性完全无关紧要(除非您正在使用 eval/compile，在这种情况下您还必须考虑实现编译器的复杂性)因为它在编译时运行一次；只有扩展代码很重要。