CSCI3160 L02 · Part 2/4 逆序对计数

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L02，第 2 部分 / 共 4 部分 · 原件 L02-Divide-and-Conquer-未核.pdf（本地课件） p.7–12 定位：按原位置分半，分别统计内部和跨半逆序对，并算出递归树成本。前后：上一份 Part 1 · 下一份 Part 3

Counting Inversions

p.7 分节页。

逆序对按位置定义（p.8–9）【新】

题面（同原件 · Counting Inversions · p.8）

p.8 An inversion is a pair of (i, j) such that $1\le i<j\le n$ , and $A[i]>A[j]$ .

Example: Consider A = (10, 3, 9, 8, 2, 5, 4, 1, 7, 6). Then (1, 2) is an inversion because A[1] = 10 > A[2] = 3. So are (1, 3), (3, 4), (4, 5), and so on. There are in total 29 inversions.

Think: How many inversions can there be in the worst case?

公式按讲义重排。p.8 中“逆”是相对原位置而言，不能先把整个数组排好序再数。逐个左端点计数可核对讲义：10 贡献 9，3 贡献 2，9 贡献 7，8 贡献 6，2 贡献 1，5 贡献 2，4 贡献 1，1 贡献 0，7 贡献 1，6 贡献 0，总和 29。

最坏时数组严格降序，任意两个不同位置都构成逆序对，因此最多 $\binom n2=n(n-1)/2$ 。本例 $n=10$ ，最大可能值 45，实际 29 合理。p.9 将课堂目标定为 $O(n\log^2 n)$ ，更快的 $O(n\log n)$ 留作练习；伴读不把练习版冒充课堂算法。

两半内部加跨半区（p.10–12）

p.10 It remains to count the number of crossing inversions (i, j) where $i\in A_1$ and $j\in A_2$ .

p.10 分别递归得到左半内部数 $m_1$ 、右半内部数 $m_2$ 。所有逆序对恰分成左内部、右内部、左到右三类，三类互斥，所以答案为 $m_1+m_2+m_{cross}$ 。这里的 $i\in A_1$ 是讲义对位置所属半区的简写。

p.11 先把左半副本排序，对右半每个值 $e$ 用二分查找确定左半有多少值大于 $e$ 。本例左半排序是 [2,3,8,9,10]，右半仍是 [5,4,1,7,6]：

右半值	左半不大于它的个数	大于它的个数
5	2	3
4	2	3
1	0	5
7	2	3
6	2	3

这张表是对 p.11 原例的逐项计算。二分查找定位第一个大于 $e$ 的下标，其后整个后缀都构成跨逆序。跨半区合计 17；原左半内部 8、右半内部 4，总数 $8+4+17=29$ 。

补充：先把“位置”和“值”分开。 一个元素可以想成贴着原下标的卡片 (位置, 值)。分半只按位置；左半卡片的原下标永远小于右半卡片，所以跨半配对的“左边先出现”条件已经自动满足，剩下只需比较值。排序左半副本只是方便查询，不是把原问题换成排序后的数组。若反过来先按值分两半，就丢掉了原位置条件。

把一次二分查询展开。 仍用原例中的右值 5，在已排序左半 [2,3,8,9,10] 找第一个严格大于 5 的位置。以下下标从 0 开始，区间 [lo,hi) 表示尚未判定的元素范围；最终答案边界允许等于 hi：

检查前 lo,hi	mid 与值	为什么移动边界	检查后 lo,hi
0,5	2，值 8	8 已大于 5，第一个满足者不会在它右边	0,2
0,2	1，值 3	3 不大于 5，它及左边都不满足	2,2

此时边界是 2，后缀下标 2、3、4 有三个元素，故贡献为 $5-2=3$ 。二分过程中维持的不变量是：lo 左侧已经确认不大于目标，hi 及右侧已经确认严格大于目标；中间尚未确认的范围不断缩短。若目标小于所有左值，边界为 0，贡献是左半长度；若目标不小于最大左值，边界等于长度，贡献为 0。这两个极端不需要另写错误的越界访问。

讲义 p.8–9 假设整数互异。补充（放宽条件时）：如果输入允许重复，定义里的大于仍然是严格大于；例如 [2,2,1] 只有两个逆序对，两个 2 彼此不构成逆序。因此查询必须找第一个“大于”，不能找第一个“大于等于”。这不是更改讲义前提，而是指出实现推广时要保留哪条语义。

自测：为什么不能只统计相邻的下降？先想，再展开提示。

在原例开头 10,3,9 中，10 与 9 不相邻，但原位置先后及数值大小都满足定义。相邻下降只检查 $n-1$ 对，而题目允许所有两位置组合。

进一步核对：递归合计为什么不重复？

对任意固定逆序对，两个端点要么都在左、都在右、要么分别在两边，恰好只有一种情形成立。递归负责前两类，当前层只负责第三类；因此没有一对既算在内部又算在跨半区。空数组或单元素数组返回 0，这是递归终止且不漏边界的基础。

p.12 每层多了排序和约 $n/2$ 次二分查询，合并成本 $O(n\log n)$ ，所以

T(n)\le2T(\lceil n/2\rceil)+O(n\log n)=O(n\log^2 n).

不必离开正文也可以算出这个上界。设 $n=2^h$ ，第 j 层有 $2^j$ 个规模 $n/2^j$ 的问题，每个的当前层工作至多 $a(n/2^j)\log_2(n/2^j)$ ，故该层为 $an(h-j)$ 。各内部层求和为

an[h+(h-1)+\cdots+1]=an\frac{h(h+1)}2=O(n\log^2 n).

叶子合计 O(n)，不改变上界。原来的同文件核验见附录 A1。考试角度：（A 级：Quiz-01-2025T1-题解.pdf Q3，考两半输出、跨逆序数与合并成本变化；演练见附录 A2）。

本讲核心考点

原位置分半，分成两边内部与跨半逆序对（p.8–12；A 级：Quiz-01-2025T1 Q3）。
本讲每层排序得到双对数，T03加强返回值可去掉一个对数（p.12；C 级）。

附录

A1 逆序对的递归树求和（p.12）

设 $n=2^h$ ，第 $j$ 层有 $2^j$ 个问题，每个大小 $n/2^j$ 。若合并上界为 $am\log_2m$ ，这一层总计 $an(h-j)$ 。逐层相加：

\begin{aligned} \sum_{j=0}^{h-1}an(h-j)&=an\sum_{r=1}^{h}r\\ &=an\frac{h(h+1)}2\\ &=O(n\log^2n). \end{aligned}

叶子的常数代价合计 $O(n)$ ，不改变结果。这里的第二个对数来自“每层都有二分查询”，不是递归调用次数额外乘一次 $n$ 。

回到正文：两半内部加跨半区（p.10–12）

A2 作业/往年题演练（非讲义内容）：逆序对与变慢的合并

题面（Quiz-01-2025T1-题解.pdf · Q3(a)–(c) · p.4）

p.4 3. Consider running the “counting inversion” algorithm on the array A = (70, 28, 43, 60, 80, 12, 30, 50). Recall that the algorithm divides A into two equal halves at the middle, and recursively solves the subproblems corresponding to the two halves, respectively. Answer the following questions: (a) (10 points) What are the outputs of the two subproblems, respectively? (b) (15 points) After recursion, the algorithm will count the number of “crossing inversions.” How many crossing inversions are there in A? (c) (15 points) In the class, we used an $O(n\log n)$ -time method to count the number of crossing inversions and proved that the whole algorithm ran in $O(n\log^2n)$ time. Assume that Mr. Goofy decides to replace our $O(n\log n)$ -time method with his own method that runs in $O(n\log^2n)$ time. What is the worst-case time of the whole algorithm now? You need to explain the derivation of your answer.

公式按原题重排。(a) 左半 [70,28,43,60] 只有 70 与其余三项构成逆序，返回 3；右半 [80,12,30,50] 只有 80 与其余三项构成逆序，返回 3。

(b) 排序左半为 [28,43,60,70]。依次考察右半 80、12、30、50，大于它们的左值数量分别为 0、4、3、2，所以跨逆序 $0+4+3+2=9$ ，整体数 $3+3+9=15$ 。这个总数可以逐个左端点重新计数核验。

回到正文：两半内部加跨半区（p.10–12）

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L02-Divide-and-Conquer-未核.pdf（本地课件），本部分 p.7–12；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。