插入排序的效率问题

插入排序包含4 种步骤:移除、比较、平移和插入。

要分析插入算法的效率,就得把每种步骤都统计一遍。


首先看看比较。

每次拿temp_value 跟空隙左侧的值比大小就是比较。
在数组完全逆序的最坏情况下, 我们每一轮都要将temp_value 左侧的所有值与temp_value 比较。因为那些值全都大于temp_value,所以每一轮都要等到空隙移到最左端才
能结束。
在第一轮,temp_value 为索引1 的值,由于temp_value 左侧只有一个值,所以最多进行一次比较。

到了第二轮,最多进行两次比较,以此类推。

到最后一轮时,就要拿temp_value 以外的所有值与其进行比较。

换言之,如果数组有N 个元素,则最后一轮中最多进行N - 1 次比较。
因而可以得出比较的总次数为:
1 + 2 + 3 + … + N -1 次。
对于有5 个元素的数组,最多需要:
1 + 2 + 3 + 4 = 10 次比较。
对于有10 个元素的数组,最多需要:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 次比较。
(对于有20 个元素的数组,最多需要190 次比较,以此类推。)

由此可发现一个规律:对于有N 个元素的数组,大约需要N2/ 2 次比较(102/ 2 是50,202/ 2是200)。


接下来看看其他几种步骤。
我们每次将值右移一格,就是平移操作。当数组完全逆序时,有多少次比较就要多少次平移,因为每次比较的结果都会使你将值右移。

把最坏情况下的比较步数和平移步数相加。
N2/ 2 次比较+ N2/ 2 次平移=N2


temp_value 的移除跟插入在每一轮里都会各发生一次。因为总是有N -1 轮,所以可以得出结论:有N- 1 次移除和N -1 次插入。把它们都相加。
N2比较和平移的合计
+ N -1 次移除
+ N -1 次插入
=
N2 + 2N-2 步
我们已经知道大O 有一条重要规则——忽略常数,于是你可能会将其简化成O(N2+N)。
不过,现在来学习一下大O 的另一条重要规则:

换句话说,如果有个算法需要N4 + N3 + N2 + N 步,我们就只会关注其中的N4,即以O(N4)来表示。为什么呢?

插入排序的效率问题

 

随着N 的变大,N4 的增长越来越抛离其他阶。当N 为1000 时,N4 就比N3 大了1000 倍。因此,我们只关心最高阶的N。

所以在插入排序的例子中,O(N2 + N)还得进一步简化成O(N2)。

在最坏的情况里,插入排序的时间复杂度跟冒泡排序、选择排序一样,都是O(N2)。

 

上一篇:SysUtils.StrLComp、SysUtils.StrLIComp


下一篇:数字图像处理基础之--像素间的关系(邻接/连通)