分治算法应用：逆序计数（Counting Inversions）

逆序计数问题是分治Divide and Conquer思想的经典应用它不仅能量化两个序列的相似程度还能将暴力搜索 O(n²) 的时间复杂度优化至 O (n log n)。本文从问题定义、暴力搜索、分治核心思路、算法实现到复杂度证明全方位解析逆序计数问题。一、问题定义什么是逆序对1.1 逆序对的概念给定一个序列 a1​,a2​,...,an​若存在下标对 (i,j) 满足ij 且 ai​aj​则称 (ai​,aj​) 为一个逆序对Inversion。逆序对的数量就是该序列的逆序数。简单的示例如下。序列 [2,3,1] 的逆序对为2,1、(3,1)因此逆序数为2。序列 [3,2,1] 的逆序对为(3,2)、(3,1)、(2,1)因此逆序数为3最大逆序数。1.2 问题的实际意义逆序数是衡量两个序列相似程度的重要指标典型场景电影评分排名两个用户对同一批电影的排名逆序数越小审美越相似序列有序性一个完全升序的序列逆序数为 0完全降序的序列逆序数为 Cn2​2n(n−1)​最大逆序数。二、暴力搜索最直观的方式是枚举所有下标对 (i,j)ij逐一判断是否满足 ai​aj​统计符合条件的对数。伪代码实现def count_inversions_brute(seq): n len(seq) inv_count 0 for i in range(n): for j in range(i1, n): if seq[i] seq[j]: inv_count 1 return inv_count分析两层嵌套循环枚举所有点对共执行 2n(n−1)​ 次判断时间复杂度为 O (n²)。问题当 n 达到 10⁴、10⁵量级时暴力解法会因计算量过大直接超时因此需要分治思想优化。三、分治算法逆序计数的分治算法基于归并排序MergeSort改造核心是将 “统计逆序数” 与 “归并排序” 结合在排序的同时完成逆序数统计分治过程分为三步分割Divide、求解Conquer、合并Merge。图1 对半分割以及合并统计3.1 核心思想一个序列的逆序数由三部分组成左半部分的逆序数序列前半段内部的逆序对数量记为invA​右半部分的逆序数序列后半段内部的逆序对数量记为invB​跨左右的逆序数一个元素在左半段、一个元素在右半段形成的逆序对数量记为inv​C。总逆序数totalinv​invA​invB​invC​。3.2 三步拆解设待处理序列为L长度为 n分治步骤如下步骤 1Divide将序列L从中间划分为左半段 A和右半段 B使两段长度尽可能相等相差不超过 1左半段AL[0,n/2] [a0,a1,...,am];右半段BL[n/21,n−1][b0,b1,...,bn];步骤 2Conquer统计左半段 A 的逆序数invA​和右半段 B 的逆序数invB​同时递归对 A、B 进行升序排序为合并阶段统计跨段逆序数做准备。当序列长度为1时逆序数为 0单个元素无逆序对。步骤 3Merge合并阶段的任务接收两个已排序的子序列 A、B在将其归并为一个有序序列的同时统计跨段逆序数​。由于 A、B 均为升序序列当遍历到 A 中元素aibj时A 中从i到m的所有元素都大于bj这些元素都会与bj成逆序对数量为∣A∣−a左半段剩余元素数,见图1。无需逐一比较直接批量统计将跨段逆序数的统计时间从 O (n²) 降至 O (n)。合并统计初始化指针i0指向 A 开头、j0指向 B 开头跨段逆序数invC​0结果序列OutList[]循环比较A[i]和B[j]将较小的元素加入OutList若B[j]A[i]将B[j]加入OutListj1且invC​∣A∣−i批量统计逆序对若B[j]A[i]将A[i]加入OutListi1当其中一个序列遍历完毕将另一个序列的剩余元素直接追加到OutList末尾返回跨段逆序数invC​和归并后的有序序列OutList。四、算法实现分治算法的核心是SortAndCount函数递归和MergeAndCount函数合并统计整体流程与归并排序高度一致。# 合并两个有序序列统计跨段逆序数返回(跨段逆序数, 归并后的有序序列) def MergeAndCount(A, B): a b cross_inv 0 out [] len_A, len_B len(A), len(B) while a len_A and b len_B: if A[a] B[b]: out.append(A[a]) a 1 else: out.append(B[b]) b 1 cross_inv len_A - a # 批量统计逆序对 # 追加剩余元素 out A[a:] out B[b:] return cross_inv, out # 递归统计逆序数返回(总逆序数, 排序后的序列) def SortAndCount(L): n len(L) if n 1: return 0, L # 终止条件单个元素逆序数为0 # 1. 分割划分为左右两半 mid n // 2 A, B L[:mid], L[mid:] # 2. 求解递归统计左右半段逆序数同时排序 inv_A, sorted_A SortAndCount(A) inv_B, sorted_B SortAndCount(B) # 3. 合并统计跨段逆序数 cross_inv, sorted_L MergeAndCount(sorted_A, sorted_B) # 总逆序数 左 右 跨段 total_inv inv_A inv_B cross_inv return total_inv, sorted_L # 主函数调用 def count_inversions(seq): total_inv, _ SortAndCount(seq) return total_inv五、时间复杂度5.1 递推公式建立逆序计数与归并排序的时间复杂度完全一致设处理长度为 n 的序列的时间为T(n)则分割将序列划分为两半时间 O (1)求解递归处理两个长度为 n/2 的子序列时间2∗T(n/2)合并遍历一次序列时间 O (n)递推公式为T(n)2∗T(n/2)O(n)当n1T(1) 1, 当n1;5.2 递推公式求解对于上述递推式有两种经典求解方法递归树法和代入法数学归纳法最终结果均为T(n)O(nlogn)。方法 1递归树法递推树的每一层总工作量为 O (n)根节点为 n第一层两个子节点各为 n/2总工作量 n/2 n/2 n第二层四个子节点各为 n/4总工作量仍为 n以此类推递推树的高度为log2​n每次将序列划分为两半直到长度为 1共划分log2​n次总工作量 每层工作量 × 层数 n∗log2​nO(nlogn)。方法 2代入法数学归纳法证明目标T(n)≤c∗nlognc 为常数。基例n2 时T(2)2∗T(1)O(2)O(2)而c∗2log22c≥T(2)基例成立归纳假设假设对于所有 k n有T(k)≤c∗klogk归纳步骤T(n)​≤2∗T(n/2)c∗n≤2∗c∗(n/2)log(n/2)c∗nc∗n(logn−log2)c∗nc∗nlogn−c∗nc∗nc∗nlogn​归纳成立因此T(n)O(nlogn)。5.3 总时间复杂度分治算法的总时间复杂度为O(n log n)远优于暴力解法的 O (n²)能高效处理大规模序列。六、总结逆序对是满足ij且ai​aj​的下标对逆序数可量化序列有序性和两个序列的相似程度暴力搜索枚举所有数对时间复杂度 O (n²)仅适用于小规模序列基于归并排序改造将逆序数拆分为左半段、右半段、跨段三部分在排序的同时统计逆序数时间复杂度优化至O(nlogn)合并阶段的批量统计是算法优化的核心利用有序序列的性质将跨段逆序数的统计从逐一比较改为批量计算实现O(n)合并T(n)2∗T(n/2)O(n)是经典分治递推式可通过递归树法或代入法求解结果为O(n logn)。本文的逆序计数算法是归并排序的经典改造理解其思路不仅能掌握逆序计数问题更能深入理解分治思想的核心 ——将复杂问题拆分为简单子问题再高效合并结果。