如何衡量一个算法的好坏?我们可以从时间和空间两个方面入手,也就是时间复杂度和空间复杂度。

无论是时间复杂度还是空间复杂度,都采用大O的渐进表示法。只保留最高阶项,且最高阶项的系数为1.例如一个算法的执行次数是2N^2+M+3,那么该算法的时间复杂度是O(N^2)。

时间复杂度

时间复杂度的衡量标准也就是算法的执行次数。我们下面用几段代码来练习一下算法时间复杂度的计算。

  • 冒泡排序的时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}

假设有N个元素,最坏的情况下需要走N-1趟,每趟排序end-1次。例如有5个元素,N-5,那么需要走4趟,每趟排列次数分别为4,3,2,1。刚好构成等差数列,可以用等差数列求和公式计算执行次数,也就是[(N*(N-1))]/2

按照大O的渐进表示法,时间复杂度是O(N^2)。

  • 二分查找的时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}

二份查找的好处是每次能去掉一半,第一次是去掉一半还剩一半,第二次去掉一半还剩1/4,第三次去掉一半还剩1/8……如下图所示:

image-20220604213754161

所以二分查找的时间复杂度是O(logN)

  • 递归求阶乘的时间复杂度
1
2
3
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}

递归算法的时间复杂度 = 递归的次数 * 每次递归执行的次数

递归求阶乘算法递归次数为N,每次递归执行1次,所以时间复杂度是O(N)。

  • 递归求斐波那契数列
1
2
3
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

递归次数,也就是层数为N的二叉树最多的结点个数,(2^N) - 1。

所以时间复杂度是O(2^N)。

空间复杂度

空间复杂度的衡量标准是临时占用的存储空间大小。随着计算机的发展,存储空间越来越大,空间复杂度也就不必太过关注。

  • 递归求阶乘的空间复杂度
1
2
3
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}

递归了N次,开辟了N个栈帧,每个栈帧占用常数的存储空间,所以该算法的空间复杂度是O(N)。