算法基础——1、插入排序及算法分析

note

算法学习系列。一、算法基础——1、插入排序及算法分析

我考虑了很久,觉得很有必要从头将算法知识整理一遍,也算是《算法导论》的学习笔记。
今天先从基础的插入排序讲起。
在这篇文章中,我们将探讨插入排序和如何分析算法(关于运行时间)的问题。

插入排序

计算机的优势在于快速的计算,它还没有聪明到一眼就能将元素排序的程度,我们需要做的是设计一个能让计算机执行的可行算法,对于少量的元素进行排序。这种情况下,插入排序算法将是一个很不错的选择

  • 插入排序有点类似于打扑克时大家整理手中牌的过程,每次从桌上抽取一张牌,比对了它与之前手中已有牌的大小之后,再将它放入正确的位置。

现在考虑一个元素个数为$n(n≤20000)$的正整数集合$A$,我们需要将这个集合中的元素从小到大排序。

这里我们直接给出插入排序的伪代码

1
2
3
4
5
6
7
for j=2 to A.length
t=A[j]
p=j-1
while p>0 and A[p]>t
A[p+1]=A[p]
p=p-1
A[p+1]=t

这是C++代码完整实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
using namespace std;
int main(){
int A[20001],n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
for(int j=2;j<=n;j++){
int t=A[j];
int p=j-1;
while(p>0&&A[p]>t){
A[p+1]=A[p];
p--;
}
A[p+1]=t;
}
for(int k=1;k<=n;k++) printf("%d ",A[k]);
return 0;
}

这里我再给出那一段while语句的另一种实现思路:

1
2
3
4
5
6
7
do{
if(A[p]>t){
A[p+1]=A[p];
A[p]=t;
}
p--;
}while(p>0);
  • 不难发现,这一段while语句的思路与我们给出的伪代码并不相同,那么究竟有什么不同之处呢?我们在后面给出解答。

下面,我们举$A=\lbrace5,2,4,6,1,3\rbrace$的例子,来看一看插入排序具体是如何实现的:

process

上图表明了对$A=\lbrace5,2,4,6,1,3\rbrace$时,该算法的工作流程。
在该算法中,$j$指出当前我们摸到的牌,在while循环中,我们将$A_j$与之前的牌一一比对,找到合适的位置来插入它。
在这个图中,我们可以很好地解释两段while语句的不同:第一段while语句意识到对于摸到的第$j$张牌,之前的牌实际上都已经从小到大排序,只需找到一张比第$j$张更小的牌,将$j$放到这张牌前面即可;第二段while语句却没有意识到这一点,笨拙地从第$j-1$张对比到了第$1$张。

算法分析

算法分析主要是对其需要的运行时间进行分析。

一般来说,算法需要的时间与其输入规模同步增长,我们下面对“运行时间”和“输入规模”进行更为严谨的说明:

输入规模的最佳概念依赖于研究的问题。对于许多问题,如排序,输入规模最自然的量度是输入项数,比如,待排序数组的规模$n$。对于其它一些问题,如两个整数相乘,输入规模的最佳量度是用二进制表示输入所需的总位数。此外还有一些情况,我们不再细说。

一个算法在特定输入上的运行时间是指执行的基本操作步数。让我们暂且认为执行每行伪代码需要常量时间。我们假定第$i$行每次执行需要$c_i$的时间,其中$c_i$为常量。

(摘自《算法导论》——Charles E. Leiserson等)

下面我们将讨论插入排序运行时间的表达式,接下来的过程是由繁到简的:

第1行代码:for j=2 to A.length
运行次数:$n$

第2行代码:t=A[j]
运行次数:$n-1$

第3行代码:p=j-1
代价:$c_3$
运行次数:$n-1$

第4行代码:while p>0 and A[p]>t
运行次数: $\sum_{j=2}^nt_j$

第5行代码:A[p+1]=A[p]
运行次数: $\sum_{j=2}^n(t_j-1)$

第6行代码:p=p-1
运行次数:$\sum_{j=2}^n(t_j-1)$

第7行代码:A[p+1]=t
运行次数: $n-1$

然后我们将每行代码代价与次数之积求和,得:

$$\begin{align} T(n) & = c_1n+c_2(n-1)+c_3(n-1)+c_4\sum_{j=2}^nt_j\\ & + c_5\sum_{j=2}^n(t_j-1)+c_6\sum_{j=2}^n(t_j-1)+c_7(n-1) \end{align}$$

我们来看看极好的情况,即数组已经排好序

  • 这种情况下,对$j={2,3,…,n}$,始终有$t_j=1$,那么:

$$\begin{align} T(n) & = c_1n+c_2(n-1)+c_3(n-1) +c_4(n-1)+c_7(n-1) \\ & = (c_1+c_2+c_3+c_4+c_7)n -(c_2+c_3+c_4+c_7) \end{align}$$

  • 这种情况下,$T(n)$是关于$n$的线性函数。

我们再来看看极差的情况,即数组被反向排序

  • 这种情况下,对$j={2,3,…,n}$,始终有$t_j=j$,那么:

$$\sum_{j=2}^nj=\frac {n(n+1)}2-1$$

$$\sum_{j=2}^n(j-1)=\frac {n(n-1)}2$$

$$\begin{align} T(n) & = c_1n+c_2(n-1)+c_3(n-1)+c_4(\frac{n(n+1)}2-1)+c_5(\frac{n(n-1)}2)+c_6(\frac{n(n-1)}2)+c_6(n-1) \\ & = (\frac{c_4}2+\frac{c_5}2+\frac{c_6}2)n^2+(c_1+c_2+c_3+\frac{c_4}2-\frac{c_5}2-\frac{c_6}2+c_7)n-(c_2+c_3+c_4+c_7) \end{align}$$

  • 这种情况下,$T(n)$是关于$n$的二次函数。

  • 我们在设计算法时,往往更需要研究它的最坏情况运行时间。

接下来我们继续简化,从而探讨关于增长率(增长量级)的问题:

  • 注意到,最坏情况下(最好情况也是)$T(n)$是依赖于$c_i$的,我们现在忽略$c_i$,直接将$T(n)$表示为$an^2+bn+c$。

  • 只考虑公式中最重要的项$an^2$(因为当$n$足够大时,低阶项影响并不大)。同时,我们忽略系数$a$(常量因子不如增长率重要),现在我们只剩下了最重要的$n^2$。

  • 故而,我们记插入排序具有最坏情况运行时间$\Theta(n^2)$(在后面的文章中我们讲详细探讨$O$,$\Theta$,$\Omega$)。

  • 如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级,我们通常认为前者比后者效率更高。但需要注意的是,这样的比较对于小的输入有时并不适用,但对于足够大的输入,这是必然的。

最后更新于18-08-04
助力本站发展