top 10 algorithms.doc

Top 10 Algorithms of the CenturyMetropolis Algorithm for Monte Carlo : Monte Carlo算法是一种基于统计抽样的数值计算方法，其旨在获得高自由度的数值问题和阶乘规模的组合问题的近似解。后成为Bayesian统计学的基础。由于Monte Carlo模拟结果的精度和概型的维数D无关，因此在解决高维度问题上具有很大的优越性。Krylov Subspace Iteration Methods: 运用迭代法计算出Ax=b的一系列近似解，从而有效解决大规模、稀疏的、非对称的矩阵问题。Krylov子空间由大量的应用于初始余项向量r0=b-Ax的矩阵旋转而得到（A为nn的大矩阵）。The Fortran Optimizing Complier: Fortran编译器是一种多用途的、程序性的命令式编程语言，尤其适用于数值计算与科学计算，其出现大大提高了编码效率。后来被不断改进为Fortran Fortran Fortran。Fast Fourier Transform: 快速傅里叶变换是一种计算离散傅里叶变换及其逆过程的高效算法，其将算法复杂度从O(N2)降至O(NN)，被广泛应用于数字电路和离散数据中。Simplex Method for Linear Programming: 线性规划简化算法通过建立线性模型高效地求出可行域内的最优解，被广泛应用于经济、工业领域。The Decompositional Approach to Matrix Computations: 矩阵分解法将复杂的矩阵分解为三角、对角线、正交线等特殊形式，这一方法使得软件开发者能够生成灵活、高效的矩阵簇。尽管一次分解代价昂贵，但可以被再次用来解决原矩阵的其他问题。另外，这一分解方法促进了循环错误（数值线性代数中最大的棘手问题之一）的分析。QR Algorithm for Computing Eigenvalues: QR分解特征值算法的基本思想是进行QR分解（即把矩阵写成正交矩阵与上三角矩阵的乘积，再乘以反向的因子）和迭代，从而求出矩阵特征值和特征向量。Quicksort Algorithm for Sorting:快速排序算法通过选取断点将数据元素分为比断点大的部分、断点及比断点小的部分。将此过程递归，实现数据排序。相对其他排序算法，具有很大的优越性。Integer Relation Detection: 整数关系算法是对给定的一系列实数x1，x2，xn 找出满足a1 x1+ a2 x2+anxn=0的不全为0的整数a1，a2，an。其在n=2时的特殊情况即为欧几里得算法。Fast Multipole Method: 快速多级子法起初是为了高效计算N主体之间的引力与电磁力而被发明的。它成功地将复杂度从O(N2)减小到了O(N)，且可以进行精确地误差分析。Quicksort Algorithm for Sorting快速排序算法利用分而治之的思想将一个序列分为两个子序列，其步骤如下：1.选取一个元素作为断点Pivot;2.将序列划分为比断点小的部分、断点、比断点大的部分，划分后，断点处于它最后的位置，即两个部分之间；3.递归排序比断点小的序列和比断点大的序列。递归的基本情况是只有一个元素的序列或空序列。算法程序如下：#include using namespace std;/function prototypesvoid quick_sort(int x,int first,int last);int split(int x,int first,int last);int main()int n;cin n;/input the num of arrayint *x=new int n;for (int i=0;ixi;quick_sort(x,0,n-1);for (int j=0;jn;j+)cout xj ;delete x;return 0;void quick_sort(int x,int first,int last)/first and last are the beginning and end subcripy of the subarray respectivelyif (first last)/if the array has more than one elementsint split_point;split_point = split(x,first,last);quick_sort(x,first,split_point-1);quick_sort(x,split_point+1,last);int split(int x,int first,int last)int split_point,pivot;pivot=xfirst;split_point=first;for (int i=first+1;i=last;i+)if (xipivot)/*if there are n elements less than pivot,spit_point will move left n times*/split_point+;int temp=xsplit_point;/exchange xi and xsplit_pointxsplit_point=xi;xi=temp;/exchange xfirst and xsplit_pointxfirst=xsplit_point; xsplit_point=pivot;return split_point;要使快速排序算法达到最有效果，pivot应取大小为待排序的所有元素的中间值（不是位置）的元素，但这一点不容易做到，一个简单的处理办法是取xfirst、x(first+last)/2和xlast中的中间值作为pivot。通常情况下，快速排序算法要比其他排序算法快。但是，由于快速排序采用了递归函数调用，当待排元素较少时，函数调用所需的开销将会使其效率大打折扣。因此，可以把快速排序与其他某个排序算法结合起来用，即在快速排序的递归调用中，当待排序的元素的个数小于某个值时，采用其他排序算法。改进算法程序如下：#include using namespace std;/function prototypesint split(int x,int first,int last);void quicksort(int x,int first,int last);void bubblesort(int x,int first,int last);int main()int n;cin n;/input the num of arrayint *x=new int n;for (int i=0;ixi;quicksort(x,0,n-1);for (int j=0;jn;j+)cout xj ;delete x;return 0;void quicksort(int x,int first,int last)/first and last are the beginning and end subcripy of the subarray respectivelyif (first last)/if the array has more than one elementsif (last-first10)/if the num of elements less then 10bubblesort(x,first,last);elseint split_point;split_point=split(x,first,last);quicksort(x,first,split_point-1);quicksort(x,split_point+1,last);void bubblesort(int x,int first,int last)for (int i=first+1;i=last;i+)for (int j=first;jxi)int temp=xi;xi=xj;xj=temp;int split(int x,int first,int last)int split_point=first;int pivot=xfirst;/make pivot to be the median of xfirst ,xlast, x(first+last)/2if (xfirstxlast)if (xlastx(first+last)/2)pivot=xlast;else if (xfirstx(first+last)/2)pivot=xlast;else if (xfirstx(first+last)/2)pivot=x(first+last)/2;/exchange xfirst and pivotint t=xfirst;xfirst=pivot;pivot=t;for (int i=first+1;i=last;i+)if (xipivot)/*if there are n elements less than pivot,spit_point will move left n times*/split_point+;int temp=xsplit_point;xsplit_point=xi;xi=temp;/exchange xfirst and xsplit_pointxfirst=xsplit_point;xsplit_point=pivot;return split_point;快速排序算法的复杂度分析设快速排序的时间复杂度为T(n)，对于任选的断点，有递归式T(n)= T(i)+ T(n-1-i)+3n+i；T(1)=1；T(0)=1；若取i=0，则T(n)= (3n2+5n-6)/2Best-case Time Complexity当断点正好取在数据中间，将原数列分为两个等长的子数列时，快速排序算法为最优情况，此时T(n)=2T(n/2)+7n/2；迭代得，T(n)=7 /2,即T(n)=O();Worst-case Time Complexity设快速排序的时间复杂度为T(n)，对于任选的断点，有递归式T(n)= T(i)+ T(n-1-i)+3n+i；T(1)=1；T(0)=1；若取i=0，则T(n)= (3n2+5n-6)/2；易知，当i=n-1时为最坏情况，T(n)= (2n2+2n-3)；因此，T(n)=O(n2)。相对排序的下界O()而言，快速排序算法的最坏复杂度并不算最佳。但是，在平均复杂度和数据结构，快速排序算法要优于其他算法。Average-case Time Complexity这里，我们考虑取第一个元素为初始断点的情况，并假设数列元素随机分布，则最终断点的每一种情况为基本事件，即i为随机从0(n-1)中抽取的值。则快速排序的平均复杂度T(n)满足：T(n)=1/n(T(i)+T(n-1-i)+(7n-1)/2;T(0)=T(1)=1;为计算简便，上式写为：T(n)=2/n(T(i)+cn;两边同乘以n，得nT(n)=2(i)+cn2;将n-1代入，得(n-1)T(n-1)=2T(i)+c(n-1)2;两式相减，得nT(n)-(n-1)T(n-1)=2T(n-1)+2cn-c;舍去c，得nT(n)= (n+1)T(n-1)+2cn；化简得，T(n)/(n+1)= T(n-1)/n+2c/(n+1);将n-1，n-2,n-3,，2依次代入，累加得T(n)/(n+1)=1/2+2c1/i=2c(n+1)+2cr+1/2;(r=0.577为欧拉常数)则T(n)=O()；事实上，对于任意选取断点的随机数列，快速排序算法的复杂度为O()的概率为1-n-c，随着n的增大，快排的复杂度会趋向于最优，且出现最坏的情况的概率趋向于0，因此快速排序适用于大规模元素的排序。而且，数据结构简单。Worst-case Space Complexity快速排序算法的空间复杂度根据实现方式的不同而不同。原地分割快排为O(n)（注：以上分析的均为原地分割快排），其主要分为两个部分：1. 序列划分部分；需要O(1)；2. 划分之后，对各部分分别递归排序。最坏情况下，需要进行O(n)次递归调用，因此需要O(n)空间。对于Sedgewick改进版本，元素最少的部分将被首先递归排序，至多需要O()空间。而另一部分运用尾部递归或循环排序。因此最坏情况下的空间复杂度为O()。快速排序算法的稳定性假定在待排序的记录序列中，存在多个具有相同的元素的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，xi=xj，且xi在xj之前，而在排序后的序列中，xi仍在xj之前，则称这种排序算法是稳定的；否则称为不稳定的。快速排序算法是一种不稳定的排序算法，其不稳定发生在xi与xsplit_point交换的时刻，此时可能会把原序列中元素稳定性打乱。但是若原序列中只有一组相同元素，且断点正好选为相同元素的其中一个，此时快速排序算法就是稳定的。附： 快速排序算法与其他排序算法的比较NameBestAverageWorstMemoryStableMethodOther notesInsertion sort15 !25 !25 !00 !YesInsertionAverage case is also , where d is the number of inversionsShell sort15 !23 !23 !depends on gap sequence. Best known: O(nlog2n)00 !NoInsertionBinary tree sort50 !20 !20 !15 !YesInsertionWhen using a self-balancing binary search treeCycle sort50 !25 !25 !00 !NoInsertionIn-place with theoretically optimal number of writesLibrary sort50 !20 !25 !15 !YesInsertionPatience sorting50 !50 !20 !15 !NoInsertion & SelectionFinds all the longest increasing subsequences within O(n log n)Timsort15 !20 !20 !15 !YesInsertion & Mergingcomparisons when the data is already sorted or reverse sorted.Selection sort25 !25 !25 !00 !NoSelectionIts stability depends on the implementation. Used to sort this table in Safari or other Webkit web browser.Heapsort20 !20 !20 !00 !NoSelectionSmoothsort15 !20 !20 !00 !NoSelectionAn adaptive sort - comparisons when the data is already sorted, and 0 swaps.Strand sort20 !20 !25 !15 !YesSelectionTournament sort50 !20 !20 !SelectionBubble sort15 !25 !25 !00 !YesExchangingTiny codeCocktail sort15 !25 !25 !00 !YesExchangingComb sort50 !50 !25 !00 !NoExchangingSmall code sizeGnome sort25 !25 !25 !00 !YesExchangingTiny code sizeMerge sort20 !20