常数操作
评估算法的优劣指标
1.时间复杂度（流程决定）
2.额外空间复杂度（流程决定）
3.常数项时间（实现细节决定）
常数时间的操作指的是固定时间的操作
例如：
有两个int型整数的a,b相加
在Java中由于int型都占32位，所以a+b 位数一样 因此是固定时间
在数组中的寻址，在内存中是连续区间，直接根据偏移量去寻找，直接去找200万位置的数组也是常数时间
常见的常数实现操作：
•常见的算术运算 （+、-、*、/、%）
•常见的位运算（>>、>>>、<<、|、&、^等）
•赋值、比较、自增、自减操作等
•数组寻址操作
时间复杂度
在一个要计算的流程操作中，常数量位为N的话，执行完整个流程操作，用来描述我的常数量操作是个什么样的关系。
选择排序
选择算法思路
在一个整数数组中，长度为N，实现从小到大的排序操作。描述整个算法流程
arr[0~N-1]范围上，找到最小值，把最大值交换到0位置处。（1次交换）
arr[1~N-1]范围上，找到最小值，把最大值交换到1位置处。（1次交换）
arr[2~N-1]范围上，找到最小值，把最大值交换到2位置处。（1次交换）
每一步的操作都是常数级别，交换N次，通过看加比较的方式得出时间复杂度便是一个等差数列：aN^2+ bN^2+c
便得到选择排序的时间复杂度就是O(N^2)
选择排序的代码实现
public static void selectSort(int[] arr){ if(arr == null || arr.length < 2){ return; } for(int i = 0;i < arr.length -1 ;i++){ int minIndex = i; for(int j = i + 1;j < arr.length;j++){ 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; }
冒泡排序
冒泡算法思路
在arr[0～N-1]范围上：arr[0]和arr[1]，谁大谁来到1位置；arr[1]和arr[2]，谁大谁来到2位置…arr[N-2]和arr[N-1]，谁大谁来到N-1位置
在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置
在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置 …
最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置
很明显，如果arr长度为N，每一步常数操作的数量，依然如等差数列一般。所以，总的常数操作数量 =a*(N^2)+ b*N + c (a、b、c都是常数)
所以冒泡排序的时间复杂度为O(N^2)。
代码实现
public static void bobbleSort(int[] arr){ if(arr == null || arr.length < 2){ return; } for(int e = arr.length -1 ;e > 0;e--){ for(int i = 0;i < e; i ++){ if(arr[i] > arr[i+1]){ swap(arr,i,i+1) } } } } public static void swap(int[] arr,int i,int j){ arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j];
插入排序
插入算法思路
想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做。 …
想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
最后一步，想让arr[0~N-1]上有序，arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。
最差情况估计
最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般；所以，总的常数操作数量 =a*(N^2)+ b*N + c (a、b、c都是常数)
代码实现
pupublic static void insertionSort(int[] arr){ if(arr == null || arr.length < 2){ return; } for(int i = 1;i<arr.length;i++){ for(int j = i - 1;j >= 0 && a[j] > arr[j+1] ;j--){ swap(arr,j,j+1); } } } public static void swap(int[] arr,int i,int j){ arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
额外的空间复杂度
1.算法的过程，和具体的语言是无关的。
2.想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉
3.一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。
4.如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。就是常数时间,开辟空间来办事 最差情况考虑开辟空间的复杂度 注意有限几个变量这个很关键 用户要求不算
5.作为输入参数的空间，不算额外空间。程序员的自主空间;作为输出结果的空间，也不算额外空间。因为这些都是必要的、和现实目标有关的。所以都不算。
6.除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。
算法流程的常数项
当两个算法的时间复杂度一样的时候 拼常数时间 常数项
冒泡 和 插入 插入就是比冒泡快 冒泡排序就是没有插入的好 尽管时间复杂度相同
如何分析？
放弃理论分析 生成随机数直接测试
例如加操作就是没有异或快 除法操作就是没有加号快
常数操作类型是很多的 那就实际跑来估计
算法的最优解
时间复杂度尽可能低
空间复杂度小
常数时间操作在这两者之外 就比至高处项系数
时间复杂度从好到差的排名
O(1)
O(logN)
O(N)
O(N*logN)
O(N^2) O(N^3) … O(N^K)
O(2^N) O(3^N) … O(K^N)
O(N!)
对数器的认识
认识对数器：
1，你想要测的方法a
2，实现复杂度不好但是容易实现的方法b
3，实现一个随机样本产生器
4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，断点调试，改对方法a和方法b
6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
计算机0~1进行离散是有穷个的
认识二分法
只要能正确构建左右两侧的淘汰逻辑，就可以使用二分法
估计时间复杂度最差法来估计 下标换算 数组寻址 常数时间 每次砍掉一半查看
常数时间O(1) O(log2N)时间复杂度 简写为 O(logN)
- 在一个有序数组中，找>=某个数最左侧的位置
思想还是不变 二分可以实现
二分法的代码实现
public static boolean exist(int[] sortedArr, int num) { if (sortedArr == null || sortedArr.length == 0) { return false; } int L = 0; int R = sortedArr.length - 1; int mid = 0; // L..R while (L < R) { // L..R 至少两个数的时候 mid = L + ((R - L) >> 1); if (sortedArr[mid] == num) { return true; } else if (sortedArr[mid] > num) { R = mid - 1; } else { L = mid + 1; } } return sortedArr[L] == num; }
