演算法效率

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

&ensp；

時間復雜度

時間復雜度的概念

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

大O 的漸進表示法

讓我們通過代碼，來了解它

當我們看到func1方法時，首先，要找到運行次數最多的陳述句

public class TimeComplexityAndSpaceComplexity {
    public static  void func1(int N){
        int count = 0;
        for (int i = 0; i < N ; i++) {
            for (int j = 0; j < N ; j++) {
                count++;// 第一個就是 這個 count++;,它執行了多少次？
 //  兩個for嵌套，兩個for回圈N次，最外圍的for回圈，每遍歷一個資料，嵌套在內部的for回圈，就要回圈 N 次，
                //即 count++; 陳述句 被回圈執行 N*N 次，
                // 小技巧，找執行次數最多的陳述句，你就看哪里有回圈就行了，
            }
        }
        for (int k = 0; k < 2 * N ; k++) {
            count++;// 這里的 count++; 被執行了 2*N
        }
        int M = 10;
        while ((M--) > 0) {
            count++;// 這里count++; 被執行了 10次
        }
        System.out.println(count);
    }
}

 經過我們分析，這句代碼在程式中 一共被執行了 F(N) = N^2 + 2N + 10
 在座的各位，跟著我思考一個問題：
如果我們的 N 越來越大
比如：
N = 10 F(N) = 10^2 + 20 + 10 == 100 + 30 == 130
N = 100 F(N) = 100^2 + 200 + 10 == 10000 + 210 == 10210
N = 1000 F(N) = 1000^2 + 2000 + 10 == 1000000 + 2010 == 1002010
 --- ---- ---
---- ----  ---

 按照這樣想法，后面的 2N + 10，隨著N增大，就顯得微不足道，

?

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

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

?

推導大O階方法：

    以func1的時間復雜度為例： F(N) = N^2 + 2N + 10
    
    1、用常數1取代運行時間中的所有加法常數，{F(N)= N^2 +2N +1}
    2、在修改后的運行次數函式中，只保留最高階項，{F(N)=N^2}
    
    3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階
   假設 使用完方法 1 和 2，把該做的都做了，還剩 3* N^2,
 此時，按照方法3的規則去操作(去掉3*)，最終的時間復雜度為 O(N^2),
即分析這個代碼的時間復雜度，在使用大O的漸進表示法以后

Func1的時間復雜度為 O(N^2).

?

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，

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

    最壞情況：任意輸入規模的最大運行次數(上界)
    平均情況：任意輸入規模的期望運行次數（根據代碼的情況給出平均時間復雜度）
    最好情況：任意輸入規模的最小運行次數(下界)
    例如：在一個長度為N陣列中搜索一個資料x
    最好情況：1次找到
    最壞情況：N次找到
    平均情況：N/2次找到（可以這么理解，在中間的位置找到的，）

&ensp；

在實際中一般情況關注的是演算法的最壞運行情況，

舉個例子：

 假設陣列中有N個元素，現在我們要在陣列中查找一個元素，最壞的情況，該元素處在陣列末尾，
 也就是說 需要遍歷整個陣列元素，
 故：陣列中搜索資料時間復雜度為O(N)

?

再來看幾個代碼案例

案例1

public class TimeComplexityAndSpaceComplexity {
    public static  void func(int N){
            int count = 0;
            for (int k = 0; k < 2 * N ; k++) {
                count++;// 2*N
            }
            int M = 10;
            while ((M--) > 0) {
                count++;// 10
            }
            System.out.println(count);
        }
    }
  時間復雜度為 F(N) = 2*N + 10.使用大0漸進法來表示時間復雜度為 O(N)

?

案例 2

public class TimeComplexityAndSpaceComplexity {
    public static  void func(int N,int M) {
        int count = 0;
        for (int k = 0; k < M; k++) {
            count++;// M
        }
        for (int k = 0; k < N; k++) {
            count++;// N
        }
        System.out.println(count);
    }
}
  時間復雜度為 F(N) = N + M.使用大0漸進法來表示時間復雜度為 O(N + M)

&ensp；

案例3

public class TimeComplexityAndSpaceComplexity {
    public static  void func(int N) {
        int count = 0;
        for (int k = 0; k < 100; k++) {
            count++;// 100
        }
        System.out.println(count);
    }
}
  時間復雜度為 F(N) = 100.使用大0漸進法來表示時間復雜度為 O(1)

?

大家在分析時間復雜度時，一定要結合思想，不能光看代碼，

?

接下來，我們來分析 幾個復雜 的 時間復雜度 的 程式

冒泡排序

public class TimeComplexityAndSpaceComplexity {
    public  void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {// 執行 length 次
            boolean sorted = true;// 暫不考慮優化(陣列已經是有序的, 也就是說 程式在遍歷一次判斷一下，就結束了)
            // 最好情況：時間復雜度為 O(N)
            for (int i = 1; i < end; i++) { //length -1 次
                if (array[i -1]> array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }
}

時間復雜度是考慮最壞情況（每一個元素都需排序），不考慮優化情況和平均情況：
兩個for回圈嵌套length * (length - 1) == N(N-1) = N^2 - N == N^2
故 冒泡排序的空間復雜度為 O(N^2)

?

二分查找

public class TimeComplexityAndSpaceComplexity {
    int binarySearch(int[] array, int value) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (array[mid] < value) {
                left = mid + 1;
            } else if (array[mid] > value) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
} 圖1

圖1

?

遞回

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

比如說：我這個遞回，遞回了N次（N），每次下去（N） 就是 一個回圈，回圈是回圈了 N 次
 那么遞回的時間的復雜度 為 N * N^2 = N^3

現在我們來看下面的程式（階乘）

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

雖然我們不知道該程式的遞回次數，但是程式每次遞回下去的時候，遇到是三目運算子，
三目運算子 不是回圈，所以 每次遞回的次數為1次
再來看看 程式，如果我們求的是 4 的階乘，也就是 N==4,

N<2,那么只有 N==1時，回傳 1（終止遞回），然后在看后面 factorial(N-1)
每次遞回減一，那么 4,3,2,1 一共 4次
也就是說 遞回的次數 為 N 次，
所以 時間的復雜度 = 遞回的次數 * 每次遞回執行的次數 == N * 1 == N
即 O(N)

?

計算斐波那契遞回fibonacci的時間復雜度？

public class TimeComplexityAndSpaceComplexity {
    int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }
}

還是一樣，每次進來就是一個 三目運算子，每次遞回執行的次數為1，
再來看 遞回的次數
假設我們想求第四個斐波那契數，那么就需要我們去計算 第3 和 第4 個斐波那契數
因為斐波那契數，從第三位數開始，該數 等于 自身前兩個數之和，

那么 第3個斐波那契數 ，需要 第1和第2個斐波那契數
第2個斐波那契數 需要 第1個斐波那契數，（因為N<2,是終止條件）
至于，第1個斐波那契數，就不需要再計算了（終止了）

第4個斐波那契數，需要 第3 和 第2個斐波那契數
第3個斐波那契數需要 第2 和 第1 個斐波那契數，第2個斐波那契數，需要第1個斐波那契數，（因為N<2,是終止條件）
至于，第2個斐波那契數，需要第一個斐波那契數 （因為N<2,是終止條件）
見 圖 2

 斐波那契數的 時間復雜度 見圖3

圖2

圖3

?

空間復雜度

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

冒泡排序 的 空間復雜度

public class TimeComplexityAndSpaceComplexity {
    public 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(1)
 有的人可能會說 sorted 在每次回圈的時候，都會創建，
 但是請注意 sorted 變數只有1個，你不能說我們回圈10次，定義了10個 sorted
 每次回圈結束 變數空間是會被回收的，回圈開始再創建一個，
 也就是說 sorted 自始至終都是一個，
 至于陣列，不算，注意空間復雜度解釋的題干中的 “臨時” ，你可以理解為另外消耗的,或者說括號里的變數
 這么說吧，陣列是冒泡排序必須品，而 sorted 只是臨時創建的，為了輔助這個程式的運行
 所以”臨時“的變數個數，只有sorted一個
 故 該冒泡排序的空間復雜度為 O(1)

?

計算fibonacci的空間復雜度

public class TimeComplexityAndSpaceComplexity {
    int[] fibonacci(int n) {// 計算斐波那契數的第N項
        long[] fibArray = new long[n + 1];
         n如果越大，資料就越大，你的結果要存入這個陣列里(這里的n+1，是因為下標，自己品)
         下面的陣列元素，最后都是要存入陣列的，也就是說 下面生成的臨時變數，都是存入陣列的
         即元素個數，就是 臨時變數的個數，即求斐波那契數 的 空間復雜度 為 O(N+1)
         再根據大O漸進法，空間復雜度的最終結果： O(N)
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }
}

?

計算階乘遞回Factorial的時間復雜度？

public class TimeComplexityAndSpaceComplexity {
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1)*N;
    }
}
 遞回的空間復雜度有點不一樣，
 每遞回一次，函式就要在堆疊上開辟一塊記憶體
 也就是說遞回一次，空間復雜度為 O(1)
 遞回N次，空間復雜度為 O(N)
 即 階乘遞回函式的 空間復雜度為 O(N)

想要熟練的分析時間和空間的復雜度還是需要多刷題，多練習，

本文結束