本文首發公眾號：架構精進，請移步，排版比較清晰。
經常有同學在 LeetCode 的題解中問解法的復雜度是多少。作為一個懶人，我一直在「逃避」這個問題，畢竟這東西聽起來就這么「復雜」。
但本著對題解認真負責的態度（心虛），我想趁此機會做一個總結。下面我將通過一些較為經典的算法題聊一聊幾種常見的時間復雜度。
什么是時間復雜度？
算法的時間復雜度（Time complexity）是一個函數，用于定性描述算法的運行時間。
提出時間復雜度的目的是：分析與比較完成同一個任務而設計的不同算法。
分析算法的結果意味著算法需要的資源，雖然有時我們關心像內存，通信帶寬或者計算機硬件這類資源，但是通常我們想要度量的是計算時間。一般來說，通過分析求解某個問題的幾種候選算法，我們可以選出一種最有效的算法。這種分析可能指出不止一個可行的候選算法，但是在這個過程中，我們往往可以拋棄幾個較差的算法。 ——《算法導論》
大 O 符號
時間復雜度通常用 大 O 符號（Big O notation）表示。大 O 符號 又被稱為漸近符號，是用于描述函數 漸近行為。
舉個例子，假設我們解決一個規模為 n 的問題要花費的時間為 T(n)T(n)：
T(n)=4n2−2n+2T(n)=4n2−2n+2
當 n 不斷增大時，n2n2 開始占據主導地位，而其他各項可以被忽略，寫作 T(n)=O(n2)T(n)=O(n2)。因此時間復雜度可被稱為是 漸近 的。
常見復雜度比較
常見時間復雜度比較
常數時間
若算法 T(n)T(n) 的上界與輸入大小無關，則稱它具有常數時間，記作 T(n)=O(1)T(n)=O(1)。
常見的例子有：
- 訪問數組中的單個元素
- 哈希表
別被循環所迷惑
例如這道題 有效的數獨，需要在 9x9 的格子中判斷數獨是否有效。
思路：把行、列和小正方形區域出現的數字用哈希表記錄下來，在遍歷過程中只要判斷數字是否在這三個范圍出現過就行了，如果出現過就返回 False。
題解如下：
我們可以看到，雖然題解中用到了如下循環：
但由于復雜度始終是 O(9×9)O(9×9)，加上使用哈希表來判斷元素是否存在，所以算法的復雜度始為 O(1)O(1)。
對數時間
若 T(n)=O(logn)T(n)=O(logn)，則稱其具有對數時間。
常見例子：
- 二叉樹相關操作
- 二分查找
為什么是 logn？
什么是對數？
首先，我們復習一下 對數。
對數 是冪運算的逆運算。假如 x=βyx=βy，那么就有 y=logβxy=logβx。其中：
- ββ 是對數的底（基底）
- yy 就是 xx（對于底數 ββ）的對數
那我們說一個算法的復雜度是 O(logn)O(logn)，那么 lognlogn 這個對數的底數去哪了？
換底公式
二分查找
線性時間
如果一個算法的時間復雜度為 O(n)O(n)，則稱這個算法具有線性時間。隨著樣本數量的增加，復雜度也隨之線性增加。常表現為單層循環。
來看一到例題 求眾數。這里我們用了摩爾投票法，時間復雜度為 O(n)O(n)。
線性對數（準線性）時間
若算法復雜度為 T(n)=O(nlogn)T(n)=O(nlogn)，則稱這個算法具有線性對數時間。可以理解為執行了 n 次對數時間復雜度的操作。
有幾種排序算法的平均時間復雜度都是線性對數時間，例如：
- 堆排序：前 K 個高頻元素
- 快速排序：顏色分類
- 歸并排序
二次時間
若算法復雜度為 T(n)=O(n2)T(n)=O(n2)，則稱這個算法具有二次時間，即時間復雜度隨著樣本數量的增加呈平方數增長。常表現為雙層循環。
常見的算法中有一寫比較慢的排序算法，例如：
- 冒泡排序
- 選擇排序
- 插入排序
由于涉及的排序算法很多，若一一講解的話就偏離這篇文章的側重點了。如果大家對各類算法感興趣可以參考：維基百科：排序算法。
算法是生活中的大智慧，而我們都是智慧的受益者。
