isOriginal | category | tag | date | |
---|---|---|---|---|
true |
数据结构与算法 |
|
2022-05-12 |
所谓算法,其实就是我们用来操作数据、解决程序问题的一组方法。针对同一个问题,我们可以采用不同的算法,然后实现相同的结果。但是针对不同的算法,对于时间和资源的消耗却有不同的差别。而为了分析不同算法的效率,我们常常从 时间 和 空间 两个方面来对比,然后从中挑出最适合我们的解决方案。
本文主要从时间复杂度和空间复杂度的定义说起,然后介绍常见的时间复杂度和空间复杂度,最后则是对常见排序算法进行了总结。
若存在函数
- 若运行时间是常数量级,则用常数 1 表示;
-
只保留时间函数中最高阶项,如
$O(n^2 + 4n)$ ,保留最高阶项后,成为$O(n^2)$ ; -
若最高阶项存在,则省去最高阶项前的系数,如
$O(4n^2)$ ,省去最高阶项的系数后,成为$O(n^2)$ ;
总结起来,对于如何分析一段代码的时间复杂度,主要有如下 3 个实用方法:
- 只关注循环执行次数最多的一行代码;
- 加法原则:总复杂度等于量度最大的那段代码的复杂度;
- 乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积;
即无论执行多少行,都不会影响到其他区域,此时代码的复杂度就是
void sayHello(String name){
System.out.prinln("Hello, " + String);
System.out.prinln("欢迎关注我的公众号:【村雨遥】");
}
如下列二分查找代码中,通过 while
循环,能够成倍的缩减搜索范围,假设需要 x
次才能跳出循环,则有 num * 2 * 2 * ... = n
,其中 num
是常数,有 n
个 2 相乘,则有
int binarySearch(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){
int middle = left + (left - right) / 2;
if(arr[middle] == target){
return middle;
}else if(arr[middle] > target){
right = middle - 1;
}else {
left = middle + 1;
}
}
return -1;
}
如下面这段代码中,for
循环中的代码被执行了 arr.length
次,因此所需要的时间和数组长度成正比的,因此可以用
int sum(int[] arr){
int total = 0;
for(int i = 0; i < arr.length; i++){
total += arr[i];
}
return total;
}
如果我们将一个复杂度为
void hello (int n){
for( int i = 1 ; i < n ; i++){
int m = 1;
while( m < n ){
m *= 2;
}
}
}
假设我们将时间复杂度为
void selectionSort(int[] arr, int n){
for(int i = 0; i < n; i++){
int min = i;
for(int j = i + 1; j < n; j++){
if(arr[j] < arr[min]){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
和
void demo(int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
System.out.print("Hello, World");
}
System.out.print("------");
}
System.out.print("******");
}
}
虽然理论上存在时间复杂度为
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度(即除开原始序列大小的内存,在算法过程中用到的额外的存储空间),反映的对内存占用的趋势,而不是具体内存,也叫作 渐进空间复杂度 ,表示算法的存储空间与数据规模间的增长关系,用
算法执行所需临时空间不随某一变量 n
的大小而变化,则该算法空间复杂度为一个常量,表示为
int num1 = 1;
int num2 = 2;
int total = num1 + num2;
数组占用内存大小为 n
,而且后续未分配新的空间,因此该算法空间复杂度为
int[] arr = new int[n];
二维数组的情况;
int[][] arr = new int[n][n];
对于面试中常见的的排序算法,以下总结给出了其时间复杂度以及空间复杂度,以及算法稳定性。
排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
插入排序 | 稳定 | ||||
希尔排序 | 不稳定 | ||||
选择排序 | 不稳定 | ||||
堆排序 | 不稳定 | ||||
冒泡排序 | 稳定 | ||||
快速排序 | 不稳定 | ||||
归并排序 | 稳定 | ||||
计数排序 | 稳定 | ||||
桶排序 | 稳定 | ||||
基数排序 | 稳定 |
好了,以上就是今天文章的内容了。主要介绍了时间复杂度的定义、推导原则以及常见时间复杂度,还对空间复杂度定义以及常见空间复杂度进行了介绍,最后则是总结了常见排序算法的时间复杂度和空间复杂度。如果觉得文章对你有所帮助,那就点个赞再走吧!