评估算法的核心指标
1 时间复杂度
2 空间复杂度
空间复杂度就是算法解决一个问题时额外占用的内存空间是多大
时间复杂度就是算法解决一个问题时数据量和运行时间的关系
一般我们评判算法的优劣首先考虑的就是时间复杂度。
时间复杂度
什么是常数时间操作？
执行时间固定的就是常数时间操作，和样本量大小没有关系
例如:
1+1和 43241234+4123151235 的执行时间是固定的
常见的常数时间操作
算术运算：+, -, *, /, %
位运算：>>, >>>, <<, |, &, ^
赋值、比较、自增、自减
数组寻址操作
时间复杂度怎么估算？
-
充分理解算法流程
-
拆分算法流程：拆分出来的行为都是常数时间的操作
-
找到数据量和常数操作的关系是什么，建立表达式
-
完成表达式建立后，只取最高阶，低阶向都去掉，低阶的系数也去掉
记为：O(忽略系数的高阶项)
为什么用big O？
看了一圈大家都比较赞同的是big O 好写，而Θ ，Ω 键盘上没有
常见时间复杂度从好到差
O(1) 常数时间
O(logN)
O(N)
O(N*logN)
O(N^2)...O(N^K)
O(2N)...O(KN) 递归
O(N!) 最差
选择排序的时间复杂度估算
一个数组arr，有N个数，对arr进行选择排序
实现思路：
arr[0...N-1]范围上，找到最小值所在的位置，把最小值交换到0位置
arr[1...N-1]范围上，找到最小值所在的位置，把最小值交换到1位置
arr[2...N-1]范围上，找到最小值所在的位置，把最小值交换到2位置
...
arr[N-1..N-1]范围上，找到最小值所在的位置，把最小值交换到N-1位置
代码：
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1 找到最小值，在哪，放到0位置上
// 1 ~ n-1 找到最小值，在哪，放到1 位置上
// 2 ~ n-1 找到最小值，在哪，放到2 位置上
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
1 分解算法流程
看一个错误的分解步骤：
第一步：0到N-1，最小值放0位置
第二步：1到N-1，最小值放1位置
。。。
第N步：N-1到N-1，最小值放N-1位置
没有分解到底，这样计算不出时间复杂度是多少
正确的分解步骤：
将每一步分解到常数时间
第一步：
1）0到N-1遍历：
1.1） N个数遍历是：N次，
1.2）找最小值需要比较：N-1次
遍历和比较的数量是 N
2）最小值放0位置交换：1次
第二步：
1）1到N-1遍历：遍历和比较数量是N
1.1） N-1个数遍历是：N-1次，
1.2）找最小值需要比较：N-2次
2）最小值放1位置交换：1次
遍历和比较的数量是 N-1
。。。
第N步：
1）N-1到N-1遍历
1.1） 1个数看一遍是：1次，
1.2）找最小值需要比较：0次
2）最小值放N-1位置交换：0次
遍历和比较的数量是 1
2 建立表大式并估算时间复杂度
这里的时间复杂度有两部分组成：遍历和比较的时间复杂度 + 交换的时间复杂度
1 遍历和比较的时间复杂度
遍历和比较是变化的：N, N-1, N-2....1 成等差数列
已知等差数列求和公式：aN^2+bN+c (a,b,c常数项)，
时间复杂度是：O(N^2)
2 交换的时间复杂度
交换的总次数是N次
时间复杂度是：O(N)
3 总的时间复杂度：
时间复杂度是：O(N^2) + O(N)
4 最终时间复杂度：
只取最高阶
时间复杂度是：O(N^2)
时间复杂度的意义？
为什么只要最高阶忽略常数项
时间复杂度的用法是，数据量逼近无穷大时，数据量和运行时间的关系，低阶项是什么不重要，系数是什么不是最重要的，真正重要的是最高阶。
例如：
当两个算法 O(N^3) 和 O(N^2) 完成同样功能，实现细节不一样
数据量很大时， O(N^3), O(N^2) 他们的常数项，低阶项都不重要了，O(N^3)肯定比O(N^2)的时间复杂度好
时间复杂度一样时怎么判断算法优劣？
看常数项时间
例如：an^2 + bn+ c
a,b,c都是常数项
空间复杂度
空间复杂度估算其实是额外空间复杂度的估算。
额外空间是在处理流程时，需要新开辟的空间。
输入参数和输出结果的空间不算额外空间，这些都是必要的和实现目标有关的都不算。
但是如果流程需要额外开辟空间才能继续执行，这部分空间就是额外空间。
开辟有限几个变量的额外空间就是O(1)
例如：
int fun(int[] arr){
int a;
}
返回值int和入参arr不算是额外空间
要执行这个fun函数需要开辟的空间才是额外空间：int a;
额外空间O(1)
标签：arr,遍历,int,简介,复杂度,算法,最小值,时间 From： https://www.cnblogs.com/etangyushan/p/17679188.html