时间复杂度
算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。时间复杂度常用O（读作big O）来表示，不包括这个函数的低阶项和首项（高阶项）的系数。
来思考一个问题：
有一个有序数组A,以及另一个无序数组B,请打印出B中的所有不在A中的数。
对于这个问题可以使用以下几种思路解决：
思路一：对于B中的每一个数都通过遍历数组A来判断
public class Solution{
public static void printMethod1(int[] arrA,int[] arrB){
for(int i = 0;i<arrB.length;i++){
for(int j = 0;j<arrA.length;j++){
if(arrA[j] == arrB[i])
break;
if(j == arrA.length-1 && arrA[j] != arrB[i])
System.out.println(arrB[i]);
}
}
}
}
在遍历嵌套的内部，进行了数组的寻址，以及比较等操作，这样的操作是一个常数时间的操作，常数操作的时间复杂度记作：O(1)。对于printMethod1方法，执行算法的时间和数组A及数组B的样本量有关，假设A中有N个数，B中有M个数，两层for循环实际上就是将数组A和数组B遍历一遍。那么该算法的时间复杂度为(M×N)O(1) ，可以表示为O(M×N)。
思路二：对于B中的每一个数，都在A中通过二分查找判断
public class Solution{
public static void printMethod2(int[] arrA,int[] arrB){
for(int i = 0;i<arrB.length;i++){
if(!bSearch(arrA,0,arrA.length-1,arrB[i]))
System.out.println(arrB[i]);
}
}
public static boolean bSearch(int []arr,int L,int R,int target){
if(L < R){
int mid = L + ((R-L)>>1) ;
if(target == arr[mid]){
return true;
}else if(target < arr[mid]){
return bSearch(arr,L,mid-1,target);
}else{
return bSearch(arr,mid+1,R,target);
}
}else if(L == R){
return arr[L]==target?true:false;
}else{
return false;
}
}
}
第二种算法，可以分解为两个过程，第一个过程是对数组B遍历的过程，第二个过程是对数组A二分搜索的过程，其他的比较两个数，数组寻址等操作都可以记作O(1)。二分搜索同一棵完全二叉树一样，其时间复杂度和二叉树的高度有关为为O(logN),对数组B遍历的时间复杂度为O(M),也就是说共需要M次O(logN)的时间复杂度，为O(M logN)。
思路三：对数组B进行排序，再利用外排的方式筛选数据。
public class Solution{
public static void printMethod3(int[] arrA,int[] arrB){
// 先对数组B进行排序
mergeSort(arrB);
// 利用外排的方式进行筛选判断
int p1 = 0;
int p2 = 0;
int lenA = arrA.length;
int lenB = arrB.length;
while(p1 <= lenA-1 && p2 <= lenB-1){
if(arrB[p2]<arrA[p1] && p1 <= lenA-1 && p2 <= lenB-1){
System.out.println(arrB[p2]);
p2++;
}
if(arrB[p2] == arrA[p1] && p1 <= lenA-1 && p2 <= lenB-1 ){
p2++;
}
if(arrB[p2] > arrA[p1] && p1 <= lenA-1 && p2 <= lenB-1){
p1++;
}
}
while(p2 <= lenB-1){
System.out.println(arrB[p2++]);
}
}
//
public static void mergeSort(int []arr){
if (arr == null || arr.length < 2) {
return;
}
sort(arr,0,arr.length-1);
}
public static void sort(int []arr,int L,int R){
if(L == R)
return;
int mid = L + ((R-L)>>1);
sort(arr,L,mid);
sort(arr,mid+1,R);
merge(arr,L,mid,R);
}
public static void merge(int []arr,int L,int mid,int R){
int p1 = L;
int p2 = mid+1;
int []temp = new int[R-L+1];
int i = 0;
while(p1<=mid && p2<=R){
temp[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid){
temp[i++] = arr[p1++];
}
while(p2<=R){
temp[i++] = arr[p2++];
}
for(i = 0;i<temp.length;i++){
arr[L+i] = temp[i];
}
}
}
对于第三个算法，对数组B先进行排序，这里面使用的排序为归并排序(merge-sort),归并排序的时间复杂度为O(N logN),对数组B排好序后，利用两个变量p1,p2分别指向数组A和数组B的第一个数
while(p1 <= lenA-1 && p2 <= lenB-1)
在上面的循环条件内，如果p2指向的数小于p1指向的数，那么打印p2指向的数字并移动p2;如果p2指向的数等于p1指向的数，那么移动p2不打印；如果p2指向的数大于p1指向的数，那么移动p1不打印。这样利用p1,p2对两个数组依次外排，就可以打印出符合条件的数。这个过程，最坏的情况需要遍历一遍数组A和数组B,所以时间复杂度显而易见为O(M+N)。那么该算法的时间复杂度可以表示为：O(M logM)+O(M+N)。
三种算法时间复杂度的比较
第一种算法的时间复杂度为O(M×N),第二种算法的时间复杂度为O(M logN),如果了解过指数爆炸，那么就知道第二种算法要远远好于第一种算法。当N的数量级达到几千万，几亿时logN还没有超过100。那么对于第二种算法和第三种算法，哪种算法更好呢？这就没有办法比较了，第三种算法跟数组B的数据量有很大关系，当数据量M很大时，这个算法的评价指标趋近为O(N logN)级别的算法，当M的值很小时，这个算法的评价指标可以看做一个O(N)级别的算法。不过第二种算法和第三种算法的时间复杂度肯定是优于算法一的。
冒泡排序，选择排序与插入排序的时间复杂度分析
冒泡排序
public class BubbleSort{
public static void sort(int []arr){
//每次将最大的数字排到最后，一共需要排len-1次
for(int i = 0;i < arr.length-1;i++){
// 需要交换的次数
for(int j = 0;j<arr.length-1-i;j++){
if(arr[j] > arr[j+1])
swap(arr,j,j+1);
}
}
}
public static void swap(int []arr,int i,int j){
if(i>arr.length-1 || j>arr.length-1 ||i==j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
}
冒泡排序的时间复杂度显而易见为O(N²)
选择排序
public class SelectionSort{
public static void sort(int []arr){
for(int i = 0;i<arr.length;i++){
int minIndex = i;
for(int j = i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex])
minIndex = j;
}
swap(arr,i,minIndex);
}
}
public static void swap(int []arr,int i,int j){
if(i>arr.length-1 || j>arr.length-1 || i==j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
}
选择排序使用一个minIndex来记录最小值的下标，每次将最小值排序出来，因为有两次遍历数组的过程，所以这个选择排序算法的时间复杂度也是O(N²)。
插入排序
public class InsertionSort{
public static void sort(int []arr){
for(int i = 1;i<arr.length;i++){
for(int j = i;j>=1 && arr[j]<arr[j-1];j--){
swap(arr,j,j-1);
}
}
}
public static void swap(int []arr,int i,int j){
if(i>arr.length-1 || j>arr.length-1 || i==j)
return;
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
}
插入排序又叫扑克牌排序，它的排序过程和我们抓牌并理牌的过程一样。插入排序和冒泡以及选择排序不同，冒泡和选择排序是一个稳定的时间复杂度，但是插入排序不同，试想一个数组如果是已经排好序的数组，那么插入排序只需要依次插入，遍历了一个循环即可，那么时间复杂度就是O(n),如果一个数组为逆序数组，那么插入排序则退化成了O(N²)的算法。而冒泡排序和选择排序则不会依赖数组的分布状况，无论怎样都会遍历N²次。所以插入排序在当前也是一个非常有意义的排序，如果一个数组是一个近乎有序的数组，那么插入排序的速度就会很快。
递归的本质与master公式的使用
设计一个算法，结果返回一个无序数组的最大值
非递归思路：
public class Solution{
public static int findMax(int []arr){
if(arr == null)
return -1;
int maxIndex = 0;
for(int i = 1;i<arr.length;i++){
if(arr[i]>arr[maxIndex])
maxIndex = i;
}
return arr[maxIndex];
}
}
递归思路：
public class Solution{
public static int findMax(int []arr,int L,int R){
if(arr == null)
return -1;
if(L==R)
return arr[L];
int mid = L+((R-L)>>1);
int maxInLeft = findMax(arr,L,mid);
int maxInRight = findMax(arr,mid+1,R);
return maxInLeft > maxInRight?maxInLeft:maxInRight;
}
}
在写递归程序的时候，第一步是分治，将一个问题化成更小的一个问题，对于本题，把求出一个数组中最大值这个问题转化成了将一个数组分成两半儿，左边求出最大值，右边也求出最大值，左边的最大值和右边的最大值比较出一个最大值。这是分治的过程，第二步就是为递归程序设计一个终止点的返回值，当递归到最简单的情况时，返回什么。递归的本质则是系统的压栈。
程序自上而下执行，执行到int maxInLeft = findMax(arr,L,mid);时，系统栈会记录程序执行到第几行，有哪些变量等信息，并把这些信息压入到系统栈中，保存好信息以后程序进入到findMax方法，等到L==R时，终于得到了返回值，系统栈开始pop,最后进栈的最先还原，因为栈记录了所有信息，所以得以还原现场，当maxInLeft拿到返回值后，系统栈也没有残留的信息了，程序就可以继续往下面执行。
master公式
一个递归过程，如何去分析它的时间复杂度？对于将一个过程分解成均等子过程的递归来说，可以使用master公式来计算时间复杂度。
master公式：T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)
b代表的含义是递归分解成了几个子过程，a代表的含义是一次递归子过程执行了几次，O(N^d)表示除去递归外，额外需要的过程的时间复杂度。
用递归求数组最大值问题中，master通式为：2T(N/2)+O(1)
所以该式子满足条件二：log(b,a) > d。所以这个求最大值的时间复杂度为：O(N)。
归并排序与归并排序时间复杂度分析、额外空间复杂度分析
归并排序的思路：将一个数组，分治成左数组和右数组，对左，右数组分别排序，然后利用外排的方式，使用一个辅助数组将两个数组进行merge操作。代码如下：
public static void mergeSort(int []arr){
if (arr == null || arr.length < 2) {
return;
}
sort(arr,0,arr.length-1);
}
public static void sort(int []arr,int L,int R){
if(L == R)
return;
int mid = L + ((R-L)>>1);
sort(arr,L,mid);
sort(arr,mid+1,R);
merge(arr,L,mid,R);
}
public static void merge(int []arr,int L,int mid,int R){
int p1 = L;
int p2 = mid+1;
int []temp = new int[R-L+1];
int i = 0;
while(p1<=mid && p2<=R){
temp[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid){
temp[i++] = arr[p1++];
}
while(p2<=R){
temp[i++] = arr[p2++];
}
for(i = 0;i<temp.length;i++){
arr[L+i] = temp[i];
}
}
归并排序中利用了非常重要的递归思想，对归并排序的时间复杂度进行分析为：T(N) = 2T(N/2) + O(N)。递归的过程分解了执行两次的子过程，并且两次sort后，还需要进行merge操作，这里面需要一个额外空间的数组，并把两个sort好的数组进行遍历，两个数组的总长度为N,所以除去递归，额外需要的时间复杂度为O(N),因为log(b,a) = d,所以归并排序的时间复杂度为：O(N logN)。什么是额外空间复杂度呢？空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间的大小，额外空间复杂度则是，刨去算法本身程序所占的空间，输入数据所占的空间外，额外的辅助变量所需要的空间与输入数据量N的关系。归并排序在merge过程中，需要一个长度为N的辅助数组来完成，所以归并排序的额外空间复杂度为O(N)。下表为几种常见的排序的时间复杂度与额外空间复杂度：
版权声明：本文为CSDN博主「-出发-」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/happyjacob/article/details/84620880
对数器
对数器的概念和使用
1:有一个你想要测的方法a，
2:实现一个绝对正确但是复杂度不好的方法b，
3:实现一个随机样本产生器
4:实现比对的方法
5:把方法a和方法b比对很多次来验证方法a是否正确。
6:如果有一个样本使得比对出错，打印样本分析是哪个方法出错
7:当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
如何验证归并排序的结果是绝对正确的：
设计对数器的代码如下：
// test 实现一个绝对正确的，同要测试的算法实现相同功能的方法
public static void comparator(int[]arr){
Arrays.sort(arr);
}
// test 实现一个随机样本生成器
public static int[] generateRandomArray(int maxSize,int maxValue){
// 最多生成容量为 maxSize长度的数组
int []arr = new int[(int)((maxSize+1)*Math.random())];
for(int i = 0;i<arr.length;i++){
// 数组每一个数的范围为：(-maxValue,maxValue)
arr[i] = (int)((maxValue+1)*Math.random() - (maxValue*Math.random()));
}
return arr;
}
// test 判断两数组是否相等
public static boolean isEqual(int []arr1,int []arr2){
if(arr1 == null && arr2 == null)
return true;
if(arr1 == null && arr2 !=null || arr1 !=null && arr2 == null)
return false;
if(arr1.length != arr2.length)
return false;
for(int i = 0;i<arr1.length;i++){
if(arr1[i] != arr2[i])
return false;
}
return true;
}
// test 打印
public static void printArray(int []arr){
if(arr == null)
return;
for(int i = 0;i<arr.length;i++){
System.out.print(arr[i]+ " ");
}
System.out.println();
}
// test 复制数组
public static int[] copyArray(int []arr){
if(arr == null)
return null;
int [] copyArr = new int[arr.length];
for(int i = 0;i<arr.length;i++){
copyArr[i] = arr[i];
}
return copyArr;
}
// 测试mergeSort是否正确0
public static void main(String[]args){
int testTime = 5000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for(int i = 0;i<testTime;i++){
int [] arr1 = generateRandomArray(maxSize,maxValue);
int [] arr2 = copyArray(arr1);
mergeSort(arr1);
comparator(arr2);
if(!isEqual(arr1,arr2)){
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed?"Nice":"Wrong");
}
对数器用大样本来测试算法的正确性，可以对算法进行验证，如果设计的算法有误，还可以打印出导致算法与comparator不一致的样本，来进行对比观察。
小和与逆序对问题
小和问题：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组
的小和。
例子：
[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16
解决思路：
可以使用对数组每一个值遍历求得，但是时间复杂度为O(N²)。可以使用归并排序，代码如下：
public class SmallSum{
public static int smallSum(int[] arr){
return mergeSort(arr);
}
public static int mergeSort(int[] arr){
return sort(arr,0,arr.length-1);
}
public static int sort(int[] arr,int L,int R){
if(L == R)
return 0;
int mid = L+((R-L)>>1);
return sort(arr,L,mid)
+sort(arr,mid+1,R)
+merge(arr,L,mid,R);
}
public static int merge(int[] arr,int L,int mid,int R){
int p1 = L;
int p2 = mid+1;
int[] temp = new int[R-L+1];
int i = 0;
int result = 0;
while(p1<=mid && p2<=R){
result += arr[p1]<arr[p2]?(R-p2+1)*arr[p1]:0;
temp[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
// only one can run
while(p1<=mid){
temp[i++] = arr[p1++];
}
// only one can run
while(p2<=R){
temp[i++] = arr[p2++];
}
// temp -> arr
for(i = 0;i<temp.length;i++){
arr[L+i] = temp[i];
}
return result;
}
}
除了小和问题外，逆序对问题也可以通过归并排序巧妙解决,
来源于剑指offer：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007
逆序对和小和问题的思路是一样的，代码如下：
public class Solution{
int result = 0;
public int InversePairs(int[]array){
mergeSort(array);
return result;
}
//
public void mergeSort(int [] arr){
sort(arr,0,arr.length-1);
}
//
public void sort(int []arr,int L,int R){
if(L == R)
return;
int mid = L + ((R-L)>>1);
sort(arr,L,mid);
sort(arr,mid+1,R);
merge(arr,L,mid,R);
}
// merge
public void merge(int[]arr,int L,int mid,int R){
int p1 = L;
int p2 = mid+1;
int [] temp = new int[R-L+1];
int i = 0;
while(p1<=mid && p2<=R){
result=arr[p1]>arr[p2]?(result+(R-p2+1))%1000000007:result;
temp[i++] = arr[p1]>arr[p2]?arr[p1++]:arr[p2++];
}
// only one can execute
while(p1<=mid){
temp[i++] = arr[p1++];
}
// only one can execute
while(p2<=R){
temp[i++] = arr[p2++];
}
// temp -> arr
for(i = 0;i<temp.length;i++){
arr[L+i] = temp[i];
}
}
}
