未分类

【分治策略】逆序对问题总结

数据结构与算法

一、逆序对

1. 问题背景

假如有一组电影集合，包括n部电影。某个人对这n部电影的喜欢程度各有高低，根据其喜欢程度对这n部电影进行排名，按照从1到n的方式进行标记，这就形成了一个关于电影的排名表。假设你和一个陌生人各有自己对于这n部电影的排名表。现在想要比较你跟这个陌生人的“品味”差别，看看你们俩是否有“类似”的爱好。一个很自然的办法就是对比两个人各自的排名表，看看两个排名表的排名状况是否相似。如果两张排名表上的电影顺序非常接近，就表示两个人的”品味”非常接近，反之则两个人的”品味”差距较大。

2. 问题的具体描述

给定一个序列包含n个数据{a1, a2, ..., an}，我们假设所有的数都是不相同的，我们想定义一个度量，它将告诉我们这个序列跟处于上升顺序的序列相差多远。如果a1 < a2 < ... < an，那么这个度量的值应该为0，表示与上升顺序基本一致。如果数变得更加杂乱时这个度量也就相应增大，表示与上升顺序相差较大。把这个概念量化的一种自然方式是计算序列中的逆序对的个数。逆序对的判断标准如下，当i < j且ai > aj时，这两个元素构成一个逆序对。举个例子，序列{2，4，1，3，5}中有3个逆序对(2,1)，(4,1)，(4,3)，所以该序列与上升顺序的序列之间的不相似度为3。

3. 逆序对的应用

继续考虑背景介绍中提出的问题，我们可以把任意两个人的排名表，其中一个作为上升顺序表来参考，然后计算另一个排名表中的逆序对个数。逆序对越多，则两个排名表的差别越大，说明两个人的爱好品味差别越大。逆序对如果很接近0，说明两个人的爱好品味都很接近。这种计算可以用于许多方面，比如书本、电影、餐厅等等，对用户的嗜好进行匹配，进而知道哪些用户跟哪些用户的兴趣爱好更为接近，这些计算结果可以用于许多应用软件的推荐服务。

4. 计算逆序对的算法

显然，存在一个时间复杂度为O(n^2)的暴力算法，遍历所有可能的数据对(ai, aj)，计算出其中的逆序对的个数。这种算法比较简单便不多做阐述，这里介绍的是一种更高效的算法，它的时间复杂度只有O(nlogn)。

这个算法的思想跟归并排序很是类似，也是一个分治算法。它的基本思想如下：把要统计逆序对个数的序列C沿着中间位置切分成两个子序列A和B，递归地计算子序列A和子序列B中逆序对的个数并排序，然后合并两个子序列，合并的同时计算所有(ai,aj)的数对中逆序对的个数(ai在子序列A，aj在子序列B)。这个算法的关键过程是合并计数这个环节，假设我们已经递归地排序好了这个序列的两个子序列并计算好了子序列的逆序对个数，我们要如何计算总的逆序对个数呢？由于子序列A和B是已经排好序的，在把A和B合并到C时，按照归并排序的合并过程，每次都挑选两个子序列中最小的元素加入到C中。每次A中的元素ai被加到C中，不会遇到新的逆序，因为ai小于子序列B中剩下的每个元素，并且ai出现在B中元素的前面(子序列A为原序列的前半部分)。但每次B中的元素bj被加到C中，说明它比子序列A中剩下的元素都小，由于B中所有元素本来都排在A后面，所以bj就与A中剩下的所有元素都构成逆序对，此时A中剩下的元素个数就是与bj构成的逆序对的个数。理解这个过程之后，我们就可以很容易地在合并过程中计算逆序对个数了，合并计数过程的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
mergeAndCount(A, B)
初始化count= 0，C = 空
while A和B都不为空
  令ai和bj分别为A和B中的首元素
  if ai <= bj
    把ai加入到输出表C中
    A = A - {ai}
  else
    把bj加入到输出表C中
    B = B - {bj}
    count += A中剩下的元素
  endIf
endWhile
if A 为空
  把B中剩下元素加入到C
else
  把A中剩下元素加入到C
endIf
return 合并结果C和逆序对个数count

整个合并计数过程如以上所示，理解了合并计数过程之后再来理解整个计算逆序对个数的算法就简单多了，整个算法流程的伪代码如下：

1
2
3
4
5
6
7
8
9
10
sortAndCount(C)
if L只有1个元素
  没有逆序,c1 = c2 = c3 = 0
else
  把这个表C均分成两半，A和B
  (c1, A) = sortAndCount(A)
  (c2, B) = sortAndCount(B)
  (c3, C) = mergeAndCount(A, B)
endIf
return (c1 + c2 + c3, C)

5. C++代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;

class Array {
public:
  Array(const int& size): size(size) {
    entry = new int[size];
  }
  ~Array() {
    if (entry != NULL) {
      delete [] entry;
    }
  }
  int operator[](int i) const { return entry[i%size]; }
  int& operator[](int i) { return entry[i%size]; }
  int count() {
    int* tmp = new int[size];
    int c = sortAndCount(entry, tmp, 0, size-1, true);
    delete [] tmp;
    return c;
  }
private:
  int sortAndCount(int* arr, int* tmp, int beg, int end, bool inArr) {
    if (beg < end) {
      int mid = (beg + end) / 2;
      int c1  = sortAndCount(arr, tmp, beg, mid, !inArr);
      int c2  = sortAndCount(arr, tmp, mid+1, end, !inArr);
      int c3  = 0;
      if (inArr) {
        c3 = mergeAndCount(arr, tmp, beg, mid, end);
      } else {
        c3 = mergeAndCount(tmp, arr, beg, mid, end);
      }
      return c1 + c2 + c3;
    } else {
      if (!inArr)
        tmp[beg] = arr[beg];
      return 0;
    }
  }
  int mergeAndCount(int* arr1, int* arr2, int beg, int mid, int end) {
    int i = beg, j = mid+1, k = beg, c = 0;
    while (i != mid+1 && j != end+1) {
      if (arr2[i] < arr2[j]) {
        arr1[k++] = arr2[i++];
      } else {
        arr1[k++] = arr2[j++];
        c += mid - i + 1;
      }
    }
    while (i != mid+1) arr1[k++] = arr2[i++];
    while (j != end+1) arr1[k++] = arr2[j++];
    return c;
  }
  int* entry;
  int size;
};

int main() {
  int size;
  cin >> size;
  Array arr(size);
  for (int i = 0; i < size; ++i) {
    cin >> arr[i];
  }

  cout << "逆序对个数: " << arr.count() << endl;
  return 0;
}
分享到