有关Lisp程序算法分析的建议吗？

Question

Common Lisp程序中的哪些操作被认为是足够原始的,以便计算算法分析中的单个"步骤"？现代lisps的实施有多广泛？

当然,使用小整数的算术只算作一个步骤,但更大的数字呢？而关于考虑之间有什么区别reverse和nreverse？具体来说,是nreverseθ reverse？那么所有的数组和序列操作呢？另外,宏如何计算 - 在分析复杂性时我应该如何考虑宏？

Answer 1

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