音乐网站试图将你的听歌喜好与其他人相匹配：
你的排前n的歌音乐网站从数据库中找到与你有相似品味的人相似性度量（similarity metric）：两个排列间的逆序的数量
我的排名：1，2，...，n.你的排名：.如果i < j，但 ，歌i和j是逆序 ABCDEMe12345You13425
列出每一对 i<j 并计数逆序的数量。c++实现：
/*************************************************************** 暴力求解(Brute Force): 列出每一对i<j并计数逆序，返回逆序对数量。 复杂度：O(n^2) ****************************************************************/ int CI_BF(vector<int>& v) { int r = 0; int sz = v.size(); for(int i = 0; i < sz; ++i) for(int j = i + 1; j < sz; ++j) if(v[i] > v[j]) ++r; return r; }在归并排序的基础上加了计数逆序 。c++实现：
/**************************************************************** 分而治之（Divide-and-Conquer） : 在归并排序的基础上加了计数逆序 复杂度：O（nlogn） 备注：向量区间是左闭右开，即[lo,hi) *****************************************************************/ int MergeAndCount(vector<int>& v, int lo, int mi, int hi) { int r = 0; vector<int> v1(v.begin()+lo,v.begin()+mi); int sz = v1.size(); int j = 0; //v1的索引 while(j < sz && mi < hi){ if(v1[j] <= v[mi]){ v[lo++] = v1[j++]; } else{ v[lo++] = v[mi++]; r += (sz - j); //计数 } } while(j < sz){ v[lo++] = v1[j++]; } while(mi < hi){ v[lo++] = v[mi++]; } return r; } int SortAndCount(vector<int>& v, int lo, int hi) { if(hi - lo < 2) return 0; //递归基：单个元素自然有序，且逆序对为0 int mi = (lo + hi) / 2; int r1 = SortAndCount(v,lo,mi); int r2 = SortAndCount(v,mi,hi); int rm = MergeAndCount(v,lo,mi,hi); return r1+r2+rm; } int CI_DC(vector<int>& v) { return SortAndCount(v,0,v.size()); }
Then
，for all
定义：向量是向量和向量的卷积。（这是数字信号处理中的主要问题。）
直接使用定义公式求解。c++实现：
/*************************************************************** 暴力求解(Brute Force): 按定义直接求解。 复杂度：O(n^2) ****************************************************************/ void PM_BF(vector<int>& A, vector<int>& B, vector<int>& C) { int n = A.size(); int m = B.size(); C.clear(); C.assign(n+m-1,0); for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ C[i+j] += A[i] * B[j]; } } return; }假定n为2的幂
同理，定义，
输入规模为n的原始问题被分为输入规模为n/2的4个子问题。
c++实现：
/******************************************************************************************************** 分而治之（Divide-and-Conquer） 第一种: 将两个多项式都分为两块，将整个问题分为四个子问题分别解决 复杂度：O（n^2） 备注：假定n为2的幂 *********************************************************************************************************/ void PM_DC_1_Recur(vector<int>& A, int la, int ha, vector<int>& B, int lb, int hb, vector<int>& C) { int n = ha - la; //n为2的幂 int h = n/2; C.clear(); C.assign(2*n-1,0); if(n == 1){ //递归基 C[0] = A[la] * B[lb]; return; } vector<int> U,V,W,Z; PM_DC_1_Recur(A,la,la+h,B,lb,lb+h,U); PM_DC_1_Recur(A,la,la+h,B,lb+h,hb,V); PM_DC_1_Recur(A,la+h,ha,B,lb,lb+h,W); PM_DC_1_Recur(A,la+h,ha,B,lb+h,hb,Z); for(int i = 0; i < n-1; ++i){ C[i] += U[i]; C[i+h] += V[i] + W[i]; C[i+n] += Z[i]; } return; } void PM_DC_1(vector<int>& A, vector<int>& B, vector<int>& C) { PM_DC_1_Recur(A,0,A.size(),B,0,B.size(),C); return; }事实上。我们只需三项：
且，我们只需三次多项式乘法就可以得到前述三项：
可得
c++实现：
/********************************************************************************************************** 分而治之（Divide-and-Conquer） 第二种: 将两个多项式都分为两块，将整个问题分为三个子问题分别解决 复杂度：O（n^log3） 备注：假定n为2的幂 ***********************************************************************************************************/ void PM_DC_2_Recur(vector<int>& A, int la, int ha, vector<int>& B, int lb, int hb, vector<int>& C) { int n = ha - la; //n为2的幂 int h = n/2; C.clear(); C.assign(2*n-1,0); if(n == 1){ //递归基 C[0] = A[la] * B[lb]; return; } vector<int> U,Z,Y; PM_DC_2_Recur(A,la,la+h,B,lb,lb+h,U); PM_DC_2_Recur(A,la+h,ha,B,lb+h,hb,Z); vector<int> A1(h,0); vector<int> B1(h,0); for(int i = la,j = 0; j < h; ++i,++j){ A1[j] = (A[i] + A[i+h]); B1[j] = (B[i] + B[i+h]); } PM_DC_2_Recur(A1,0,h,B1,0,h,Y); for(int i = 0; i < n-1; ++i){ C[i] += U[i]; C[i+h] += Y[i] - U[i] - Z[i]; C[i+n] += Z[i]; } return; } void PM_DC_2(vector<int>& A, vector<int>& B, vector<int>& C) { PM_DC_2_Recur(A,0,A.size(),B,0,B.size(),C); return; }分而治之的方法并不总是最好的解决方法。（第一种分而治之算法与暴力求解方法时间复杂度相同）
事实上，有O(nlogn)的解决多项式乘积的办法。（使用了傅里叶变换FFT）
在大整数乘法中也使用了三个乘法代替四个乘法的想法。（这个想法同样是经典的Strassen矩阵乘法算法的基础）
