知识卡片
复杂度结论必须指明输入情形
“插入排序最坏情况为 Θ(n²)”只约束各规模最慢的输入;省掉“最坏情况”而说“运行时间为 Θ(n²)”会误指所有输入,因为最好情况是 Θ(n)。
若要不分输入给出上界,可说运行时间为 O(n²)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
Here is what we cannot correctly say: insertion sort’s running time is Θ(n2). That is an overstatement because by omitting “worst-case” from the statement, we’re left with a blanket statement covering all cases.
参考来源
- 位置:《算法导论(第4版)》第 3 章 3.2 节“Asymptotic notation and running times”(`OEBPS/chapter003.xhtml`)。
- 结论依据:原文把最坏、最好与任意情况分别表述,并明确指出省去情形限定的 Θ(n²) 错误。
- 原始内容:Here is what we cannot correctly say: insertion sort’s running time is Θ( n 2 ). That is an overstatement because by omitting “worst-case” from the statement, we’re left with a blanket statement covering all cases.