数据结构：时间复杂度和空间复杂度
我们知道代码和代码之间算法的不同，一定影响了代码的执行效率，那么我们该如何评判算法的好坏呢？这就涉及到了我们算法效率的分析了。
📖一、算法效率
所谓算法效率的分析分为两种：第一种时间效率，又称时间复杂度。第二种空间效率，又称空间复杂度。其中，时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。
📖二、时间复杂度
🐬1、概念
算法的时间复杂度其实是一个数学函数，它描述了该算法的运行时间，然而实际上，我们并不能准确的，将一个算法所耗费的时间算出来，只有在机器上跑起来，才能够得到，但是一段代码可能有多个算法，难道我们要每个都上机器上跑吗？这显然是不现实的，因此我们在这种情况下就得到了时间复杂度的分析方式：一个算法所花费的时间与其中语句的执行次数成正比例，因此我们将算法中的基本操作的执行次数，为算法的时间复杂度，并且我们将时间复杂度的表示方法称为大O的渐进表示法 。
🐬2、大O的渐进表示法
我们将大O符号作为用于描述函数渐进行为的数学符号表示形式为：O(?)
?: 算法中的基本操作的执行次数
现在我们了解了大O的渐进表示法的使用，那么我们接下来看一下这段代码
public class Test{
public static void main(String[] args) {
int count = 0;
for (int i = 0; i < n; i++) {
count++;
}
System.out.println(count);
}
}我们可以明确发现算法中的基本操作的执行次数为n次，那么我们的时间复杂度就为O(n)。
再来看下面这段代码
public class Test{
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);
}
public static void main(String[] args) {
}
}我们可以发现第一个for循环的执行一次第二个for循环就执行N次，因此上面一共执行了N*N=N^2次，中间的for循环，显然是执行了2N次，而最后的while循环，由于M=10，因此执行了10次，那么这段代码的总体执行次数为(N^2+2N+10)次，那么我们的时间复杂度就是O(N^2+2N+10)次吗？
其实不是的，这时其实又涉及到了另一个方法：推导大O阶方法 。
🐬3、推导大O阶方法
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
那么我们还是以上面的代码为例，我们的执行次数为N^2+2N+10，根据规则用常数1，取代所有常数：N^2+2N+1，在修改后的运行次数函数中，只保留最高阶项：N^2,如果最高阶项存在且不是1，则去除与这个项目相乘的常数:(N^2)/1 = N^2。
最后根据这个规则我们就得到了最终的时间复杂度为：O(N^2)。
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执想次数。因此我们在实际中一般情况关注的是算法的最坏运行情况.
🐬4、常见的时间复杂度
| 阶 | 术语 |
| O(1) | 常数阶 |
| O(N) | 线性阶 |
| O(N^2) | 平方阶 |
| O(logN) | 对数阶 |
| O(NlogN) | NlogN阶 |
| O(N^3) | 立方阶 |
| O(2^N) | 指数阶 |
从上往下时间复杂度不断增大 。
🐬5、实例
好了现在我们已经成功的了解了什么是时间复杂度和时间复杂度的表示方法了，接下来我能一起看几道经典例子。
📌（1）执行次数明确
void func(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
}
System.out.println(count);在这段代码中我们明确的可以发现我们的算法基本操作的执行次数为100次，根据规则我们要用常数1取代所有常数，因此我们这段代码的时间复杂度应为O(1)。 而在这里我们其实也得出了一个结论，只有执行次数明确，我们就可以说这段算法的时间复杂度为O(1)（注意：并不是说整体代码的时间复杂度，只是单指这段算法）。
📌（2）冒泡排序
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，对于一些初学者来说， 一个for循环执行一次另一个for循环执行N-1次，我们N=5为例4+3+2+1+0=10，最后为O(1)这显然是没有问题的，但是当他等于N时我们用这种方法显然是没有办法计算的,然而我们知道，算法中的基本操作的执行次数，为算法的时间复杂度，那么这段代码的基本操作是什么呢？，显而易见，就是两个数的交换，那么我们就知道了其实他的交换次数就是我们的执行次数。
其中我们根据他的交换次数得出的规律发现他是一个以1为公差的等差数列，因此利用等差数列求和公式就能得出他的总次数，最后根据规则得到他的时间复杂度为O(N^2) 。
📌（3）二分查找
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;
}二分查找又称折半查找，原理是先取中间数，将中间数与我们要找的数进行比较，如果不是在进行折半，知道找到，这题我们其实可以将他看成一个纸条，我们要找一段纸条的长度，如果我们先将他这半一次，就得到了这是最好的情况时间复杂度就为O(1),但是如果我们要找X次才能找到，那么O(X)，才是我们的时间复杂度，那么X等于什么呢？我们可以想象找一次纸条就要折半，如果一次找到那么乘于一次2就等于他的长度，X次找到就是乘于X个2即2^X=N。那么
logN在算法分析中表示是 底数为2，对数为N，因此时间复杂度为O(logN)。
📌（4）递归
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}我们来看这段代码，我们发现他是一段递归，而对于他的时间复杂度，我们先把N看成是1，当N=1时，我们执行次数为1，当N=2时，执行次数为2,当N=3时，执行次数为3，因此当这段代码为N时，我们总体的执行次数应为N，所以我们的时间复杂度为O(N)。
📖三、空间复杂度
🐬1、概念
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度计算规则基
本跟时间复杂度类似，也使用大O渐进表示法。
📌（1）
他的临时空间变量， 就是三个临时变量，所以空间复杂度为O(1)。
📌（2）
他的临时空间变量为n+1，所以空间复杂度为O(n)。
📌（3）
根据上面所学N为几就会执行几次，同样也会开辟几个临时空间，因此他的临时空间变量为N，所以空间复杂度为O(N)。
好的今天我们要分享的就到这里了，我们下一篇在见！