对算法进行分析（2）
IT商界
上期我们讲解了怎样分析算法的复杂性以及描述算法时间复杂性的一些基本知识。本期我们将结合具体的实例来介绍如何分析和描述算法的时间复杂性。
首先我要引入两个用来描述算法复杂性的符号：O、Ω。O用来表示在规模充分大时算法复杂性的一个上界，Ω则表示算法复杂性的一个下界。可以看出对于同一个算法而言，总有O(f(n))≥Ω(g(n))。对一个特定问题而言，如果问题本身的复杂性有一个下界Ω(g(n))，假设有一个算法，它存在一个复杂性的上界O(f(n))= Ω(g(n))，则可以认为这个算法在渐近意义上是最优的。
在我们算法演义的第一期中讲到了排序算法。排序法中最简单的就是冒泡法了。关于冒泡法的算法思想在第一讲中已有详细的讲述，这里就不再讲了。下面是冒泡法的算法实现伪码：
1 for i:=First(L) to Last(L)-1 do
2 for j:=Last(L) downto i+1 do
3 if L[j]＜L[j-1] then
4 swap(L[j],L[j-1]) //交换L[j]和L[j-1]
其中L是储存待排序元素的数组，过程swap是交换两个元素的值。
假设swap需要的时间是O(1)，所以整个循环体内部的耗时也就是O(1)。由于总循环次数为n(n-1)/2次，也就是有O(n(n-1)/2)，其中n=Last(L)-First(L)+1。对于n→∞，我们可以近似地考虑算法的复杂性就是O(n2)。另一方面，即使不需要交换位置，也就是原有的元素序列都已排序好，算法的第3行的检验也要执行n(n-1)/2次，所以算法至少需要Ω(n2)的计算时间。其实对于第4行的swap的调用依赖于第3行的检验结果，所以实际调用的次数往往要远小于n(n-1)/2。假设考虑不同的排列方式是可能性等同的，那么冒泡法实际调用swap的平均次数就是n(n-1)/4。
排序方法中还有一种叫做选择排序的。它的基本思想是对待排序的元素序列进行n-1次的处理，第i次处理是将L(i)……L(n)中的最小者与L(i)交换位置。这样，经过i次处理后，前i个元素的位置就是正确的了。下面是选择法的算法实现伪码：
1 for i:=First(L) to Last(L)-1 do
begin
2 s:=i;
3 for j:=i+1 to Last(L) do
4 if L[j]＜ L[s] then
5 s:=j; //记录L[i..n]中最小元素的位置
6 swap(L[i],L[s]); //交换L[i]，L[s]
end;
对于上面算法的第3到5行的FOR循环显然需要O(n-i)的计算时间，所以整个算法需要O(n2)的计算时间。另一方面对于任意的元素序列，其中的第4行总要被执行n(n-1)/2次，所以选择排序法至少需要Ω(n2)计算时间。选择排序算法调用swap的次数是n-1次，要比冒泡法少得多。如果当元素很大时，过程swap的用时大于其他基本运算(如元素比较)的时候，显然选择排序法要优于冒泡法。
但这两种方法都还不是最优的比较排序算法。我现在给出一个结论：对于任何一个基于比较的排序算法需要Ω(nlogn)的计算时间(这个结论的证明这里就不赘述了)。如果我们能设计一个需要O(nlogn)时间的排序算法，则在渐近意义上，这个算法就是最优的。
为了达到上面的目的，人们构思了快速排序的方法。它的基本思想是基于分治策略。对于要排序的序列进行分解、递归求解和合并的三步处理。这个算法的基本实现如下：
procedure QuickSort(p,r: integer);
var
q: integer;
begin
if p＜r then
begin
q:=Partition(p,r,L[p])
QuickSort(p,q);
QuickSort(q+1,r);
End
End;{QuickSort}
对于含有n个元素的数组L[1..n]进行快速排序只要调用QuickSort(1,n)就行。其中Partition函数是以一个确定的标准值对子序列L[p..r]进行划分。它是快速排序的关键。
Function Partition(p,r: integer; var x: anytype): integer;
Var
i,j :integer;
begin
i:=p-1;
j:=r+1;
While true do
Begin
Repeat j:=j-1 until L[j]＜=x;
Repeat i:=i+1 until L[i]＞=x;
If i＜j then swap(L[i],L[j])
Else return(j)
End
end;{Partition}
如果有感兴趣的话，可以分析一下上面的快速排序法的时间复杂度究竟是多少。