Lisp程序算法分析的建议？

Question

7

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

肯定地说，使用小整数进行算术运算将计为一个步骤，但对于较大的数字呢？考虑`reverse`和`nreverse`之间的区别呢？具体而言，`nreverse`是否是`reverse`的theta函数？那么所有的数组和序列操作呢？此外，在分析复杂性时，宏如何发挥作用？我应该如何思考宏？

- Aoriste

1

这听起来更像是一种恐慌而不是一个问题 :-) - P Shved

哈哈 - 如果是这样的话，那不是我的本意，我今天早上开始思考这个问题，意识到我只能猜测这些事情。 - Aoriste

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kevin Reid · Accepted Answer

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