知识卡片

普通读书笔记卡 · 3593.b

逆序对刻画数组失序程度

理解等级:初级

数组A的逆序对是索引iA[j]的二元组;它刻画相对目标升序的次序冲突,可用于分析插入排序移动次数。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第2章《算法入门》(OEBPS/chapter002.xhtml,文本字符[60000,65000))。 - 结论依据:问题2-4先定义 i<j 且 A[i]>A[j] 的逆序对,随后要求读者分析其与插入排序时间的关系;后者不是题干已证结论。 - 原始内容:Let A [1 : n ] be an array of n distinct numbers. If i < j and A [ i ] > A [ j ], then the pair ( i, j ) is called an inversion of A .