知识卡片

普通读书笔记卡 · 3595.a.2

复杂度结论必须指明输入情形

理解等级:中级

“插入排序最坏情况为 Θ(n²)”只约束各规模最慢的输入;省掉“最坏情况”而说“运行时间为 Θ(n²)”会误指所有输入,因为最好情况是 Θ(n)。

若要不分输入给出上界,可说运行时间为 O(n²)。

这张卡片看不懂?

已有反馈 · 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.