知识卡片
增长率可压过硬件优势
比较算法不能只看单次运行速度。
低阶常数可能让平方时间算法在小输入上更快,但输入规模增长后,n log n 与 n² 的增长率差会压过硬件和编译器优势;选择要依据目标规模与实测交叉点。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第1章 算法在计算中的作用 · 查看原书依据
Although insertion sort usually runs faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort’s advantage of lg n versus n more than compensates for the difference in constant factors. No matter how much smaller c1 is than c2, there is always a crossover point beyond which merge sort is faster.
参考来源
- 位置:《算法导论(第4版)》第 1 章《算法在计算中的作用》(源文件:`OEBPS/chapter001.xhtml`)
- 结论依据:第1章比较小输入时插入排序的常数优势与大输入时归并排序的增长率优势,并指出存在交叉规模。
- 原始内容:Although insertion sort usually runs faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort’s advantage of lg n versus n more than compensates for the difference in constant factors. No matter how much smaller c 1 is than c 2 , there is always a crossover point beyond which merge sort is faster.