这一系列的笔记,我们讨论算法。
首先,到底什么是算法?
其实吧,我的个人观点,严格的说,机器学习或者深度学习的那些,或许不应该被称为算法,称之为模型更合适。但似乎现在,算法和模型两个概念已经被混在一起了,算法包括模型,模型属于算法。
总之,我们这一系列的笔记,所讨论的算法是特指不包括模型的算法。
如何衡量算法的优劣
我们所讨论的第一个问题是,如何衡量算法的优劣?
这个很简单,快和省。
什么是快?运行时间,这个是时间复杂度。
什么是省?所耗费的内存空间,这个是空间复杂度。
这一章,我们主要讨论时间复杂度。关于空间复杂度,会在我们讨论栈和递归之后,再讨论。
常数时间操作
常数时间操作的定义
要讨论时间复杂度的话,我们又要先讨论一下常数时间操作。顾名思义,常数时间操作就是说一个操作的执行时间是常数的操作。
具体就是,如果一个操作的执行时间不因具体样本而改变,每次执行时间都是固定的时间。这样的操作就是常数时间操作。
常见的常数时间操作
- 算数运算:+、-、*、/、% 等。
- 位运算:>>、>>>、<<、|、& 等。
- 赋值、比较、自增、自减 等。
- 数组寻址操作。
时间复杂度的计算规则
现在,我们来做一件事情。
比如现在有这么一个数组:
1
| [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
|
一共15个数字。
我们按照下图的方法进行排序,这个排序方法也被称为选择排序,因为每次选择一个最小的数字移动到前部。
第一轮
我们把从index为0的数字到index为n-1的数字进行比较,记住最小值的index。
- 3和44相比,3最小(比较操作一次)
记住最小值的index(赋值操作一次) - 3和38相比,3最小(比较操作一次)
记住最小值的index(赋值操作一次) - 3和5相比,3最小(比较操作一次)
记住最小值的index(赋值操作一次) - ······
最后,我们把最小值移动到前部,和0位置的数字进行互换。
怎么进行互换?比如,在这一轮中,我们已经知道了最小值的index是9。我们的互换操作是
1 2 3
| temp = arr[0] arr[0] = arr[9] arr[9] = temp
|
一共三次操作,完成互换。
第一轮结束,我们会得到
1
| [2,44,38,5,47,15,36,26,27,3,46,4,19,50,48]
|
这么算的话,在第一轮,我们的常数操作的次数是
2∗(n−1)+3
第二轮
我们把从index为1的数字到index为n-1的数字进行比较,并把最小的数字,移动到前部。
最后会得到
1
| [2,3,38,5,47,15,36,26,27,44,46,4,19,50,48]
|
在第二轮中,我们常数操作的次数是
2∗(n−2)+3
那么,问,要完成整个数组的排序,我们需要多少次常数级别的操作呢?
这是一个等差数列求和。
2∗2(n−1)+(n−(n−1))∗(n−1)+3∗(n−1)=n2+2n−3
上面这个过程有没有争议?
有!比较算一次常数时间操作,赋值算一次常数时间操作,那么,数组寻址呢?
除了这个争议呢?除了这个争议还有很多争议,互换也不是必须的吧?而且就算每次互换,也不定就是三次吧?
但是,无所谓,因为不管怎么样,最后的结果如下的形式。
an2+bn+c
根据高等数学中的极限,我们知道
n→∞lima2n2+b2n+c2a1n2+b1n+c1=一个不为零的常数
- 当然,上式成立的前提条件是a不等于0。如果a等于0的话,都不是an2+bn+c这个形式。
- 除了a不能等于0之外,b和c都可以等于0。
在上式中,真正其决定性作用的只是n2。
我们只把最高阶项留下,低阶项去掉,高阶项的系数也去掉。
把刚刚排序的时间复杂度记作O(n2)。
这就是大O时间复杂度。并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也被称为渐进时间复杂度(asymptotic time complexity),简称时间复杂度。
那么,现在有没有争议?在上面我们一共操作的n−1轮,只不过是每一轮都有若干次而已。为什么不说时间复杂度是O(n)呢?
这是因为每一轮都还可以继续拆分为若干次常数操作,我们一定要拆分为一个个不可以再拆分的常数操作才行。
第一个结论:计算时间复杂度的规则是,把整个流程拆分为一个个不可以再拆分的常数操作,只考虑最高阶。
我们还可以把这个选择排序算法实现。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| package ch01;
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) { int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; System.out.println(Arrays.toString(arr)); if (null != arr && arr.length > 1){ arr = selectionSort(arr); } System.out.println(Arrays.toString(arr)); }
public static int[] selectionSort(int[] arr){ for (int i = 0; i < arr.length; i++) { int minIndex = i; for (int j = i+1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j:minIndex; } swap(arr,i,minIndex); } return arr; }
public static void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
|
运行结果:
1 2
| [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
|
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| def selectionSort(arr_args): """ 选择排序 :param arr_args: 需要排序的数组 :return: 排序之后的数组 """ for i in range(len(arr_args)): minIndex = i for j in range(i + 1, len(arr_args)): if arr_args[j] < arr_args[minIndex]: minIndex = j
arr_args[i], arr_args[minIndex] = arr_args[minIndex], arr_args[i]
return arr_args
if __name__ == '__main__': arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(arr) print(selectionSort(arr))
|
运行结果:
1 2
| [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
|
最好和最坏时间复杂度
现在,我们再用一种方法进行排序,这个排序方法叫做冒泡排序,因为整个过程中,最大的数就像冒泡一样,一步一步的浮出水面。
首先
index为0的数字和index为1的数字进行比较,3和44比较,右边(index为1)的数大,不交换。
index为1的数字和index为2的数字进行比较,44和38比较,左边(index为1)的数大,交换。
得到
1
| [3,38,44,5,47,15,36,26,27,2,46,4,19,50,48]
|
index为2的数字和index为3的数字进行比较,44和5比较,左边(index为2)的的数大,交换。
最后,当我们index为i-1的数字和index为i的数字进行比较,并按条件进行交换之后,一定是最大的数在最右边。
然后我们再进行一轮,这样第二大的数会在从右往左第二个。
如此循环。最后我们的时间复杂度是O(n2),对吗?
来,换一个数组。
只需要一轮,O(n),完成!
那么,冒泡排序的时间复杂度到底是多少?
这就涉及到了最好时间复杂度和最坏时间复杂度了。对于冒泡排序,最坏时间复杂度是O(n2),最好时间复杂度是O(n)。最好时间复杂度和最坏时间复杂度对应的都是极端情况下的复杂度,那么平均情况下呢?这就是平均时间复杂度。
那么,哪个时间复杂度最有参考价值呢?
第二个结论:最有参考价值的是最坏时间复杂度
一般情况下,如果没有特别说明,我们所讨论的时间复杂度都是最坏时间复杂度。
我们还可以把冒泡排序算法实现。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| package ch01;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) { int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; System.out.println(Arrays.toString(arr)); if (null != arr && arr.length > 1){ arr = bubbleSort(arr); } System.out.println(Arrays.toString(arr)); }
public static int[] bubbleSort(int[] arr){ for (int i = 0; i < arr.length; i++) { boolean isComplete = true;
int maxIndex = arr.length - i - 1; for (int j = 0; j < maxIndex; j++) { if (arr[j] > arr[j+1]){ swap(arr,j,j+1); isComplete = false; } } if (isComplete){ break; } } return arr; }
public static void swap(int[] arr,int i,int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
|
运行结果:
1 2
| [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
|
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| def bubbleSort(arr_args): """ 冒泡排序 :param arr_args: 需要排序的数组 :return: 排序之后的数组 """ for i in range(len(arr_args)): isComplete = True maxIndex = len(arr_args) - i - 1 for j in range(maxIndex): if arr_args[j] > arr_args[j + 1]: arr_args[j], arr_args[j + 1] = arr_args[j + 1], arr_args[j] isComplete = False
if isComplete: break return arr_args
if __name__ == '__main__': arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(arr) print(bubbleSort(arr))
|
运行结果:
1 2
| [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
|
一定要有isComplete
,只有存在这个参数,才可能会有冒泡排序提前停止,否则每一次排序的时间复杂度都是O(n2)。如果最好的情况也O(n2),那就太亏了…
小结
关于时间复杂度的两个结论:
- 计算时间复杂度的规则是,把整个流程拆分为一个个不可以再拆分的常数操作,只考虑最高阶。
- 最有参考价值的是最坏时间复杂度。一般情况下,如果没有特别说明,我们所讨论的时间复杂度都是最坏时间复杂度。