知识卡片

普通读书笔记卡 · 3593.a

插入排序的耗时取决于初始次序

理解等级:中级

插入排序对已排序输入,每轮只检验一次,最好情况为 Θ(n);

对逆序输入,第 i 轮须扫描此前全部 i−1 个元素,最坏情况为 Θ(n²)。

分析循环时还要计入最后一次使条件为假的测试。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 2 章 2.2 节“Analysis of insertion sort”(`OEBPS/chapter002.xhtml`,式 2.1、2.2)。 - 结论依据:原文用各行代价与执行次数展开 T(n),比较已排序和逆序输入;式 2.1、2.2 的公式图片已核对。 - 原始内容:The worst case arises when the array is in reverse sorted order—that is, it starts out in decreasing order.