本文首發(fā)公眾號(hào)：架構(gòu)精進(jìn)，請(qǐng)移步，排版比較清晰。

經(jīng)常有同學(xué)在 LeetCode 的題解中問(wèn)解法的復(fù)雜度是多少。作為一個(gè)懶人，我一直在「逃避」這個(gè)問(wèn)題，畢竟這東西聽(tīng)起來(lái)就這么「復(fù)雜」。

但本著對(duì)題解認(rèn)真負(fù)責(zé)的態(tài)度（心虛），我想趁此機(jī)會(huì)做一個(gè)總結(jié)。下面我將通過(guò)一些較為經(jīng)典的算法題聊一聊幾種常見(jiàn)的時(shí)間復(fù)雜度。

什么是時(shí)間復(fù)雜度？

算法的時(shí)間復(fù)雜度（Time complexity）是一個(gè)函數(shù)，用于定性描述算法的運(yùn)行時(shí)間。

提出時(shí)間復(fù)雜度的目的是：分析與比較完成同一個(gè)任務(wù)而設(shè)計(jì)的不同算法。

分析算法的結(jié)果意味著算法需要的資源，雖然有時(shí)我們關(guān)心像內(nèi)存，通信帶寬或者計(jì)算機(jī)硬件這類(lèi)資源，但是通常我們想要度量的是計(jì)算時(shí)間。一般來(lái)說(shuō)，通過(guò)分析求解某個(gè)問(wèn)題的幾種候選算法，我們可以選出一種最有效的算法。這種分析可能指出不止一個(gè)可行的候選算法，但是在這個(gè)過(guò)程中，我們往往可以拋棄幾個(gè)較差的算法。 ——《算法導(dǎo)論》

大 O 符號(hào)

時(shí)間復(fù)雜度通常用 大 O 符號(hào)（Big O notation）表示。大 O 符號(hào) 又被稱為漸近符號(hào)，是用于描述函數(shù) 漸近行為。

舉個(gè)例子，假設(shè)我們解決一個(gè)規(guī)模為 n 的問(wèn)題要花費(fèi)的時(shí)間為 T(n)T(n)：

T(n)=4n2−2n+2T(n)=4n2−2n+2

當(dāng) n 不斷增大時(shí)，n2n2 開(kāi)始占據(jù)主導(dǎo)地位，而其他各項(xiàng)可以被忽略，寫(xiě)作 T(n)=O(n2)T(n)=O(n2)。因此時(shí)間復(fù)雜度可被稱為是 漸近 的。

常見(jiàn)復(fù)雜度比較

常見(jiàn)時(shí)間復(fù)雜度比較

常數(shù)時(shí)間

若算法 T(n)T(n) 的上界與輸入大小無(wú)關(guān)，則稱它具有常數(shù)時(shí)間，記作 T(n)=O(1)T(n)=O(1)。

常見(jiàn)的例子有：

• 訪問(wèn)數(shù)組中的單個(gè)元素
• 哈希表

別被循環(huán)所迷惑

例如這道題 有效的數(shù)獨(dú)，需要在 9x9 的格子中判斷數(shù)獨(dú)是否有效。

思路：把行、列和小正方形區(qū)域出現(xiàn)的數(shù)字用哈希表記錄下來(lái)，在遍歷過(guò)程中只要判斷數(shù)字是否在這三個(gè)范圍出現(xiàn)過(guò)就行了，如果出現(xiàn)過(guò)就返回 False。

題解如下：

我們可以看到，雖然題解中用到了如下循環(huán)：

但由于復(fù)雜度始終是 O(9×9)O(9×9)，加上使用哈希表來(lái)判斷元素是否存在，所以算法的復(fù)雜度始為 O(1)O(1)。

對(duì)數(shù)時(shí)間

若 T(n)=O(logn)T(n)=O(logn)，則稱其具有對(duì)數(shù)時(shí)間。

常見(jiàn)例子：

• 二叉樹(shù)相關(guān)操作
• 二分查找

為什么是 logn？

什么是對(duì)數(shù)？

首先，我們復(fù)習(xí)一下 對(duì)數(shù)。

對(duì)數(shù) 是冪運(yùn)算的逆運(yùn)算。假如 x=βyx=βy，那么就有 y=logβxy=logβx。其中：

• ββ 是對(duì)數(shù)的底（基底）
• yy 就是 xx（對(duì)于底數(shù) ββ）的對(duì)數(shù)

那我們說(shuō)一個(gè)算法的復(fù)雜度是 O(logn)O(logn)，那么 lognlogn 這個(gè)對(duì)數(shù)的底數(shù)去哪了？

換底公式

二分查找

線性時(shí)間

如果一個(gè)算法的時(shí)間復(fù)雜度為 O(n)O(n)，則稱這個(gè)算法具有線性時(shí)間。隨著樣本數(shù)量的增加，復(fù)雜度也隨之線性增加。常表現(xiàn)為單層循環(huán)。

來(lái)看一到例題 求眾數(shù)。這里我們用了摩爾投票法，時(shí)間復(fù)雜度為 O(n)O(n)。

線性對(duì)數(shù)（準(zhǔn)線性）時(shí)間

若算法復(fù)雜度為 T(n)=O(nlogn)T(n)=O(nlogn)，則稱這個(gè)算法具有線性對(duì)數(shù)時(shí)間。可以理解為執(zhí)行了 n 次對(duì)數(shù)時(shí)間復(fù)雜度的操作。

有幾種排序算法的平均時(shí)間復(fù)雜度都是線性對(duì)數(shù)時(shí)間，例如：

• 堆排序：前 K 個(gè)高頻元素
• 快速排序：顏色分類(lèi)
• 歸并排序

二次時(shí)間

若算法復(fù)雜度為 T(n)=O(n2)T(n)=O(n2)，則稱這個(gè)算法具有二次時(shí)間，即時(shí)間復(fù)雜度隨著樣本數(shù)量的增加呈平方數(shù)增長(zhǎng)。常表現(xiàn)為雙層循環(huán)。

常見(jiàn)的算法中有一寫(xiě)比較慢的排序算法，例如：

• 冒泡排序
• 選擇排序
• 插入排序

由于涉及的排序算法很多，若一一講解的話就偏離這篇文章的側(cè)重點(diǎn)了。如果大家對(duì)各類(lèi)算法感興趣可以參考：維基百科：排序算法。

算法是生活中的大智慧，而我們都是智慧的受益者。