一、什么是時間和空間復雜度？

📚 那么在了解時間復雜度和空間復雜度之前，我們先要知道為何有這兩者的概念：

首先我們要先了解"算法"，在之前我們學習過關于"一維前綴和與差分"，"二維前綴和與差分"這部分知識，而這部分知識就屬于基礎算法中的"前綴和"與"差分"的兩部分，也就是說它們也是算法。

而除了它們以外，其實我們在之前的學習中，大部分的知識也都和算法脫不開干系，例如："枚舉"，"位運算"，"冒泡排序"，"二分查找"等，只不過在當時學習時，我們主要在意的是"如何解題"，并沒有深究題解的時間效率和空間效率。

📕 我們先引入一個小題：

有一高度10階的樓梯，每步只能上一階或二階，請問從下往上走，一共能得到多少種走法？

這題大家應該是很熟悉的，通過我們之前學習過的函數遞歸思想，腦海中的解題思路就會是：

反向思考一下，如果我們距離最后一步到達10階，就是有兩種情況"8->10 或 9->10"，而"8->10"就需要我們先走到8階，相應的"9->10"就需要我們先走到9階，所以從0階走到10階的走法應該等于"0階到9階的走法+0階到8階的走法"。

相應的，之前的7，8，9階也皆是如此，于是我們便能寫出遞歸函數：

public static void main(String[] args) {System.out.println(climbStairs(10));}public static int climbStairs(int num){if(num == 0){return 0;}if(num == 1){return 1;}if(num == 2){return 2;}return climbStairs(num - 1) + climbStairs(num - 2);}

這就是我們之前學習過的"函數遞歸"了，這樣的方法確實能得到答案，但是讓我們現在思考一下，這個方法的效率是否夠高呢？按照我們這段代碼的思路來看，運算過程中實際上是這樣的：

隨著每多1階樓梯。我們要計算的步驟就都相應乘以2，并且大部分的數據都是重復的。如果我們輸入一個較大的數，那么這種算法的時間損耗是相當大的。

所以由此看來，這個方法就不算是一個高效率的算法，而判斷算法效率如何，就需要我們所提到的"時間和空間復雜度"了。

時間復雜度和空間復雜度是用來表示一個算法的優劣程度的

二、時間復雜度

① 時間復雜度的概念

📚 時間復雜度的定義：

算法的時間復雜度是一個數學函數，它能夠大致的表示出一個算法的運行時間，因為一個算法運行所消耗的時間，是不能算出精確值的，只有將代碼運行一遍，才能夠得出對應精確的時間，但是總不能將所有的算法都測試一遍，這樣太麻煩了，于是就有了時間復雜度的分析方法：算法中的基本操作執行次數，就稱為算法的時間復雜度。

② 大O漸進表示法

📚 我們先舉一個例子，試著求一下這段代碼的時間復雜度：

public static int fun(int n){int a = 0;for(int i = 0;i < n;i++){a++;}return a;}

這段代碼我們可以看出，傳入n，其中基本操作執行次數就也是n，故此代碼的時間復雜度為O(n)。

📚 那么如果我們在其中摻雜了多端基本操作，使得執行次數的函數變得較為復雜呢：

public static int fun(int n){int a = 0;for(int i = 0;i < n;i++){a++;}for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){a++;}}a++;a++;a++;return a;}

這段代碼中的基本操作執行次數就就稍微比較多了，我們分別來看：第一段的for循環的基本操作次數為n，而第二段的for循環嵌套的基本操作次數為n^2，第三段的基本操作次數3，所以得到的基本操作次數為：n + n^2 + 3；而所謂的大O漸進法就是為了簡化此等函數式的。

③ 推導大O階方法

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

📕 在修改后的運行次數函數中，只保留最高階項。

📕 如果最高階項存在且不是1，則去除以這個項目相乘的常數。

由于我們并不需要計算精確的執行次數，我們就可以將式子中基本操作次數占比較少的部分省略掉，所以我們該式子的時間復雜度可以簡化為O(N^2)。

(注:常數階的時間復雜度是O(1)，代表是常數次，不是1次，只要是常數，都用O(1)進行表示)

這里我們就可以引用一下剛剛我們所提出的經典問題"爬樓梯問題"，來算一下剛剛我們那個不完美的方法的時間復雜度為多少~

我們仍然看之前的思路圖，如果要上n階樓梯，那么就要算(n-1)階，(n-2)階，而得到(n-1)，就要知道(n-2)階，(n-3)階分別的可能次數，所以可以得到此圖：

這像是一棵二叉樹，高度為N-1，節點個數就接近2的N-1次方，所以時間復雜度近似看成O(2^N)。

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

📕 最壞情況：任意輸入規模的最大運行次數(上界)

📕 最好情況：任意輸入規模的最小運行次數(下界)

📕 常見的時間復雜度量級：

常數階	O(1)
對數階	O(logN)
線性階	O(n)
線性對數階	O(nlogN)
平方階	O(n^2)
立方階	O(n^3)
K次方階	O(n^k)
指數階	O(2^n)

順便一提，一般情況下我們的電腦的單秒運算量大概為 2e8次 我們在平時刷題時也可以按照這個與時間復雜度結合，就能大致估算運行時間了~

三、空間復雜度

空間復雜度是一個函數，它能夠描述一個算法執行所需的額外存儲空間，同樣用大O漸進法表示，如O(1)、O(n)、O(n^2)等。空間復雜度能夠直接影響算法對內存資源的使用。

在我們平時刷題，或者算法競賽中，題目會給出空間限制，通常以MB為單位。計算空間復雜度時，我們估算程序使用的內存，基本單位換算如下：

📕 8 b = 1 B
📕 1 KB = 1024 B
📕 1 MB = 1024 KB
📕 1 GB = 1024 MB

我們要知道，int占用4字節，long占用8字節，double占用8字節等，運算空間復雜度需要我們將代碼運行過程中所有字節相加并且轉換為MB。

📚 接下來讓我們看幾段代碼練習一下：

    public static void main(String[] args) {//1int[] n = new int[10000000];//2long[][] n1 = new long[2000][3000];}

📕 一個大小為 n = 10^7 的int數組，內存消耗為：4e7字節，換算成MB為 4e7/(1024*1024) 約等于38.1MB。

📕 一個大小為 2000 * 3000 的 long 二維數組，內存消耗為：8 * 2000 * 3000字節，換算成MB為(8 * 2000 * 3000) / (1024*1024) 約等于45.78MB。

public static void main(String[] args) {int[] arr = {7,9,4,8,5,6,1,2,3};bubbleSort(arr);System.out.println(Arrays.toString(arr));}public static 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]) {int tmp = array[i];array[i] = array[i - 1];array[i - 1] = tmp;sorted = false;}}if (sorted == true) {break;}}}

📕 由于bubbleSort使用的都是常數額外空間，于是空間復雜度為O(1)

    public static void main(String[] args) {System.out.println(fun(10));}public static int fun(int n) {int num = 0;int[] m = new int[n];for(int i = 1;i <= n;i++){num++;}return num;}

📕 第一行創建了int型變量，此為O(1)，而后第二行創建一個數組，這個數據占用大小為n，后續的代碼中并沒有創建新的變量，故不用看。則使用的額外空間式子為1 + n，空間復雜度為O(n)

四、優化爬樓梯問題

📚 那么經過幾道題的練習，我們再回過頭來看我們最開始舉例的"爬樓梯問題"：

剛剛使用遞歸的方式求解"爬樓梯問題"，我們得到的對應信息為：

時間復雜度為：O(2^n)

空間復雜度為：O(n)

我們剛剛已經意識到了，O(2^n)的時間復雜度有多么可怕，并且O(n)的空間復雜度也并不是特別優秀，那么我們應該如何對其進行優化呢？

時間復雜度太高的原因是因為我們從上而下的進行分支，而這些分支中又出現了很多的重復項，導致我們的代碼會在無用的地方浪費很長時間。而想要對從上而下的分支進行操作并且判斷是否重復，是并不容易的，那么我們不妨轉換一下思路，我們可以從底向上的，一步一步通過迭代的方式來嘗試一下：

首先我們先算出從1階到10階需要走的步數：

我們將其寫入表格中：

然后讓我們一步一步的觀察其中的規律：

1階2階與3階的關系：

2階3階與4階的關系：

3階4階與5階的關系：

我們可以觀察到一個現象，在每一次的迭代中，F(N)只與F(N - 1)和F(N - 2)有關，也就是說當我們想求一個狀態時，只需要保留之前的兩個狀態就足夠了，之前的數據就可以扔掉不要了。

這就是最最簡單的一個動態規劃問題~

public static int climbStairs(int num){if(num == 0){return 0;}if(num == 1){return 1;}if(num == 2){return 2;}int a = 1;int b = 2;int temp = 0;for(int i = 3;i <= num;i++){temp = a + b;a = b;b = temp;}return temp;}

一共只用了一次for循環，這段代碼的時間復雜度顯而易見是O(n)，而我們只使用了兩或三個變量，則空間復雜度為O(1)~

趁熱打鐵，既然已經講了這題了，有興趣的小伙伴也可以寫一下這題~就是一樣的道理，只是多了一個(一步邁三階)的可能~實際上我們只需要多寫出一個(n == 3)的情況，以及使temp變成(a + b + c)就可以了~

面試題 08.01. 三步問題 - 力扣（LeetCode）

class Solution {public int waysToStep(int n) {if(n < 1){return 0;}//一階臺階1種走法if(n == 1){return 1;}//兩階臺階2種走法if(n == 2){return 2;}//三階臺階4種走法if(n == 3){return 4;}long a = 1;long b = 2;long c = 4;long temp = 0;//F(n) = F(n - 1) + F(n - 2) + F(n - 3);//同理,后續的迭代中F(n)也只與F(n - 1) , F(n - 2) , F(n - 3)相關:for(int i = 4;i <= n;i++){temp = a + b + c;a = b;b = c;c = temp;a = a % 1000000007;b = b % 1000000007;c = c % 1000000007;temp = temp % 1000000007;}return (int)temp;}
}

那么這次關于時間和空間復雜度的知識就為大家分享到這里啦，作者能力有限，如果有什么講的不夠清楚或者有錯的地方還請多多在評論區指出，我們下次再見咯~