当前课程知识点：算法设计与分析 > 5 Divide and Conquer > 5.2 Counting Inversions > Counting Inversions
逆序数是线性代数中一个基本概念
有着众多的应用
我们用算法的角度来讨论如何计算逆序数
在音乐网站上
顾客根据喜爱的程度
对音乐进行评价和排序
音乐网站就可以通过
不同人对音乐的排序情况
来判别他们之间喜好的相似程度
对于相似程度
我们给出一种评价指标
比如我对n首音乐的排名为从1到n
而你的排名为a_1 a_2到a_n
我们说歌曲i和j是一对逆序
如果i 但是a_i>a_j 也就是说 在我的排序中 i排在j的前面 但是在你的排序中 i排在j的后面 比如下面的例子中 我对五首歌的排名是从1到5 而你的排序是13425 那么这里就存在着两对逆序 3和2 以及4和2 我们看到 这实际上就是线性代数中逆序数的概念 对于这个问题 我们有平凡的强力搜索算法 逐一去检查 每对数是否是逆序 总共需要进行n^2次操作 在不同的场景中 我们可以看到类似的问题 比如说在投票理论 评价队列的有序程度 google的评价函数中的敏感性分析 等等 下面我们用分治算法 来计算一个序列的逆序数 给定如下的一个序列 我们首先把它分为相等的两个序列 划分需要O(1)的时间 如果规模为n的序列计算逆序数 需要T(n)的时间 那么对每个n/2规模的问题 计算时间为T(n/2) 对这两个序列总共需要2T(n/2)的计算时间 我们把下面的序列分成2组 分别标上蓝 绿两种颜色 蓝色和绿色部分的逆序数分别为5和8 关键问题是 如何把这两部分的结果 合并为原序列中的结果 除了它们各自的逆序 我们还需要 计算蓝色和绿色部分之间逆序的关系 实际上这里有9对蓝绿的逆序关系 那么总共的逆序数就是5+8+9=22 分治算法大多包含分 治 合三步操作 其中“和”的操作是关键 往往需要我们精心的设计和细致的分析 下面我们来看一下 如何计算蓝绿两部分之间的逆序 我们假设每一部分都是排好序的 然后我们来计算 来自不同部分的逆序关系 同时我们也把这两个有序的部分 合并为一个有序的整体 我们通过一个例子来演示一下 绿色部分 第一个元素为2 小于蓝色部分的最小元素3 因此 它和蓝色部分的6个元素 都是逆序关系 我们对于元素2 标记对应的蓝绿逆序数为6 把2放到新序列中的第一个 然后向后扫描 绿色部分的第二个元素11 蓝色部分从左到右进行扫描 前三个元素小于11 第四个元素为14 大于11 因此 11这个元素对应的蓝绿逆序有3个 相应的逆序数为3 绿色部分的下一个元素是16 对于蓝色部分 我们只需要从刚才到达的14 开始向右进行扫描 我们可以得到 有两个元素大于16 所以16对应的逆序数为2 继续操作 对于绿色部分的后两个元素 和蓝色部分都不存在逆序关系 所以总共我们可以看到 蓝绿的逆序数为6+3+2+2=13 在算法执行过程中 我们可以控制两个指针 分别指向绿色和蓝色的第一个元素 在算法执行过程中 每次有一个指针向后移动一格 总共需要进行的操作次数为O（n）的 所以对于一个规模为n的序列 计算它的逆序数 所需要操作的次数 T(n)≤T(n/2取下整)+T(n/2取上整) 再加上分与合的操作需要O(n)的时间 同之前的并归排序算法相同的分析 可以得到T(n)=O(nlogn) 下面来看一下算法的伪代码 算法中序列A和B都是排好序的 最后输出的序列L也是排好序的 我们先来看边界条件 如果L中只有一个元素 那么就返回逆序数为零 以及序列L 否则把L分为A,B 2个序列 分别递归调用算法 得到其逆序数为r_A,r_B 并对两个序列进行排序 然后调用上边所提到的合并算法 把A,B合成一个有序序列L’ 并且计算两部分之间的逆序数r_AB 最后整个序列的逆序数为r_A+r_B+r_AB L’是排好序的序列
-1.1 Introduction
-1.2 A First Problem: Stable Matching
--A First Problem: Stable Matching
-1.3 Gale-Shapley Algorithm
-1.4 Understanding Gale-Shapley Algorithm
--Understanding Gale-Shapley Algorithm
-Homework1
-Lecture note 1
--Lecture note 1 Introduction of Algorithm
-2.1 Computational Tractability
-2.2 Asymptotic Order of Growth
-2.3 A Survey of Common Running Times
--A Survey of Common Running Times
-Homework2
-Lecture note 2
--Lecture note 2 Basics of Algorithm Analysis
-3.1 Basic Definitions and Applications
--Basic Definitions and Applications
-3.2 Graph Traversal
-3.3 Testing Bipartiteness
-3.4 Connectivity in Directed Graphs
--Connectivity in Directed Graphs
-3.5 DAG and Topological Ordering
--DAG and Topological Ordering
-Homework3
-Lecture note 3
-4.1 Coin Changing
-4.2 Interval Scheduling
-4.3 Interval Partitioning
-4.4 Scheduling to Minimize Lateness
--Scheduling to Minimize Lateness
-4.5 Optimal Caching
-4.6 Shortest Paths in a Graph
-4.7 Minimum Spanning Tree
-4.8 Correctness of Algorithms
-4.9 Clustering
-Homework4
-Lecture note 4
--Lecture note 4 Greedy Algorithms
-5.1 Mergesort
-5.2 Counting Inversions
-5.3 Closest Pair of Points
-5.4 Integer Multiplication
-5.5 Matrix Multiplication
--Video
-5.6 Convolution and FFT
-5.7 FFT
--FFT
-5.8 Inverse DFT
-Homework5
-Lecture note 5
--Lecture note 5 Divide and Conquer
-6.1 Weighted Interval Scheduling
--Weighted Interval Scheduling
-6.2 Segmented Least Squares
-6.3 Knapsack Problem
-6.4 RNA Secondary Structure
-6.5 Sequence Alignment
-6.6 Shortest Paths
-Homework6
-Lecture note 6
--Lecture note 6 Dynamic Programming
-7.1 Flows and Cuts
-7.2 Minimum Cut and Maximum Flow
--Minimum Cut and Maximum Flow
-7.3 Ford-Fulkerson Algorithm
-7.4 Choosing Good Augmenting Paths
--Choosing Good Augmenting Paths
-7.5 Bipartite Matching
-Homework7
-Lecture note 7
-8.1 Polynomial-Time Reductions
-8.2 Basic Reduction Strategies I
--Basic Reduction Strategies I
-8.3 Basic Reduction Strategies II
--Basic Reduction Strategies II
-8.4 Definition of NP
-8.5 Problems in NP
-8.6 NP-Completeness
-8.7 Sequencing Problems
-8.8 Numerical Problems
-8.9 co-NP and the Asymmetry of NP
--co-NP and the Asymmetry of NP
-Homework8
-Lecture note 8
--Lecture note 8 NP and Computational Intractability
-9.1 Load Balancing
-9.2 Center Selection
-9.3 The Pricing Method: Vertex Cover
--The Pricing Method: Vertex Cover
-9.4 LP Rounding: Vertex Cover
-9.5 Knapsack Problem
-Homework9
-Lecture note 9
--Lecture note 9 Approximation Algorithms
-10.1 Landscape of an Optimization Problem
--Landscape of an Optimization Problem
-10.2 Maximum Cut
-10.3 Nash Equilibria
-10.4 Price of Stability
-Homework10
-Lecture note 10
--Lecture note 10 Local Search
-11.1 Contention Resolution
-11.2 Linearity of Expectation
-11.3 MAX 3-SAT
-11.4 Chernoff Bounds
-Homework11
-Lecture note 11
--Lecture note 11 Randomized Algorithms
-Exam
