首先讲的就是排序问题,也就是在算法中的经典问题,在这一讲中主要讲了两个排序问题,一个是插入排序,一个是归并排序,在这里,并不是将如何去实现这个排序,而是通过这两个排序来学习渐进分析的原理以及其对应的符号。
1:排序问题
对于一个序列
InsertionSort(A,n) //对A[1,2,...n]进行排序
for j<-2 to n
do key<-A[j]
i<-j-1
while i>0 and A[i] > key
do A[i+1] <- A[i]
i<-i-1
A[i+1] = key
在使用伪代码的时候,我们不使用括号进行分界,而是使用缩进进行分界。
首先我们看一下整体的排序流程:
在排序的过程中是有一个常量的,在排序过程中保持不变,也就是前后的顺序是不变的,因为key前面的元素的前后顺序已经确定了。
我们来举个例子看一下:
8 2 4 9 3 6 //首先,我们从j=2开始,2 < 8,也就是8 > 2,所以2和8为位置调换
2 8 4 9 3 6 //接着,key = 4,8 > 4,2 < 4,所以8和4的位置调换
2 4 8 9 3 6 //接着,key = 9,8 < 9,所以位置不变
2 4 8 9 3 6 //接着,key = 3,9 > 3,9和3的位置调换,8 > 3,8和3的位置调换,4 > 3,4和3的位置调换,2 < 3,所以位置不变
2 3 4 8 9 6 //接着,key = 6,9 > 6,9和6的位置调换,8 > 6,8和6的位置调换,4 < 6,位置不变,
2 3 4 6 8 9 //这样排序就完成了。
下面我们使用工具来分析一下这个排序算法:
1:运行时间问题
对于程序的运行时间,取决于很多因素
1:取决于输入的顺序,最坏的情况下就是逆序
2:取决于输入数据的数量大小
我们在进行分析的时候,是将输入的规模参数化。
2:运行时间的上界
在我们进行算法分析的时候,经常对算法的运行时间的上界感兴趣,因为这对程序的效率比较时非常有效的,如果是运行时间下界的话,我们可能不知道该程序的最长运行时间是多少,有可能是很长很长的时间,都不好说,所以,对于一个算法的运行时间上界的分析,是非常有用的。
这里的运行时间的上界其实就是在最坏情况下程序的运行时间,在这里我们刚刚说了,当输入为逆序的时候,就是最坏情况。我们就来分析一下。
我们使用T(n)代表n个输入数据的最长运行时间。
而我们又知道,程序的运行时间和计算机的配置也是有关系的,在这里我们使用的是对相同机器上的表现。
在这里我们使用渐进分析程序的运行时间的上界。
渐进分析的意思就是忽略掉那些依赖于机器的常量,不去检查实际的运行时间,而是关注运行时间的增长。在我们进行渐进分析的时候,需要使用一些符号来理解渐进分析。
第一个需要了解的就是θ符号。
θ:写一个公式,舍弃他的低阶项,并忽略掉前面的常数因子
举个例子:
当n->无穷的时候,θ(n2)的程序总会战胜一个θ(n3)的程序,我们来看一下下面这张图片,就能印证这段话。
对于我们这个插入排血来说,我们使用内存引用计数来计算一下该算法的最坏情况下的运行时间。
在这里我们可以看出,当n比较小的时候,该算法的运行时间还是可以的,但是当n非常大的时候,该算法的运行时间是相当缓慢的。
下面我们来介绍一个更快的排序算法,叫做归并排序。
(二):归并排序
归并排序的思想就是分而治之的思想,将已有顺序的子序列进行合并,得到完全有序的序列。
在我们对A[1,2,3…N]进行归并排序的时候,通常需要三步:
1:如果n = 1,排序完成
2:递归的对A[1 到 n/2向上取整]这部分和A[n/2+1向上取整 到 n]分成两半
3:拍好顺序之后对两个表进行归并
下面我们举个例子,下面是已经排好序的两张表,我们来看一下如何归并。
20 12
13 11
7 9
2 1
两个表是竖着的。
首先比较的是1和2,其中1最小,将1输出。
1
接着,比较2和9,2最小,将2输出
1 2
接着,比较9和7,7最小,将7输出
1 2 7
再比较9和13,9最小,将9输出
1 2 7 9
再比较13和11,11最小,将11输出
1 2 7 9 11
在比较13和12,12最小,将12输出
1 2 7 9 11 12
最后只剩下一个表了,将表中的数据按顺序输出
1 2 7 9 11 12 13 20
这样,通过归并,我们就将顺序排出来了。
下面我们来分析一下这个算法。
我们通过上面的三个步骤进行分析。其中1,2,3分别代表上面的三个步骤。
1 : 第一个步骤,我们是直接进行判断 n 是否等于1,如果等于1的话,直接输出,所以这里的T(n)是一个常数,我们使用θ(1)来表示
2:第二个步骤,我们对序列进行递归分成两半,这里的时间 = 2T(n/2)
3:第三个步骤,进行归并,我们需要比较n次,所以,这里的T = θ(n)
通过这三个步骤,我们总结出一个方程:
下面为了容易分析,我们将公式总结成下面这个公式:
其中,使用cn代替θ(n)
对于递归程序,我们使用递归树的方法进行分析。
好了,根据上面的递归图,我们总结一下:
1:树的高度:lgn
2:叶子的个数:n
3:总和:cn * lgn + θ(n) = cn * lgn = θ(nlgn)
注意在求总和的时候,我们可以这样看,每一行的和都是cn,那么总和就是cn乘上数的高度,这样就得来了这个算法的复杂度 θ(nlgn)
很明显,在大规模的情况下,归并算法要优于插入排序。