引言

当我们平时在刷题的过程中，题目往往会要求我们在指定的时间复杂度和空间复杂度的前提下去完成，那什么是时间复杂度和空间复杂度呢？进入数据结构学习之后，我们会学习很多集合框架，每种集合框架会对应不同的使用场景，不同的集合框架的算法的时间和空间复杂度也会各有差异，所以不同算法展现出来的解决问题的效果也不尽相同，所以怎么衡量一个算法的效率呢？我们一般就会通过算法的时间复杂度和空间复杂度两个指标来量化算法的执行效率，从而面对不同的问题采用相对应的算法。

时间复杂度

概念

在计算机科学中，算法的时间复杂度是一个数学函数，在一个代码中，时间复杂度往往值得是核心代码的执行次数，通过量化执行次数来评判一个代码所花费时间的多少。

示例

在这里插入代码片void func1(int N){
	int count = 0;
	for (int i = 0; i < N ; i++) {
		for (int j = 0; j < N ; j++) {
			count++;
		}
	}
	for (int k = 0; k < 2 * N ; k++) {
		count++;
	}
	int M = 10;
	while ((M--) > 0) {
		count++;
	}
	System.out.println(count);
}

我们来计算一下这个程序基本操作执行了多少次？
其中第一次count++ 执行了n^2次（因为嵌套了两个for循环）
第二次count++执行了2n次
第三次count++执行了10次
综上，整个程序执行的总次数为：F(n) = n^2 + 2n +10
但是如何去表示整个代码的时间复杂度呢？计算机中一般用大O渐进表示法来表示时间复杂度，包括后面所要说的空间复杂度也是如此。

大O渐进表示法

如何使用大O渐近表示法呢？我们只需要记住这三个步骤，以后套用次模板即可！！！

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。

那按照这个模板算上面代码的时间复杂度是多少呢？
第一步 用常数1取代运行时间中的所有加法常数
F(n) = n^2 + 2n +1
第二步 在修改后的运行次数函数中，只保留最高阶项
F(n) = n^2
第三步 如果最高阶项存在且不是1，则去除与这个项目相乘的常数
F(n) = n^2
所以这个代码的时间复杂度用大O法表示就是O(n^2)
注意：衡量时间复杂度往往有最好，最坏和平均时间复杂度，一般都是取最坏时间复杂度。所以我们一般计算出这个代码最坏情况下的执行次数然后用大O渐进法表示即可。

常见时间复杂度计算举例

示例1

在这里插入代码片// 计算func2的时间复杂度？
void func2(int N) {
	int count = 0;
	for (int k = 0; k < 2 * N ; k++) {
		count++;
	}
	int M = 10;
	while ((M--) > 0) {
		count++;
	}
	System.out.println(count);
}

答案：O(n)

示例2

在这里插入代码片// 计算func3的时间复杂度？
void func3(int N, int M) {
	int count = 0;
	for (int k = 0; k < M; k++) {
		count++;
	}
	for (int k = 0; k < N ; k++) {
		count++;
	}
	System.out.println(count);
}

答案：O(M+N)
这里需要强调的是M和N都是未知的，计算时间复杂度的时候不能省略

示例3

在这里插入代码片// 计算bubbleSort的时间复杂度？
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;
	}
	}
}

最好时间复杂度：当数据是顺序的时候，至少需要比较一趟，发现有序，则不需要进行第二趟排序，故时间复杂度是O(N)
最坏时间复杂度：当数据是逆序的时候，每一趟都需要两两交换数据元素，总趟数为N-1，第一趟需要比较N-1次，第二趟比较N-2次……最后一趟比较1次，所以总的次数相加为等差数列，时间复杂度为O(N^2)。

递归相关题目的时间复杂度

计算递归相关题目的时间复杂度需要遵循一个核心思想：
时间复杂度 = 递归次数 * 每次递归之后执行的次数

示例1

在这里插入代码片// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {
	return N < 2 ? N : factorial(N-1) * N;
}

递归次数：当N = 1的时候停止递归，递归次数为N-1次
每次递归之后执行的次数：只是计算了一个三目运算符，次数为1次
整个代码执行次数 = N- 1 * 1 = N – 1，所以时间复杂度为O(N)。

示例2

在这里插入代码片// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {
	return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

这里我们通过画图来详细讲解

假设最后递归到1，近似把整个看成一个满二叉树（后续会进行讲解），所以总的个数就是整个代码执行的次数为一个等比数列，每次递归之后进行的也是三目运算操作（次数为1次），所以时间复杂度为O(2^n)。

空间复杂度

概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，一般指额外占用的空间。

常见空间复杂度计算举例

示例1

在这里插入代码片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;
	}
	}
}

因为强调空间复杂度是额外占用的空间，该冒泡排序所定义的额外变量都是常数个，所以冒牌排序的空间复杂度是O(1)。

示例2

在这里插入代码片long factorial(int N) {
	return N < 2 ? N : factorial(N-1) * N;
}

递归中的空间开销往往来源于递归中的压栈操作，每一次压栈都会在栈上面开辟空间
当N>=2时，函数会一直压栈，此时栈内包含N-1条数据，退栈时进行计算，所以空间复杂度为O(N)。

示例3

在这里插入代码片// 计算斐波那契递归fibonacci的空间复杂度？
int fibonacci(int N) {
	return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

答案：O(N)
这里很多人会疑惑为什么是O(N)，这里我们还是画图来讲解

这里可以看出，递归的时候会压栈，但是往回退的时候也会退栈然后进行下一次递归，所以递归的层数就是所占用的临时空间大小，故空间复杂度还是O(N)!!!