求逆序数的分治算法

浅浅的花香味﹌ 2022-07-12 02:19 172阅读 0赞

给我们一个序列, 让我们求其逆序数:

如3 2 1 4

逆序数为: 2+1+0+0=3

我们这样定义一个序列的逆序数: 序列a1 a2 a3 a2 ...an

这个序列的逆序数C, 等于a1,a2...的逆序数的和.即 C=sum(Ci)

Ci为满足ai > aj (j > i)的数的总的个数, 即Ci = sum(ai > aj) (j >i).

我们一般写的算法一般会做N(N-1)/2次比较, 时间复杂度为: O(N^2).

下面采用的分而治之的思想来改进:

假设我们将序列a1 a2 a3 a2 ...an分成两份: B0=(a1 a2 an/2) B1 = (a (n/2+1)...an)

那么C=C(B0)+C(B1)+M(B0B1)

如果我们直接去计算M(B0B1), f(n) = 2\*f(n/2)+c\*n^2, 计算出来的结果是f(n)=n\*f(1) + 2c\*n^2 - 2c\*n, 那么效率依然是O(N^2), 我们通过什么方式改进呢?

那假如让B0,B1有序就好了! 嗯,对的. 我们在归并排序的过程先将B0,B1排成有序数列,再来求B0′B1′的逆序数, 这时求M(B0′B1′)效率就是O(N).

即,C=C(B0′) + C(B1′) + M(B0′B1′).

下面给出求C(B0′B1′)的代码, 你在下面的完整的求逆序数的算法中也可以找到:

int i = x, j = m; //序列B0\[x,y\], B1\[m, n\] for(i = x; i <= y; ++i) \{ while(j <= n && arr\[i\] > arr\[j\]) ++j; nOrder += j-m; \}

这时f(n) = 2\*f(n/2)+c\*n, 我计算出来的结果是f(n) = n\*f(1) + c\*n\*log(n)

时间复杂度O(N\*logN)和空间复杂度O(N)都和归并算法一致, 只比比归并算法大了一个常数因子.

欢迎抛砖.

\#include <iostream> \#include <algorithm> using namespace std; void swap(int \*arr, int i, int j) \{ int tmp = arr\[i\]; arr\[i\] = arr\[j\]; arr\[j\] = tmp; \} int merge(int\* temp, int \*arr, int x, int y, int m, int n) \{ int nOrder = 0; int i = x, j = m; for(i = x; i <= y; ++i) \{ while(j <= n && arr\[i\] > arr\[j\]) ++j; nOrder += j-m; \} int k = 0; i = x, j = m; while(i <= y && j <= n) \{ if(arr\[i\] <= arr\[j\]) temp\[k++\] = arr\[i++\]; else temp\[k++\] = arr\[j++\]; \} while(i <= y) temp\[k++\] = arr\[i++\]; while(j <= n) temp\[k++\] = arr\[j++\]; return nOrder; \} int inversion\_number(int \*arr, int i, int j) \{ if(i < j) \{ int mid = i+((j-i)>>1); int v1 = inversion\_number(arr, i, mid); int v2 = inversion\_number(arr, mid+1, j); int temp\[10\]; int nValue = merge(temp, arr, i, mid, mid+1, j); memcpy(arr+i, temp, sizeof(int)\*(j-i+1)); return v1+v2+nValue; \} else return 0; \} int main() \{ int arr\[\] = \{5,3,3,3,3,3,3,3,3,3\}; cout << inversion\_number(arr, 0, 9) << endl; return 0; \}