从插入排序看算法时间复杂度


分析算法,首先需要规定或者明确一个输入输出模型,以下以插入排序为例开始整个分析过程;

输入:n个数的一个序列(a1,a2,…,an),记为A[1..n];
输出:输入序列的的一个排序(a1’,a2’,…,an’)

算法设计要求:
1) 原址排序输入;
2) 最多只有常数个数字存储在数组外面;
3) 算法结束后,输入数组A包含排序好的输出序列(侧面说明了要满足第一条);

接下来就是设计算法了,由于这篇文章重点是分析时间复杂度,下面直接已伪代码的形式给出插入排序算法(可试着用具体的语言实现运行)

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key 
        A[i + 1] = A[i]
        i--
    A[i + 1] = key
    // Tips:很明显上面A[1..j-1]始终是已经排序好的。

插入排序对于小规模的输入的排序,排序效率还是不错的;但对于大规模的元素来说,却效率不佳,为什么呢,相信看完算法分析过程,这个问题自然而然就有答案了。

严格说来,要分析一个算法的好坏,实际上是要来分析和衡量算法执行过程中所需的资源,这里的资源包含内存,宽带,计算机硬件资源等,也包含计算时间。随着计算机的发展,硬件资源越来廉价,我们最想度量的往往也是计算时间。而为了方便分析计算时间,所有算法分析必须建立在单处理器计算模型上,在这种计算模型中,指令一条一条按顺序执行,不用考虑并发操作的影响,当然也忽略了对计算机内存层次(比如几级缓存)的分析和影响。另外需要明确的,处理器中集成了一些基础指令,每条指令的执行时间均为常量。

基于上述计算模型的描述,我们为插入排序算法设定每条指令的常数执行时间Ci 和 每条指令的执行次数ni

                                    单条指令执行时间(常量) 执行次数
for j = 2 to A.length               c1                   n
    key = A[j]                         c2                   n-1
    i = j - 1                            c3                   n-1
    while i > 0 and A[i] > key   c4                   t2+..+tj
        A[i + 1] = A[i]                c5                   (t2-1)+..+(tj-1)
        i--                              c6                  (t2-1)+..+(tj-1)
    A[i + 1] = key                    c7                  n-1

//(t2-1)+..+(tj-1)

下面求总的计算时间:
T(n)=c1n+c2(n-1)+..+c4(t2+..+tj)+c5((t2-1)+..+(tj-1))+..+c7(n-1)

我们考虑最坏的情况(ps:算法的最坏运行时间,给出了一个算法在任何输入情况下运行时间的上界;实际上,实际操作过程中,最坏情况经常出现),即如果输入的数组已经反向排序。这种情况下,要按照递减排序好,就会导致最坏的情况发生。

基于上述排序算法最坏运行情况,不能发现,tj=j。这时可以对T(n)进一步化简,得到:

T(n)=(c4/2+c5/2+c6/2)n^2 + (c1+c2+c3+c4/2-c5/2-c6/2+c7)n - (c2+c3+c4+c7)

因为每条指令的运行时间为乘数(ci为常数),T(n)可以进一步表示为an^2+bn+c,其中a,b,c都是依赖于ci的的常数。所以T(n)是n的二次函数。

然而,通常会采用一种更加抽象的方式来分析和描述算法运行时间;

当输入逐渐增大时,常数项和低阶项对运行时间的影响比重会越来越小;到输入足够大时,我们可以忽略常数项和低阶项对运行时间的影响,只保留较高的增长量级;

对于上述插入排序算法,当我们忽略常数项和低阶项时,我们用O(n^2)来表示最坏情况下的运行时间,也就是通常说的时间复杂度。

Ps:实际分析和推导过程要复杂严谨的多,这里主要侧重对时间复杂度的基本理解和基本运用(对日常开发来说,我认为已足够了)。

日常刷票~
end~

知识共享许可协议本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
本站文章除注明转载/出处外,均为本站原创或翻译,请务必在遵守许可协议的前提下转载。
发布时间:2018-08-20 23:24:18 阅读:629 标签:算法技术