一、认识复杂度
1.评估算法优劣的核心指标：
时间复杂度：当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉，记为O（去掉系数的高阶项）；
时间复杂度是衡量算法流程的复杂度的一种指标，该指标只与数据量有关，与过程之外的优化无关
常见的时间复杂度（从好到坏）
O(1)
O(logN)
O(N)
O(N+logN)
O(N2),O(N3)....O（N^K）
O(2^N) O(#N)...O(KN)
O(N!)
空间复杂度
常数项时间
说明：如何确定算法流程的总操作数与样本数量之间的表达式关系？
（1）想象该算法流程所处理的数据状况，要按照最差情况来
（2）把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作
（3）如果数据量为N，看看基本动作的数量和N是什么关系
2.通过排序，实现时间复杂度的估算
2.1 选择排序
- 基本思想
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 实现逻辑
① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
③ 依次类推下去……
//将数组中的数从下到大排序
public static void selectionSort(int[] arr){
//如果数值中只有一个数，返回
if(arr == null || arr.lenght<2){
return;
}
//遍历数组按从小到大排序
for(int i=0;i<arr.length-1;i++){
//最小值的位置索引
int minIndex=i;
for(int j=i+1;j<arr.length;j++){
mindex=arr[j]<arr[minIndex]?j:minIndex;
}
//交换两个数的位置
swap(arr,i,minindex);
}
}
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];
}
- 复杂度分析
平均时间复杂度：O(N^2)
最佳时间复杂度：O(N^2)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：不稳定
2.2 冒泡排序
- 基本思想
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
- 算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较 。
//将数组中的数从下到大排序
public static void selectionSort(int[] arr){
//如果数值中只有一个数，返回
if(arr == null || arr.lenght<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];
}
2.3插入排序
- 基本思想
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
//将数组中的数从下到大排序
public static void selectionSort(int[] arr){
//如果数值中只有一个数，返回
if(arr == null || arr.lenght<2){
return;
}
//0~0是有序的
//0~i 变成有序
for(int i=0;i<arr.length-1;i++){
//最小值的位置索引
//arr[i]与arr[i-1],arr[i-2]...比较，如果小就往前交换，一直交换到合适的位置停止
for(int j=i-1;j>=0 && arr[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];
}
3、额外空间复杂度
你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。
作为输入参数的空间,不算额外空间。
作为输出结果的空间, 也不算额外空间。
因为这些都是必要的、和现实目标有关的。所以都不算。
但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空
间就是额外空间。
如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。
4、算法流程的常数项
我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的。难道同样时间复杂度的流程，在实际运行时候就一样的好吗?
当然不是。
时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。
补充说明：一个问题的最优解是什么意思？
一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。
一般说起最优解都是忽略掉常数项这个因素的,因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。
二、认识对数器
1，你想要测的方法a
2，实现复杂度不好但是容易实现的方法b3，实现一个随机样本产生器
4、把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a和方法b
6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
案例说明：产生一个随机数组
public static int[] generateRandomArray(int maxSize,int maxValue){
//Math.random():返回[0,1)范围一个随机小数
int[] arr=new int[(int)((maxSize+1)*Math.random())];
for(int i=0;i<arr.length;i++){
//进行减法是为了可以生成负数
arr[i]=(int)((maxValue+1)*Math.random())-(int)((maxValue+1)*Math.random())
}
return arr;
}
三、认识二分法
1)在一个有序数组中，找某个数是否存在
2）在一个有序数组中，找>=某个数最左侧的位置
3）在一个有序数组中，在<=某个数最右侧 的位置
- 局部最小值问题
1.有序数组使用二分法
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;//中间位置索引
while(L<R){
mid=L+((R-L)>>1);//等价于mid=(L+R)/2
if(sorteArr[mid]==num){
return ture
}else if(sottArr[mid]>num){
R=mid-1;
}else{
L=mid+1;
}
return sortArr[L]==num;
}
}
2.无序数组且相邻不等使用二分法
public static int getLessIndex(int[] arr){
//判断数组是否为空
if(arr==null || arr.length==0){
return -1;
}
//判断是否只有一个数据，或者有两个数据，但arr[0]<arr[1]
if(arr.length==1 || arr[0]<arr[1]){
return 0;
}
//判断最后一个是否是小的
if(arr[arr.length-1]<arr[arr.length-2]){
return arr.length-1;
}
int left=1;
int right=arr.length-2;
int mid=0;
while(left<right){
mid=(left+right)/2;
if(arr[mid]>arr[mid-1]){
right=mid-1;
}else if(arr[mid]>arr[mid+1]){
left=mid+1;
}else{
return mid;
}
}
return left;
}
四、认识异或运算
1.异或运算：相同为0，不同为1
同或运算：相同为1，不同为0
2.异或运算的性质
- 0^N=N N^N=0
- 异或运算满足交换律与结合律
举例：如何取出一个整型数最右侧的1（以二进制为例）
比如一个整数N:001101010000
则需要输出： 000000010000
方法：N&((~N)+1)（即N与N的取反加1进行与运算）
原理：
N: 001101010000
~N: 110010101111
~N+1: 110010110000
N&((~N)+1):000000010000
说明：上述例子可应用于多种算法中，如以下例题
给一个整数数组arr，有两个不同的数出现了奇数次，找出这两个数
//假设出现奇数次的数为a,b
public static void printOddTImesNum2(int[] arr){
for eor=0;
for(int i =0;i<arr.length;i++){
eor ^=arr[i];//此时eor的值为a^b的值
//eor=a^b
//且eor !=0
//所以eor（二进制）必然有一个位置上是1
//为了确定这个位置，我们考虑找出最右侧的1的位置p
//保留位置p的数的值
int rightOne=eor & (~eor+1);
//找出最右侧的1的位置p 后，我们将数组分为两类，
//一类是位置p上为1的，一类是位置p上不为1的
//选择其中一类进行异或运算eor1 ^=arr[i]可得出a或b其中一个数
//则另一个数进行eor1 ^eor 可得出
int onlyOne=0;//eor1
for(int i=0;i<arr.length:i++){
//找到位置p上是1 的那一类数
if((arr[i] & rightOne) !=0){
onlyOne ^=arr[i];
}
}
System.out.println(onlyOne+" "+(eor^onlyOne));
}
}