不復雜的時間復雜度

首先，為什么會有「時間復雜度」和「空間復雜度」這兩個概念呢？
人在做任何事情時，都希望投入最少時間、金錢或精力等就能獲得最佳收益，而在針對問題設計演算法時，人們同樣也希望花費最少時間，占用最少存盤空間來解決問題，因此，就有了「時間復雜度」和「空間復雜度」兩項指標來分別衡量演算法在時間維度上的效率和空間維度上的效率，演算法解決問題用時越短，時間維度上的效率越高；占用存盤空間越少，空間維度上的效率就越高，

在這一講中，我們將先討論「時間復雜度」這一概念，

大O表示法

小白同學：衡量在時間維度的效率的話很簡單呀，直接把演算法寫出來跑一遍，計時一下運行了多少時間就好了！

但仔細一想，很快就能發現這種“馬后炮”方法的不足：運行的機器硬體，實作的編程語言以及作業系統等等因素都會影響運行的時間，而我們希望的是衡量演算法時間效率的指標僅僅只由演算法本身和資料規模大小來決定，所以這種“馬后炮”方法并不能用來衡量演算法在時間效率上的優劣，

那有沒有什么辦法能讓我們用“肉眼”就能看出一段代碼的執行時間呢？

先看下面這一段代碼，

int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; i++) {
       sum = sum + i;
   }
   return sum;
}

我們用\(T(n)\)代表代碼的執行時間，并假設每條陳述句的執行時間均為\(unitTime\)，以上陳述句的總執行次數為\(1+1+2 \times n+1\)，即\(2n + 3\)次，那么\(T(n) = unitTime \times (2n+3)\)，若用大O表示成正比的關系，那么該運算式就可以記為\(T(n) = O(2n + 3)\)，再把大O括號內的式子用\(f(n)\)表示，那么就是\(T(n) = O(f(n))\)，該式子表示這段代碼的總執行時間\(T(n)\)與式子\(f(n)\)成正比，這就是大O時間復雜度表示法，

我們可以看到上面的計算都只是粗略的估計，所以大O表示法也只是用于表示代碼執行時間隨資料規模增長的變化趨勢，所以它也叫做「漸進時間復雜度」，簡稱時間復雜度，這里的“漸進”就是指資料越來越大，趨近于極限的意思，

既然表示的只是變化趨勢，那么很多細枝末節的東西就可以被忽略，所以我們只需要抓住\(f(n)\)中影響力最大的因子即可（通常為最高次項），顯然上述代碼中影響力最大的因子是\(n\)（系數可以忽略），那么剛才的式子我們就可以直接記為\(T(n) = O(n)\)，表示代碼的執行時間和資料規模大小成正比，

剛才我們是通過數出所有代碼的總執行次數，再將最高次項去掉系數得出大O時間復雜度，那既然不需要再去計算那種細枝末節的東西，有沒有更簡單直接的方式來得出一段代碼的時間復雜度呢？
答：有的，直接關注代碼中回圈執行次數最多的那段代碼即可，

例如，在剛才的例子中，第4行代碼和第5行代碼顯然就是回圈執行次數最多的那段代碼，那么\(T(n) = O(2n)\)，去掉系數，即可快速得出\(T(n) = O(n)\)，

幾種常見的時間復雜度量級

在上一小節中，我們見到了量級為線性階（linear）的時間復雜度，常見的時間復雜度量級還包括常數階（constant），對數階（logarithmic），平方階（quadratic），立方階（cubic），指數階（exponential），階乘階（factorial），

常數階\(O(1)\)

int a = 1;
int b = 2;
int c = 3;

小白同學：總共3行代碼，那時間復雜度不是\(O(3)\)嗎，怎么會是\(O(1)\)呢？
答：\(O(1)\)是用來表示代碼的執行時間為常數，即代碼的執行時間并不隨著n的增大而增長，這類的代碼即便有10000行代碼，時間復雜度也仍為\(O(1)\)，

對數階\(O(logn)\)、線性對數階\(O(nlogn)\)

while (n > 1)
    n = n/2

這段代碼不斷將 \(n\) 自除以2來接近1，假設該陳述句的執行次數為\(x\)，則\(\frac{n}{2^x} = 1\)，變換公式可得\(x = log_2n\)，所以這段代碼的時間復雜度為\(O(log_2n)\)，

再看下面代碼，同理，得出其時間復雜度為\(O(log_3n)\)，

while (n > 1)
    n = n/3

可實際上，不論是以 2 為底、以 3 為底，還是以 10 為底，所有對數階的時間復雜度都是記為\(O(logn)\)，為什么呢？
答：因為對數之間是可以相互轉換的，因為\(log_32 \times log_2n = log_3n\)，所以\(O(log_3n) = O(log_32 \times log_2n)\)，而\(log_32\)是個常數，我們在前面也提到過常量系數在大O表示法中是可以被忽略的，所以\(O(log_2n) = O(log_3n)\)，所以在量級為對數階的復雜度里，我們干脆忽略對數的底，統一表示為\(O(logn)\)，

再看這段代碼，

for (int i = 0; i < n; i++) {
  while (n > 1)
    n = n/2
}

將時間復雜度為\(O(logn)\)的代碼執行n遍，即為\(O(nlogn)\)，

平方階\(O(n^2)\)、立方階\(O(n^3)\)

int a = 0;
for (int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        a++;  
    }
}

回圈執行次數最多的代碼為a++，執行次數為\(n^2\)，所以\(T(n) = O(n^2)\)，

立方階同理，只要再多套一層for回圈即可，

指數階\(O(2^n)\)

for (int i = 0; i < 2^n; i++) {
  	n++;
}

階乘階\(O(n!)\)

int factorial(int n) {
    for (int i = 0; i < n; i++) {
				factorial(n - 1);
    }  
}

回圈執行次數最多的陳述句為factorial(n - 1)，在當前 \(n\) 下，會呼叫n次factorial(n - 1)，而在每個 \(n - 1\) 下，又會呼叫n - 1次factorial(n - 2)，以此類推，得執行次數為 \(n \times (n - 1) \times (n - 2) \times ... \times 1\)，即 \(n!\)，

時間效率排名

很明顯，對于相同的資料規模，不同的時間復雜度在時間維度的表現上有著巨大的差異，

時間效率排名為（越靠右越代表演算法的時間效率越低）：\(O(1) < O(logn) < O(n) < O(n^2) < O(n^3) < O(2^n)\)，

最好、最壞以及平均時間復雜度

此外，我們還需要知道，同一段代碼在不同情況下會有不一樣的時間復雜度，讓我們看下面這段代碼，

// Tell whether the array a contains x.
boolean contains(int[] a, x) {
    for (int i = 0; i < a.length; i++) {
        if (x == a[i])
            return true;
    }
    return false
}

首先，執行次數最多的陳述句很明顯為if (x == a[i])，
接著問題來了，假如我們想找的元素x正好就處于陣列的第一個位置，那么無論陣列規模多大，該陳述句的執行次數都為\(1\)，此時\(T(n) = O(1)\)，這種情況就是最好時間復雜度（best-case time complexity）；假如我們想找的元素x不在陣列中，那么這整個陣列都會被遍歷一遍，if (x == a[i])的執行次數為\(n\)，則\(T(n) =O(n)\) ，這種情況就是最壞時間復雜度（worst-case time complexity），我們通常會以最壞的角度來進行時間復雜度的評估，\(\frac{x+y}{y+z}\)

設 \(T_1(n)\), 設\(T_2(n)\), ...分別為所有可能情況下的時間復雜度；設 \(P_1(n)\), \(P_2(n)\), ...為這些對應情況的分布概率，則平均時間復雜度（average-case time complexity）為 \(P_1(n)T_1(n) + P_2(n)T_2(n)+ ...\)

平均時間復雜度通常來說較難計算，因為難以得出各類情況的分布概率，有時為了簡便，會將最好時間復雜度以及最壞時間復雜度相加除以二來得出平均時間復雜度，例如上述代碼的平均時間復雜度可以簡單計算為\(O(\frac{1 + n}{2})\)，即為\(O(n)\)，

\(\Omega\) 表示法

除了大O表示法，你可能還會見過\(\Omega\)表示法和\(\Theta\)表示法，這三類表示法都可以用于表示時間復雜度，但是略有不同，大O表示法\(O(f(n))\)表示的是漸進上界（upper bound），即當資料規模越來越大時，演算法的執行時間最多也不會超過\(M \cdot f(n)\)（M為某一常數），接下來我們將詳細介紹另外兩種表示法，

\(\Omega\)表示法\(\Omega(f(n))\)表示的是漸進下界（lower bound），即當資料規模越來越大時，演算法的執行時間最少也不會小于\(k \cdot f(n)\)（k為某一常數），

那么如何快速地找出一段代碼的漸進下界呢？

先看個例子，\(T(n)\)仍用于代表代碼的總執行時間，并假設每條陳述句的執行時間均為\(unitTime\)，

假設某演算法的總執行時間\(T(n) = unitTime \times (2^n + 5)\)，因為無論\(n\)有多大，\(unitTime \times (2^n + 5) \geq unitTime \times 2^n\)的式子恒成立，那么\(unitTime \times 2^n\)就可被稱為是該演算法在時間維度上的漸進下界，記為\(T(n) = \Omega(2^n)\)（\(unitTime\)為常量系數，可被忽略），表示該演算法的執行時間最少不會小于\(k \cdot 2^n\)（\(k\)為某常數），

所以要想用\(\Omega\)表示法表示代碼的時間復雜度時，總結起來就是先列出\(T(n)\)，\(T(n) = unitTime \times 代碼的總執行次數\)，再糾出\(T(n)\)中的最高次項，將其去掉系數即可，即\(T(n) = \Omega（去掉系數的最高次項）\)，這樣就成功表示了這段代碼在時間維度上的漸進下界了，

\(\Theta\)表示法

\(\Theta\)表示法\(\Theta(f(n))\)表示的是漸進緊確界（tight bound），即當資料規模越來越大時，演算法的執行時間將落在\(k_1 \cdot f(n)\)和\(k_2 \cdot f(n)\)之間（\(k_1,k_2\)均為常數），

那么如何用\(\Theta\)表示法表示演算法的時間復雜度呢？

如果可以用同一個多項式表示一個演算法的O和\(\Omega\)，那么這個多項式就是我們要求的漸進緊確界了，

例如：假設某演算法的\(T(n) = unitTime \times （3n^3 + 2n + 7）\)，那么用大O表示其時間復雜度即為\(O(n^3)\)，用\(\Omega\)表示其時間復雜度即為\(\Omega(n^3)\)，兩種表示法的多項式均為\(n^3\)，那么用\(\Theta\)表示該演算法的時間復雜度即為\(\Theta(n^3)\)，表示該演算法的執行時間落在\(k_1 \cdot n^3\)和\(k_2 \cdot n^3\)之間（\(k_1,k_2\)均為常數），

Q & A

小白同學：「時間復雜度」這個概念和\(O、\Omega、\Theta\)這三種表示法的關系我還是有點搞不清哎？
答：首先，「時間復雜度」這個概念是用來衡量演算法在時間維度上的增長趨勢，這個概念具體可以用\(O、\Omega、\Theta\)這三種表示法表示，若想表示「漸進上界」就用O；想表示「漸進下界」就用\(\Omega\)；想表示「漸進緊確界」就用\(\Theta\)，實際作業中，最常用的是大O表示法，

 
小白同學：怎么感覺三種表示法的求法都一樣？得出來的都是同樣的多項式？
答：確實一樣，基本求法都是最高次項去掉系數，盡管得出來的多項式相同，但是表達的意義卻不盡相同：O表示演算法的執行時間最多不超過\(k_1 \cdot f(n)\)；\(\Omega\)表示演算法的執行時間最少不小于\(k_2 \cdot f(n)\)；\(\Theta\)表示演算法的執行時間在\(k_3 \cdot f(n)\)和\(k_4 \cdot f(n)\)之間，（\(k_1,k_2,k_3,k_4\)均為常數）

 
小白同學：最開始的時候介紹了最好情況最壞情況，怎么后面又來了個漸進上界漸進下界？這兩者是一樣的嗎，漸進上界（upper bound）就指的是最壞情況（worst-case），漸進下界（lower bound）就指的是最好情況（best-case），對嗎？
答：錯誤，上界、下界和最壞、最好情況并不是一回事，讓我們先看下面這個故事（摘選自Khan Academy），

假設小白同學某天被抓進監獄，獄長告訴他只有玩完下面這個游戲才能放他走，

他給小明同學展示了兩個一模一樣的盒子，并告訴他游戲規則如下：

• A盒子有10到20只小蟲子，
• B盒子有30到40只小蟲子，
• 兩個盒子在外觀上一模一樣，所以小明分不清哪個是A盒子，哪個是B盒子，
• 小明必須選出一個盒子，并吃掉里面所有的蟲子，

具體地，A盒子里有17只小蟲子，B盒子里有32只小蟲子，不過小明并不知道，

接下里輪到小明做出選擇了，前提假設小明喜歡少吃點蟲子，

那么對于小明來說，很顯然，最好的情況（best-case）就是選到A盒子，

那在這種場景下，吃到的蟲子最少為10只（下界），最多為20只（上界），

最壞的情況（worst-case）是選到B盒子，

那在這種場景下，吃到的蟲子最少為30只（下界），最多為40只（上界），

所以我們可以看出，無論是最好情況還是最壞情況，兩種情況下都是存在上界和下界的，

同樣也很容易看出，最壞情況里的上界是最最最糟糕的，而最好情況里的下界是最最最好的，

總結

本講介紹了「時間復雜度」這一概念，用它來表示演算法在時間維度上的效率，它不是計算演算法具體耗時的，而是反映演算法在時間維度上的一個趨勢，時間復雜度具體可以用\(O、\Omega、\Theta\)這三種表示法表示，分別表示演算法執行時間的「漸進上界」、「漸進下界」和「漸進緊確界」，此外還介紹了演算法在最好、最壞、平均情況下的時間復雜度以及一些常見的時間復雜度量級，

參考

1. https://www.sohu.com/a/271774788_115128
2. https://mp.weixin.qq.com/s/rMfBC5PA8zIu9bPBYS8zBQ
3. https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation
4. https://blog.csdn.net/qq_41856733/article/details/89034055

創作不易，點個贊再走叭～

標籤：其他

上一篇：【布隆過濾器】過濾器中的戰斗機

下一篇：0131. Palindrome Partitioning (M)