時間複雜度O(N^2)：太簡單沒啥要解釋的了
額外空間複雜度O(1)：在完成每個目标的過程中，在目标完成過程中增加的變量和對象占用的空間
遞歸的深入剖析
通過一個簡單執行個體來分析：通過遞歸求一個數組中的最大值
public class GetMaxNum {
public static int getMax(int[] arr,int L,int R){
if (L==R){
return arr[L];
}
int middle=(L+R)/2;
int leftMax=getMax(arr,L,middle-1);
int rightMax=getMax(arr,middle,R);
return Math.max(leftMax,rightMax);
}
}
接下來我們分析遞歸的底層是怎麼實作的
遞歸的過程就是一個系統進行一個壓棧的過程
從底層一路壓棧上去，當到達了if判斷的結束之後，系統就會進行一個出棧的過程，一步步往回出棧。
總結來說：在邏輯上是自己調用自己，在系統中隻是一個系統棧而已。是以說所有的遞歸都可以變成非遞歸，也就是疊代。
master公式的詳細講解
T：時間複雜度
N：樣本量
以上面為例：
T(N)=a*T(N/b)+O(N^d) --》 T(N)=2*T(N/2)+O(N^0)
T(N)：指的是該算法完成某個目标所使用的所有時間；
2*T(N/2)：上面程式将查詢分為左右兩邊，也就是将樣本平分了(N/2)，又因為被平分了兩半是以就要乘以2 ( 2*T(N/2) )，
O(N^0)：主查詢塊以外的一些消耗，這裡就是左右兩邊對比的消耗，隻進行了一次比較是以N^d=1，也就是d=0
然後帶入式子：
log(b,a)：以b為底，log a
log(b,a) >d --》 log(2,2) > 0 滿足了第一個，是以上面式子的複雜度就是O(N^log(2,2)) --》 O(N)
歸并排序的深入講解
時間複雜度O(N*logN),額外空間複雜度O(N)
思想：
假設：有一個無序數組：arr=5 3 6 2 0 1
首先将左邊排好序，和右邊排好序
然後建立一個空數組，對原數組左右兩邊進行比較：
首先比較a和b值：a>b
放入到空數組中：
移動b位置
繼續比較a和b的值：a>b
移動b位置
繼續比較a和b的值：a>b
移動b位置，發現b已經沒有了，直接拷貝a的數組
排序完成！
使用master公式計算：T(N)=2T(N/2)+O(N)
log(b,a)=d,是以複雜度是N*log(N)
Coding:
将左右兩邊分别排好序
merge()方法
while語句中：排序的過程，如上面分析一樣，比較兩個p1和p2的值，然後指派以及移動
上面while語句一定會導緻一個越界，這樣的話，就需要将另外一個沒有越界的值賦到後面
完整代碼
package cn.mxl.work;
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {4,3,2,7,6,8,0,9};
sortProcess(arr, 0, arr.length-1);
for(int i : arr) {
System.out.println(i);
}
}
public static void sortProcess(int[] arr,int L,int R) {
if(L == R) {
return ;
}
int mid=L+((R-L)>>1);
sortProcess(arr,L,mid);
sortProcess(arr,mid+1,R);
merge(arr,L,mid,R);
}
private static void merge(int[] arr, int L, int mid, int R) {
// TODO Auto-generated method stu
int[] help=new int[R-L+1];
int i=0;
int p1=L;
int p2=mid+1;
while(p1<=mid&&p2<=R) {
help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
// 兩個必有且隻有一個越界
while(p1<=mid) {
help[i++]=arr[p1++];
}
while(p2<=R) {
help[i++]=arr[p2++];
}
for(i=0;i<help.length;i++) {
arr[L+i]=help[i];
}
}
}
歸并解決小和問題
問題描述：
左右兩邊進行分治 ，将左邊和右邊分别排好順序
左邊的每個數字對于右邊排好序的來說，目前值要被加（右邊的長度-p2位置+1）次
完整代碼：
public class SmallSum {
public static int partitionSort(int[] arr,int L,int R){
if (L==R){
return 0;
}
int middle=L+((R-L)>>1);
return partitionSort(arr,L,middle)
+partitionSort(arr,middle+1,R)
+merge(arr,L,middle,R);
}
private static int merge(int[] arr, int l, int middle, int r) {
int pos1=l;
int pos2=middle+1;
int[] help=new int[r-l+1];
int i=0;
int res=0;
while (pos1<=middle && pos2<=r){
res+=arr[pos1]<arr[pos2]?(r-pos2+1)*arr[pos1]:0;
help[i++]=arr[pos1]<arr[pos2]?arr[pos1++]:arr[pos2++];
}
while (pos1<=middle){
help[i++]=arr[pos1++];
}
while ((pos2<=r)){
help[i++]=arr[pos2++];
}
for (int j = 0; j < help.length; j++) {
arr[l+j]=help[j];
}
return res;
}
public static void main(String[] args){
int[] arr={1,3,4,2,5};
int res = partitionSort(arr, 0, arr.length - 1);
System.out.println(res);
}
}