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

无论是时间复杂度还是空间复杂度，都采用大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）。