点击上方“游戏程序员聚集地”，进行关注
一夕轻雷落万丝，霁光浮瓦碧参差。
大O记法是一个判断算法好坏的一个利器,但是在某些时候,虽然大O记法表现的是一样的,但是它们的速度一个要比另一个要快的多.
本文就会介绍一种算法,虽然大O记法一样,但是速度比之前的冒泡排序算法快的多.
选择排序
上篇文章介绍过,冒泡排序的时间复杂度是O(N^2),那么先来学习选择排序的算法,然后再写出选择排序的时间复杂度.我们先来简单复习上篇文章的内容,其实对于排序算法,程序只不过做了2个操作,一个是比较,还有一个是交换.如果是2层循环嵌套,那么时间复杂度就是O(N^2).那么问题来了,时间复杂度一样,那这两个排序方式的排序步数就一样了吗?
那么先来看看选择排序,选择排序的步骤如下
- 从左到右检查数组的每个格子,声明一个变量,这个变量中国存放着最小的值的下标找出最小的那个后将变量存在这个变量中.这个变量称之为min 吧.
- 然后将最小值放在开头,再将开头的数字放在本来最小的数字的位置.这么说可能有些啰嗦,那么看下面的详细讲解.
看下面的数组
|
9 |
6 |
7 |
1 |
|---|
首先,min记录下第一个值为9的下标,指针指向第二个数字.
下标min的值:9
|
9 |
6 |
7 |
1 |
|---|
此时声明的空变量中的数字为9 ,指针指向的数字为6,那么现在就来比较这两个数字,9>6,那么空变量中的值要改为6的下标,然后指针继续下移.
下标min的值:6
|
9 |
6 |
7 |
1 |
|---|
此时空变量中的数字为6,指针的值为7,那么6<7,所以min中的值不需要改变.指针继续下移
下标min的值:1
|
9 |
6 |
7 |
1 |
|---|
这个时候,已经到了数组的最后一位了.现在比较min中的数字6,与指针指向的数字,发现6>1.那么min中的值要变成1的下标.那么在这个时候,就要将指针指向的数字放到数组的开头.那么数组的开头数字放哪呢?如果你还记得排序的2个操作,一个是比较,一个是交换.所以指针指向的1 要放在开头,而开头的数字则要放在现在1的位置.
下标min的值:1
需要交换的2个值:
|
9 |
6 |
7 |
1 |
|---|
交换之后的数组:
|
1 |
6 |
7 |
9 |
|---|
此时,第一轮的比较与交换结束,最小的值已经放在了数组的第一位,接下来要比较剩余的数字,操作都是相同的.那么用代码表示为:
1int[] array = new int[5] { 9, 8, 7, 6, 5 };
2 private void Start()
3 {
4 for (int i = 0; i < array .Length; i++) //
5 {
6 int min =i;
7 for (int j = i+1; j < array .Length ; j++)
8 {
9 if (array[min] < array[j])
10 {
11 min = j;
12 }
13 }
14 int temp = array[i];
15 array[i] = array[min];
16 array[min] = temp;
17 }
18
19 foreach (var item in array)
20 {
21 Debug.Log(item);
22 }
23}首先看到的是它是一个双循环,上文中说过,看到双循环,立马就知道这个算法的时间复杂度是O(N^2).
那么通过代码分析,看同样是O(N^2)的算法,到底谁更快呢?
那我们一句一句的代码分析.首先它不像冒泡排序那样,冒泡是一旦比较到了二者不一样大就立马交换,而选择排序不同,它是将所有的值与”假想值”比较了一遍,记录下实际最小值的下标,比较完了之后,才开始交换,也就是说,在最坏的情况下,一个长度为N的数组交换的次数是N,那么比较呢?
第一轮是N-1次
第二轮是N-2次
第三轮是N-3次
…
拿上面的数组来举例
|
第几轮 |
比较的次数 |
|---|---|
|
1 |
4 |
|
2 |
3 |
|
3 |
2 |
|
4 |
1 |
扩展开来,长度为N的数组比较的次数为:
(N-1)+(N-2)+(N-3)…+1.
再将交换的步骤加上,放到表格中做个比较
|
N个元素 |
冒泡排序 |
选择排序 |
|---|---|---|
|
5 |
20 |
14(10次比较+4次交换) |
|
10 |
90 |
54(45次比较+9次交换) |
|
20 |
380 |
199(180次比较+19次交换) |
|
40 |
1560 |
819(780次比较+39次交换) |
|
80 |
6320 |
3239(3160次比较+79次交换) |
由此可以看出,选择排序的步数远远少于冒泡排序,而且这个少,对于元素越多,表现的就越明显.
大O究竟有什么用?
但遗憾的是,他们的时间复杂度是一样的,都是O(N^2)
其实这里要说明一个概念,大O有个特性,就是”忽略常数”,如果大O不忽略常数,那么选择排序的记法大概是为O(N^2/2).
但是忽略了常数之后,不管是O(N),还是O(100N),统统都记作O(N).
那么,也许你会有疑问,既然大O不能准确的反映出算法的快慢,那么,大O还有什么值得我们去学习的呢?
首先,大O表现的是不通时间复杂度在无限数据后的好坏情况,比如O(N)一定比O(N^2)的时间发杂度低,不论是O(10000N)还是O(1000000N).总会有一个节点,过了节点之后,O(100N)的时间复杂度比O(N^2)低.具体如图:
所以,我们就会在表示时间复杂度的时候忽略常数,那么,相同的大O记法怎么去比较哪个更适合一点呢?
办法就是具体问题具体分析,大O只会比较出时间复杂度不一样的算法哪个更快,但是快也是在样本容量到达一定数量之后的一个必然.也就是说,即使你的算法中有循环嵌套,但是你也可以在循环中优化代码,减少操作,就像把冒泡排序改成选择排序一样.想想在比较耗费步数的代码块中如何调节代码直至最优.
总结
我们基本上已经掌握了大O的分析方法,现在知道大O算法在何种情况下使用,以及相同的大O算法,应该怎么去优化它.
至今为止,我们考虑的大O算法的时间复杂度都是最坏情况,那么,我们在实际编码中并不会每次都会遇到最坏情况,遇到的一般都是平均情况.下篇文章中介绍的是如何乐观的优化代码.