本文主要是介绍【数据结构】算法效率揭秘：时间与空间复杂度的较量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
在计算机科学中，时间复杂度和空间复杂度是衡量算法性能的两个重要指标。它们分别表示算法在执行过程中所需的时间和空间资源。了解这两个概念有助于我们评估和比较不同算法的优劣，从而选择更合适的算法解决问题~
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
前言
算法效率
时间复杂度
大O的渐进表示法
推导大O阶
示例1 冒泡排序
若没有优化的代码
考虑最好的情况
考虑最坏的情况
代码优化后
考虑最好的情况
示例2 二分查找
示例3 递归(一路)
示例4 递归(二路)
空间复杂度
示例1（代码与上面示例1同）冒泡排序
示例2
示例3（代码与上面示例3同）递归(一路)
算法效率
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作 空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，
时间复杂度
在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。
一个 算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。一个算 法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
// 请计算一下func1基本操作执行了多少次？
void func1(int N){int count = 0;for (int i = 0; i < N ; i++) {for (int j = 0; j < N ; j++) {count++;//n^2}}
for (int k = 0; k < 2 * N ; k++) {count++;//2n}int M = 10;while ((M--) > 0) {count++;//n}System.out.println(count);
}
实际中我们计算时间复杂度时，只需要大概执行次数，所以使用大O的渐进表示法。N代表问题的规模。
推导大O阶
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：O（N^2）
大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
有些算法的时间复杂度存在最好、平均和最坏情况：
- 最坏情况：任意输入规模的最大运行次数(上界)
- 平均情况：任意输入规模的期望运行次数
- 最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
示例1 冒泡排序
// 计算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;}}
}
若没有优化的代码
if (sorted == true) {break;考虑最好的情况
外循环end=n时，内循环要走n-1次
外循环end=n-1时，内循环要走n-2次
……
外循环end=2时，内循环要走1次
所以最好的情况总次数(n-1)+(n-2)+(n-3)+……+1=n^2/2-n/2,所以时间复杂度为O(n^2)
考虑最坏的情况
因为有两个for循环，直接n*n=n^2
代码优化后
考虑最好的情况
第一遍就是有序的，即至少要遍历一遍数据，所以时间复杂度为O（n）
示例2 二分查找
// 计算binarySearch的时间复杂度？
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;elsereturn mid;}return -1;
}
二分查找，每次去除掉一半的数据，
考虑最坏的情况：找到最后一个数字为目标数字，
有N个数据，设当折半x次找到，则N/2^x=1,得x=log2N
示例3 递归(一路)
递归的时间复杂度=递归的次数 * 每次递归后的代码的执行次数
// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;
}
这里的递归次数为N次
每次递归回来执行了三目运算符，即1次
所以时间复杂度为N*1=N,即O(N)
示例4 递归(二路)
// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
考虑最坏的情况，这里的递归次数为2^0+2^1+……+2^(N-1)=2^N-1次
每次递归回来执行了三目运算符，即1次
所以时间复杂度为2^N-1,即O(2^N)
空间复杂度
是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
示例1（代码与上面示例1同）冒泡排序
使用了常数个额外空间，所以空间复杂度为 O(1)
示例2
// 计算fibonacci的空间复杂度？
int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;
}
示例2动态开辟了N个空间，空间复杂度为 O(N)
示例3（代码与上面示例3同）递归(一路)
递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)
这篇关于【数据结构】算法效率揭秘：时间与空间复杂度的较量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
