一、演算法效率

演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，
在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，因為現在的記憶體不像以前那么貴，所以經常聽到過犧牲空間來換取時間的說法

二、時間復雜度

1.時間復雜度的概念

在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，
演算法中的基本操作的執行次數，為演算法的時間復雜度，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，

一個演算法所花費的時間與其中陳述句的執行次數成正比例，
演算法中的基本操作的執行次數，為演算法的時間復雜度，

2.大O的漸進表示法

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號

(1)推導大O階方法

1. 用常數1取代運行時間中的所有加法常數，
2. 在修改后的運行次數函式中，只保留最高階項，
3. 如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階

代碼如下（示例）：

    void func(int N){
        int count = 0;//執行1次
        for (int i = 0; i < N ; i++) {//執行N*N次
            for (int j = 0; j < N ; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N ; k++) {//執行2*N次
            count++;
        }
        int M = 10;//執行1次
        while ((M--) > 0) {//執行10次
            count++;
        }
        System.out.println(count);
    }

所以func方法的執行次數為 1+N²+2*N+1+10

我看到func的執行次數，如果當我們的N非常大時，假設N = 100，那么這里的+1和+10是不是可以忽略了，因為100²=10000,在一萬面前+1和+10可以說是微乎其微了，所以+1和+10沒什么區別，

這就用到了前面說了推導大O階方法，

1. 用常數1取代運行時間中的所有加法常數，

就變成了 1+N²+2*N+1+1

再來看

2. 在修改后的運行次數函式中，只保留最高階項，

簡化后 N²

3. 如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階

這里我們的最高階項是2，但前面沒有常數所以沒必要去除，如果N²前面還有個2就是2N²就要去除2變成 N²
所以使用大O的漸進表示法以后，Func的時間復雜度為 O(N²)

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，時間復雜度是一個函式，只能大致估一下這個演算法的時間復雜度，

3.時間復雜度的三種情況

另外有些演算法的時間復雜度存在最好、平均和最壞情況，

(1) 最壞情況

最壞情況：任意輸入規模的最大運行次數(上界) 也就是 O(N)

這里的N代表的是問題的規模

(2)最好情況

任意輸入規模的最小運行次數(下界) 也就是 O(1)

(3)平均情況

任意輸入規模的期望運行次數

注意：這里的平均情況并不是最好和最壞情況相加的平均值，而是我們期望運行的次數，有時候平均情況可能和最好或者是最壞情況一樣，

在平常我們所說的時間復雜度一般說的都是演算法的最壞情況

4.常見時間復雜度計算舉例

1.例子

示例1：

void func2(int N) {
	int count = 0;//1
	for (int k = 0; k < 2 * N ; k++) { //2*N
	   count++;
	}
	int M = 10;//1
	while ((M--) > 0) {//10
	   count++;
	}
	System.out.println(count);
}

1+2*N+1+10 通過推導大O階方法后:時間復雜度為 O(N)

示例2：

void func3(int N, int M) {
int count = 0;//常數可以不加
for (int k = 0; k < M; k++) {//M
   count++;
}
for (int k = 0; k < N ; k++) {//N
   count++;
}
System.out.println(count);
}

時間復雜度為：O(M+N)

示例3：

void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {//用常數1取代運行時間中的所有加法常數
   count++;
}
System.out.println(count);
}

這里的時間復雜度為 O(1),因為傳進來的N并沒有使用

2.冒泡排序時間復雜度

示例4：
這是一個冒泡排序，我們來求一下它的最好最壞和平均情況的時間復雜度

void bubbleSort(int[] array) {
   for (int end = array.length; end > 0; end--) {
       boolean sorted = true;
       for (int i = 1; i < end; i++) {
       	if(array[i - 1] > array[i]){
       		Swap(array, i - 1, i);
               sorted = false;
           }
       }
       if (sorted == true) {
           break;
       }
   }
}

最好：O(N)
最壞：O(N²)
平均：O(N)

這是一個經過優化后的冒泡排序，最好的情況就是該組資料已經是有序的了，所以只需走一遍就好了，也是是O(N).
而最壞的情況就把陣列全部遍歷了一遍就是 N²
我們前面說過平均情況就是我么個期望的情況，我們期望的當然就是O(N)

3.二分查找的時間復雜度

我們知道求時間復雜度一般求的都是最壞的情況，二分查找只有當我們找最旁邊那兩個個數時才是最壞情況，我們就假設我們要找的就是最邊邊的那個數，

 public static int binarySearch(int[] arr,int x){
            int left = 0;
            int right = arr.length-1;
            int mid = 0;//中間下標

            while(left <= right){
                mid = left+(right-left)/2;
                if(arr[mid] > x){
                    right = mid - 1;
                }else if(arr[mid] < x){
                    left = mid+1;
                }else{
                    return mid;
                }
            }

            return -1;
  }

所以二分查找的時間復雜度為 O(log2^N)

4.遞回的時間復雜度

遞回的時間復雜度 = 遞回的次數*每次遞回執行的操作的次數

示例1：

long factorial(int N) {
 return N < 2 ? N : factorial(N-1) * N;
}

這里的的遞回次數為 N 次，這里沒有回圈，每次執行的是一個三目運算子相當于1次，所以為 N+1次，時間復雜度就是 O(N)，

示例2：
這是一個遞回實作的斐波那契數列

public static int fib(int n){
        if(n==1||n==2){
            return 1;
        }else{
            return fib(n-1)+fib(n-2);
        }
}

斐波那契數列的遞回次數其實就是一個等比數列求和，最后的執行次數為 (2ⁿ) - 1,通過通過推導大O階方法最后的時間復雜度為 O(2^N)

時間復雜度只是一個大概的，當數字足夠大時這里缺失的部分并不影響我們時間復雜度的計算，

三、空間復雜度

1.空間復雜度概念

空間復雜度是對一個演算法在運行程序中臨時(額外)占用存盤空間大小的量度
占用存盤空間大小的量度 ，
空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，
空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法

2.空間復雜度的計算

(1) 冒泡排序

這個冒泡排序的空間復雜度為 O(1)

為什么呢？因為空間復雜度是為了解決一個問題額外申請了其他變數，這里的array陣列并不是額外的它是必須的，但這里的 sorted 是額外申請的，它每回圈一次就定一次為什么不是O(N)呢？因為每回圈一次這個變數是不是不要了呢？所以來來回回就是這一個變數，

void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
     boolean sorted = true;//額外變數
     for (int i = 1; i < end; i++) {
         if (array[i - 1] > array[i]) {
             Swap(array, i - 1, i);
             sorted = false;
         }
     }
     if (sorted == true) {
         break;
     }
 }
}

(2) 斐波那契數列

這里的空間復雜度為 O(N)
這里為了求第1~N的斐波那契數列的代碼，為了解決這個問題申請了一個額外的陣列的空間，空間大小為 N+1，因為1是常數項，所以這個代碼的空間復雜度為 O(N)

public static long[] fibonacci(int n) {
        long[] fibArray = new long[n + 1];//額外空間
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }

(3)遞回

這是一個求階層的遞回，他的空間復雜度為 O(N)
因為遞回在遞的程序中，每遞一次都會都會創建一個臨時變數，

long factorial(int N) {
 return N < 2 ? N : factorial(N-1)*N;
}

總結

1.在平常我們所說的時間復雜度一般說的都是演算法的最壞情況
2.時間復雜度度是一個函式，這個函式只能大致估一下這個演算法的時間復雜度
3.空間復雜度是個演算法在運行程序中額外占用存盤空間大小的量度