烟霏霏，雪霏霏。雪向梅花枝上堆，春从何处回！
之前的文章告诉你,在使用大O记法的时候,考虑的是最坏的情况,因为在一般逻辑中,最坏的情况下都考虑到了,那么还有什么情况比最坏的情况还坏呢?但是本文告诉你,只考虑到最坏的情况仍然不是最健全的做法,有时候全面分析也是十分有必要的.
插入排序
前文中已经介绍了2种算法,冒泡排序和选择排序,二者的时间复杂度都是O(N^2),但是选择排序比冒泡排序快了近一倍.也知道大O记法忽略常数的做法,看似相同的时间复杂度但是它们内部的运行步数有很大的差别.所以，你有2个相同的复杂度的算法,建议还是要深入代码块中好好看看哪里可以优化.
下面将用个新算法来说明,最坏情况之外也是值得考虑的，这个我们称之为平均情况.
插入排序的操作步骤如下:
|
8 |
4 |
2 |
3 |
|---|
在第一轮里，也就是在外循环中,
- 我们声明一个临时变量，那么这个临时变量该干什么呢？我们将索引为1的值拿出来，放在这个临时变量中.
4
|
8 |
|
2 |
3 |
|---|
然后我们将临时变量的值与它左边的值相比较。发现临时变量的值小于它左边的值，所以，本来空的地方就放这个为8的值.
4
|
|
8 |
2 |
3 |
|---|
- 然后再将临时变量中的值放在空的位置.
|
4 |
8 |
2 |
3 |
|---|
这样，就完成了第一轮的数值比较.
此后的步骤就是一直重复到数组有序为止
在代码中的表现为：
int[] number = new int[] { ,,,,,,,,};
// Use this for initialization
void Start () {
for (int i = ; i < number .Length ; i++)
{
int temp = number[i];
while (i > && (temp < number[i - ]))
{
number[i] = number[i - ];
number[i - ] = temp;
i--;
}
}
string array ="";
foreach (var item in number)
{
array += (item + " ");
}
Debug.Log(array );
}
如你所见,双循环,所以大O记法是O(N^2).
代码比较简单,就不一一解释了,或许会有人会不明白为什么在while循环中有一个i>0的判断.从上面来看,i 的值最小会等于1.那么为什么还要再判断一次呢?
注意看,在while的第一次循环结束之后,由于i–,此时的i的值就已经是为0了,那么后面的number[i-1],那么这里就是number[-1],所以这里会报一个小标越界的错误.
插人排序包含4种步骤：移除、比较、平移和插入。要分析插入算法的效率，就得把每种步骤都统计一遍。
首先看看比较。每次拿temp 跟空隙左侧的值比大小就是比较。
在数组完全逆序的最坏情况下，我们每一轮都要将temp 左侧的所有值与temp 比较。因为那些值全都大于temp，所以每一轮都要等到空隙移到最左端才能结束。
所以这个时候就会有规律了.
当第一轮的时候,我们只移动了1个数字,
当第二轮的时候,我们就移动了2个数字,
当第三轮的时候,我们就移动了3个数字,
….
当第N-1轮的时候,我们就移动了N-1个数字.
结束.
因为下标从1开始,所以不会计算到N轮.
基本上得到规律,对于长度为N的数组,大约需要(N^2)/2次的比较操作
那么还有平移的操作,考虑到最坏的情况,有多少次平移就有多少次比较就有多少次平移.所以平移和比较的步数是相同的.
如果把它们相加也就是N^2.
但是这仅仅是第一轮操作,我们一共有N-1轮,对于临时变量,会有N-1次的移除和插入.所以将这几步相加的话会得出N^2+2N+2.但是由于上文刚说过忽略常数,所以,会写成O(N^2+N).
但是!大O还有一个特性,就是只保留最高阶,也就是说最后的时间复杂度还是O(N^2).这也呼应了前文,只要是循环嵌套,时间复杂度统统都是O(N^2).
那么,你究竟有没有考虑到为什么呢?
如果N^4+N,和N+N,如果在数学函数中表示,第一个会越来越抛离第二个,所以对于低阶的,对于算法的统计并没有太大意义,也就是说低阶不会影响结果,所以,我们只要最高阶的.
从大O记法上看,插入排序的效率比选择排序的效率低,但是,我们还应该考虑一个情况,那就是平均情况.为什么呢?因为虽然考虑了最坏的情况,但是显示世界中并不会经常发生,所以考虑一下平均情况也是很有必要的.
完全降序的最坏情况之前已经见过，它每一轮都要比较和平移所遇到的值(这两种操作合计(N^2步)。对于完全升序的最好情况，因为所有值都已在其正确的位置上，所以每一轮只需要一次比较，完全不用平移。但若是随机分布的数组，你就可能要在一轮里进行比较并平移所有数据、部分数据，或无须平移。回头看看之前步骤分解的例子，可以发现在第1、3轮，我们比较并平移了所有遇到的数据。在第4轮，我们只对部分数据进行了操作。在第2轮，则没有平移，只有一次比较。
来看一些具体的例子。最好情况就像[1，2，3，4]，已经预先排好序。用同样的数据，最坏情况就是[4，3，2，1]。平均情况，则如[1，3，4，2]。
这里的最坏情况需要6次比较和6次平移，共12步。平均情况需要4次比较和2次平移，共6步。最好情况是3次比较、0次平移。
可以看到插入排序的性能在不同场景中差异很大。最坏、平均、最好情况，分别需要N2、N^2/2、N步。
再跟选择排序对比一下。选择排序是无论何种情况，最坏、平均、最好，都要12步。因为这个算法没有提早结束某一轮的机制，不管遇到什么，每一轮都得比较所选索引右边的所有值,那么哪种算法更好？选择排序还是插入排序?答案是：
看情况
对于平均情况(数组里的值随机分布），它们性能相近。如果你确信数组是大致有序的，那么插入排序比较好。如果是大致逆序，则选择排序更快。如果你无法确定数据是什么样，那就算是平均情况了，两种都可以。
总结
也许到这里,你会觉得有点迷,会觉得大O记法以及算法并不能准确的表示一个算法的好坏,毕竟大多数情况下不能一眼看出哪个算法是最合适的,其实你错了,恰恰是因为有大O记法的分析,才能具体问题具体分析,考虑多种情况来写出更合适的代码.
懂得区分最好、平均、最坏情况，是为当前场景选择最优算法以及给现有算法调优以适应环境变化的关键。记住，虽然为最坏情况做好准备十分重要，但大部分时间我们面对的是平均情况。
不能盲目的去计算最坏情况,要考虑周全,优化吃性能的代码,当然优化代码也要带着数据结构一起来优化,这也是后面的文章会讲到的.
…END…