知识卡片
最坏情况的下界只需构造困难输入
证明算法“最坏情况”有 Ω(n²) 下界,只需对每个足够大的 n 找到至少一个耗时达到 cn² 的输入,无须证明所有输入都这么慢。
插入排序把最大的一批值置于最前面,迫使它们逐格跨越中间区,即构造了二次下界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
It does not necessarily mean that the algorithm takes at least cn2 time for all inputs.
参考来源
- 位置:《算法导论(第4版)》第 3 章 3.1 节“Example: Insertion sort”(`OEBPS/chapter003.xhtml`,图 3.1)。
- 结论依据:原文明确区分最坏情况下界与所有输入下界,构造前三分之一最大值穿越中段的输入。
- 原始内容:It does not necessarily mean that the algorithm takes at least cn 2 time for all inputs.