avatar


1.时间复杂度

这一系列的笔记,我们讨论算法。

首先,到底什么是算法?
其实吧,我的个人观点,严格的说,机器学习或者深度学习的那些,或许不应该被称为算法,称之为模型更合适。但似乎现在,算法和模型两个概念已经被混在一起了,算法包括模型,模型属于算法。

总之,我们这一系列的笔记,所讨论的算法是特指不包括模型的算法。

如何衡量算法的优劣

我们所讨论的第一个问题是,如何衡量算法的优劣?
这个很简单,快和省。
什么是快?运行时间,这个是时间复杂度。
什么是省?所耗费的内存空间,这个是空间复杂度。

这一章,我们主要讨论时间复杂度。关于空间复杂度,会在我们讨论栈和递归之后,再讨论。
速度要快

常数时间操作

常数时间操作的定义

要讨论时间复杂度的话,我们又要先讨论一下常数时间操作。顾名思义,常数时间操作就是说一个操作的执行时间是常数的操作。
具体就是,如果一个操作的执行时间不因具体样本而改变,每次执行时间都是固定的时间。这样的操作就是常数时间操作。

常见的常数时间操作

  1. 算数运算:+、-、*、/、% 等。
  2. 位运算:>>、>>>、<<、|、& 等。
  3. 赋值、比较、自增、自减 等。
  4. 数组寻址操作。

时间复杂度的计算规则

现在,我们来做一件事情。
比如现在有这么一个数组:

1
[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

一共15个数字。
我们按照下图的方法进行排序,这个排序方法也被称为选择排序,因为每次选择一个最小的数字移动到前部
选择排序

第一轮

我们把从index为0的数字到index为n-1的数字进行比较,记住最小值的index。

  1. 3和44相比,3最小(比较操作一次)
    记住最小值的index(赋值操作一次)
  2. 3和38相比,3最小(比较操作一次)
    记住最小值的index(赋值操作一次)
  3. 3和5相比,3最小(比较操作一次)
    记住最小值的index(赋值操作一次)
  4. ······

最后,我们把最小值移动到前部,和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(n1)+32 * (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(n2)+32 * (n-2) + 3

那么,问,要完成整个数组的排序,我们需要多少次常数级别的操作呢?
这是一个等差数列求和。

2(n1)+(n(n1))(n1)2+3(n1)=n2+2n32 * \frac{(n-1) + (n-(n-1)) * (n-1)}{2} + 3 * (n-1) = n^2 + 2n - 3

上面这个过程有没有争议?
有!比较算一次常数时间操作,赋值算一次常数时间操作,那么,数组寻址呢?
除了这个争议呢?除了这个争议还有很多争议,互换也不是必须的吧?而且就算每次互换,也不定就是三次吧?
但是,无所谓,因为不管怎么样,最后的结果如下的形式。

an2+bn+ca n^2 + bn + c

根据高等数学中的极限,我们知道

limna1n2+b1n+c1a2n2+b2n+c2=一个不为零的常数\lim_{n \rightarrow \infty} \frac{a_1 n^2 + b_1 n + c_1}{a_2 n^2 + b_2 n + c_2} = \text{一个不为零的常数}

  • 当然,上式成立的前提条件是aa不等于00。如果aa等于00的话,都不是an2+bn+ca n^2 + bn + c这个形式。
  • 除了aa不能等于00之外,bbcc都可以等于00

在上式中,真正其决定性作用的只是n2n^2
我们只把最高阶项留下,低阶项去掉,高阶项的系数也去掉。
把刚刚排序的时间复杂度记作O(n2)O(n^2)

这就是大O时间复杂度。并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也被称为渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

那么,现在有没有争议?在上面我们一共操作的n1n-1轮,只不过是每一轮都有若干次而已。为什么不说时间复杂度是O(n)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));
// 只有数组不为空,并且数组的长度大于1,这时候的排序才有意义
if (null != arr && arr.length > 1){
arr = selectionSort(arr);
}
System.out.println(Arrays.toString(arr));
}

/**
* 选择排序
* @param arr 需要排序的数组
* @return 排序之后的数组
*/
public static int[] selectionSort(int[] arr){
// 第一轮是 from 0 to n-1
// 第二轮是 from 1 to n-1
// 第三轮是 from 2 to n-1
for (int i = 0; i < arr.length; i++) {
// 最小值的位置
int minIndex = i;
// 从第i+1个数到第n个数
for (int j = i+1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j:minIndex;
}
swap(arr,i,minIndex);
}
return arr;
}

/**
* 互换
* @param arr 数组
* @param i 需要互换的元素的index
* @param j 需要互换的元素的index
*/
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: 排序之后的数组
"""
# 遍历arr_args的index
for i in range(len(arr_args)):
# 最小index
minIndex = i
# 从第i个数到第n个数
for j in range(i + 1, len(arr_args)):
# 如果j更小
if arr_args[j] < arr_args[minIndex]:
# 更新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^2),对吗?

来,换一个数组。

1
[0,1,2,3,4,5,6,7,8,9]

只需要一轮,O(n)O(n),完成!

那么,冒泡排序的时间复杂度到底是多少?
这就涉及到了最好时间复杂度和最坏时间复杂度了。对于冒泡排序,最坏时间复杂度是O(n2)O(n^2),最好时间复杂度是O(n)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));
// 只有数组不为空,并且数组的长度大于1,这时候的排序才有意义
if (null != arr && arr.length > 1){
arr = bubbleSort(arr);
}
System.out.println(Arrays.toString(arr));
}

/**
* 冒泡排序
* @param arr
* @return
*/
public static int[] bubbleSort(int[] arr){
// 第一轮 从index为0的数字,到index为n-1的数字,进行比较,冒泡
// 第一轮 从index为0的数字,到index为n-2的数字,进行比较,冒泡
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;
}
}
// 如果已经完成了,break
if (isComplete){
break;
}
}
return arr;
}

/**
* 互换
* @param arr 数组
* @param i 需要互换的元素的index
* @param j 需要互换的元素的index
*/
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

# 如果已经完成了,break
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(n^2)。如果最好的情况也O(n2)O(n^2),那就太亏了…

小结

关于时间复杂度的两个结论:

  1. 计算时间复杂度的规则是,把整个流程拆分为一个个不可以再拆分的常数操作,只考虑最高阶。
  2. 最有参考价值的是最坏时间复杂度。一般情况下,如果没有特别说明,我们所讨论的时间复杂度都是最坏时间复杂度。
文章作者: Kaka Wan Yifan
文章链接: https://kakawanyifan.com/10601
版权声明: 本博客所有文章版权为文章作者所有,未经书面许可,任何机构和个人不得以任何形式转载、摘编或复制。

评论区