知识卡片
逆序对刻画数组失序程度
数组A的逆序对是索引iA[j]的二元组;它刻画相对目标升序的次序冲突,可用于分析插入排序移动次数。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 算法入门 · 查看原书依据
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.
参考来源
- 位置:《算法导论(第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 .