为什么用链表实现的“埃拉托色尼筛选法”比用数组实现的运行时间更长？

Question

本人最近在重新阅读算法设计和分析基础，发现了很多之前被我忽略了的内容，其中之一就是书中所说的用链表实现埃拉托色尼筛选法比用数组实现的运行时间更长，书里没给出答案，求帮忙解惑。

Answer 1

链表涉及动态分配/回收内存和非线性的寻址，所以一般来说相同算法，都是链表慢一些。但是链表的好处是按需使用内存。