聲明：本筆記所涉及的資料來源于?？途W(wǎng)
認識時間復雜度
常數(shù)時間的操作：一個操作如果和數(shù)據(jù)量沒有關系，每次都是固定時間內(nèi)完成的操作，叫做常數(shù)操作。我的理解是這種操作最終的執(zhí)行就是執(zhí)行匯編命令，而匯編命令執(zhí)行花費的時間都是有限的機器時鐘時間，可以簡單理解為執(zhí)行一個相加指令，所以常數(shù)操作花費的時間是確定有限的，和數(shù)量級沒關系。
時間復雜度為一個算法流程中，常數(shù)操作數(shù)量的指標，常用O（讀作 big O）來表示。具體來說，在常數(shù)操作數(shù)量的表達式中，只要有高階項，不要低階項，也不要高階項的系數(shù)，剩下的部分如果記為f(N),那么時間復雜度為O(f(N))。
評價一個算法流程的好壞，先看時間復雜度的指標，然后再分析不同數(shù)據(jù)樣本下的實際運行時間，也就是常數(shù)項時間。
一個簡單理解時間復雜度的例子：
一個有序數(shù)組A,另一個無序數(shù)組B，請打印B中的所有不在A中的數(shù)，A數(shù)組長度為N,B數(shù)組長度為M。
- 算法一：對于B數(shù)組的每一個數(shù)，都在A中通過遍歷的方式找一下
這相當于兩個for循環(huán),所以常數(shù)操作量f(M,N) = M * N ,所以算法復雜度為O(M * N)
- 算法二：對于B數(shù)組的每一個數(shù)，都在A中通過二分查找的的方式找一下
二分查找常數(shù)操作量約為Log2N,所以總的算法復雜度為O(M * logN),log下標可省，一般看做2
- 算法三：先把數(shù)組B排序，然后用類似外排的方式打印所有在A中出現(xiàn)的數(shù)
排序時間復雜度可為O(M * logM),外排打印時間復雜度為O(M + N),所有總的時間復雜度為O(M * logM) + O(M + N)
所以具體算法的優(yōu)劣還要看實際的數(shù)量級，算法二肯定比算法一要優(yōu)，算法二和算法三需要考慮M,N的取值范圍來判斷
對數(shù)器的概念和使用
如果你有個想要測的方法a,你可以實現(xiàn)一個絕對正確但是復雜度不好的方法b,然后實現(xiàn)一個隨機樣本產(chǎn)生器，還要實現(xiàn)一個對比的方法，這樣方法a和方法b比對多次來驗證方法a是否正確。而且如果有一個樣本使得對比出錯，可以打印樣本分析是哪個方法錯誤。當樣本數(shù)量很多時比對測試依然正確，可以確定方法a已經(jīng)正確。
冒泡排序復雜度分析
第一次冒：0 ............. n-1
第二次冒：0 ....... n-2
第三次冒：0 ... n-3
直到冒完
所有偽代碼可以這樣：
public static void bubbleSort(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);
}
}
}
}
可知當數(shù)量級為N時，常數(shù)操作量就是N*N，時間復雜度就為O(N^2),空間復雜度因為只是操作原數(shù)組，沒有聲請什么額外的空間，所以為常數(shù)，額外空間復雜度為O(1)
選擇排序的復雜度分析
第一次從0 .................n-1中選擇出最?。ù螅┲捣旁?
第二次從 1 .................n-1中選擇出最小（大）值放在1
第三次從 2 .................n-1中選擇出最小（大）值放在2
知道選擇完
偽代碼：
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int e = 0; e < arr.length-1; e ++) {// 最后一個不用比
int min = e;
int i = e + 1;
while( i < arr.length ){
min = arr[min] < arr[i] ? i : min;
i++;
}
swap(arr,e,min);
}
}
同理：時間復雜度O(N^2),額外空間復雜度O(1)
遞歸行為和遞歸行為時間復雜度的計算
遞歸的實現(xiàn)實質(zhì)是方法數(shù)據(jù)的棧的壓入和彈出，壓入或彈出的數(shù)據(jù)即為方法的一些屬性數(shù)據(jù)，如方法指針，參數(shù)，結果等
最典型的應用就是歸并排序
套路就是：最外面一層把主問題分為兩個小問題，加一個merge處理塊
套路公式：
master公式：T(N) = a * T (N / b) + O(N ^ d)
- log(b,a) > d -> 復雜度為O(N^log(b,a))
- log(b,a) = d -> 復雜度為O(N^d * logN)
- log(b,a) < d -> 復雜度為O(N^d)
a 為子規(guī)模執(zhí)行次數(shù)，b 為主規(guī)模分了幾個子規(guī)模，d 為merge處理的負責度里的N的系數(shù)
例：歸并排序
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
最外層將主規(guī)模分為了2個子規(guī)模f(n/2)執(zhí)行，所以a = 2,b = 2,merge處理復雜度為O(2N) = O(N) ,所以d = 1,所以T(N) = 2(N/2) + O(N)
所以log(b,a) = d = 1 ，時間復雜度為O(N * logN)
額外空間復雜度為O(N),主要是每次merge都申請了新的數(shù)組空間
應用 小和問題
public static void main(String[] args){
int[] arr = Util.generateRandomArray(8,10);
smallSum(arr);
}
public static void smallSum(int[] arr){
if (arr == null || arr.length < 2) {
return;
}
System.out.println("原數(shù)組");
Util.printArray(arr);
System.out.println("");
int smallSum = deal(arr,0,arr.length-1);
System.out.println("處理后的數(shù)組：");
Util.printArray(arr);
System.out.println("小和為："+smallSum);
}
public static int deal(int[] arr,int left,int right){
if (left == right){
return 0;
}
int middle = left + ((right-left)>>1);
return deal(arr,left,middle) + deal(arr,middle+1,right)+merge(arr,left,middle,right);
}
public static int merge(int[] arr,int left,int middle,int right){
int[] help = new int[right-left+1];
int sum = 0;
int index = 0;
int p1=left;
int p2=middle+1;
while (p1 <= middle && p2 <= right){
if (arr[p1] < arr[p2]){
System.out.println((right-p2+1)+"個"+arr[p1]+" \n");//打印加數(shù)
}
sum += arr[p1] < arr[p2]? (right-p2+1)*arr[p1]:0;
help[index++] = arr[p1] < arr[p2]? arr[p1++] : arr[p2++];
}
while (p1 <= middle){
help[index++] = arr[p1++];
}
while (p2 <= right){
help[index++] = arr[p2++];
}
for (int i = 0;i < help.length;i++){
arr[left+i] = help[i];
}
return sum;
}
隨機測試結果：
逆序對問題
在一個數(shù)組中，左邊的數(shù)如果比右邊的數(shù)大，則折兩個數(shù)構成一個逆序對，請打印所有逆序對。
public static void main(String[] args){
int[] arr = Util.generateRandomArray(8,10);
System.out.println("原始數(shù)組："+Arrays.toString(arr));
nixudui(arr);
System.out.print("處理后數(shù)組："+Arrays.toString(arr));
}
public static void nixudui(int[] arr){
deal(arr,0,arr.length-1);
}
public static void deal(int[] arr,int left,int right){
if (left == right){
return;
}
int middle = left + ((right-left)>>1);
deal(arr,left,middle);
deal(arr,middle+1,right);
merge(arr,left,middle,right);
}
public static void merge(int[] arr, int left,int middle, int right){
int p1=left;
int p2 = middle+1;
int i = 0;
int[] help = new int[right-left+1];
while (p1 <= middle && p2 <= right){
if (arr[p1] > arr[p2]){
for(int j = 0;j < middle-p1+1;j++){
System.out.println("逆序對："+arr[p1+j]+" "+arr[p2]);
}
help[i++] = arr[p2++];
}else {
help[i++] = arr[p1++];
}
}
while (p1 <= middle){
help[i++] = arr[p1++];
}
while (p2 <= right){
help[i++] = arr[p2++];
}
for ( i = 0;i < help.length;i++){
arr[left+i] = help[i];
}
}
執(zhí)行結果：
和小和問題是同樣的套路，時間復雜度為O(N * log N),空間復雜度為O(N)
拓展
二分查找的時間復雜度
二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x<a[n/2],則只要在數(shù)組a的左半部分繼續(xù)搜索x,如果x>a[n/2],則只要在數(shù)組a的右半部搜索x.
時間復雜度無非就是while循環(huán)的次數(shù)！
總共有n個元素，
漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個數(shù)），其中k就是循環(huán)的次數(shù)
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2為底，n的對數(shù)）
所以時間復雜度可以表示O(h)=O(log2n)
