[TOC] ### **算法是什么** 算法（Algorithm）是指用來操作數據、解決程序問題的一組方法。對于同一個問題，使用不同的算法，也許最終得到的結果是一樣的，但在過程中消耗的資源和時間卻會有很大的區別。 ### **如何衡量不同算法之間的優劣？** * 時間維度：是指執行當前算法所消耗的時間，我們通常用「時間復雜度」來描述。 * 空間維度：是指執行當前算法需要占用多少內存空間，我們通常用「空間復雜度」來描述。 #### **時間復雜度** 通用的方法就出來了：「**大O符號表示法**」，即 T(n) = O(f(n)) 例子： ``` for(i=1; i<=n; ++i) { j = i; j++; } ``` **算法的漸進時間復雜度**: 在 大O符號表示法中，時間復雜度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代碼執行次數之和，而 O 表示正比例關系。 >假設每行代碼的執行時間都是一樣的，我們用 1顆粒時間 來表示，那么這個例子的第一行耗時是1個顆粒時間，第三行的執行時間是 n個顆粒時間，第四行的執行時間也是 n個顆粒時間（第二行和第五行是符號，暫時忽略），那么總時間就是 1顆粒時間 + n顆粒時間 + n顆粒時間 ，即 (1+2n)個顆粒時間，即： T(n) = (1+2n)\*顆粒時間，從這個結果可以看出，這個算法的耗時是隨著n的變化而變化，因此，我們可以簡化的將這個算法的時間復雜度表示為：T(n) = O(n) 為什么可以這么去簡化呢，因為大O符號表示法并不是用于來真實代表算法的執行時間的，它是用來表示代碼執行時間的增長變化趨勢的。 所以上面的例子中，如果n無限大的時候，T(n) = time(1+2n)中的常量1就沒有意義了，倍數2也意義不大。因此直接簡化為T(n) = O(n) 就可以了。 #### **時間復雜度量級** ##### 常數階級O(1) 無論代碼執行了多少行，只要是沒有循環等復雜結構，那這個代碼的時間復雜度就都是O(1) ``` int i = 1; int j = 2; ++i; j++; int m = i + j; ``` ##### 線性階O(n) for循環里面的代碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時間復雜度。 ``` for(i=1; i<=n; ++i) { j = i; j++; } ``` ##### **對數階O(logN)** 代碼： ``` int i = 1; while(i<n) { i = i * 2; } ``` 在while循環里面，每次都將 i 乘以 2，乘完之后，i 距離 n 就越來越近了。我們試著求解一下，假設循環x次之后，i 就大于 2 了，此時這個循環就退出了，也就是說 2 的 x 次方等于 n，那么 x = log2^n 也就是說當循環 log2^n 次以后，這個代碼就結束了。因此這個代碼的時間復雜度為：**O(logn)** ##### **線性對數階O(nlogN)** 線性對數階O(nlogN) 其實非常容易理解，將時間復雜度為O(logn)的代碼循環N遍的話，那么它的時間復雜度就是 n \* O(logN)，也就是了O(nlogN)。 就拿上面的代碼加一點修改來舉例： ``` for(m=1; m<n; m++) { i = 1; while(i<n) { i = i * 2; } } ``` ##### **平方階O(n2)** 把 O(n) 的代碼再嵌套循環一遍，它的時間復雜度就是 O(n2) 了。 ``` for(x=1; i<=n; x++) { for(i=1; i<=n; i++) { j = i; j++; } } ``` ##### **立方階O(n3)**、**K次方階O(n^k)** 參考上面的O(n2) 去理解就好了，O(n3)相當于三層n循環 #### **空間復雜度** ##### **空間復雜度 O(1)** 如果算法執行所需要的臨時空間不隨著某個變量n的大小而變化，即此算法空間復雜度為一個常量，可表示為 O(1) ``` int i = 1; int j = 2; ++i; j++; int m = i + j; ``` 代碼中的 i、j、m 所分配的空間都不隨著處理數據量變化，因此它的空間復雜度 S(n) = O(1) ##### **空間復雜度 O(n)** ``` int[] m = new int[n] for(i=1; i<=n; ++i) { j = i; j++; } ``` 第一行new了一個數組出來，這個數據占用的大小為n，這段代碼的2-6行，雖然有循環，但沒有再分配新的空間，因此，這段代碼的空間復雜度主要看第一行即可，即 S(n) = O(n)