跳转至

複雜度

時間複雜度和空間複雜度是衡量一個算法效率的重要標準。

基本操作數

同一個算法在不同的計算機上運行的速度會有一定的差別，並且實際運行速度難以在理論上進行計算，實際去測量又比較麻煩，所以我們通常考慮的不是算法運行的實際用時，而是算法運行所需要進行的基本操作的數量。

在普通的計算機上，加減乘除、訪問變量（基本數據類型的變量，下同）、給變量賦值等都可以看作基本操作。

對基本操作的計數或是估測可以作為評判算法用時的指標。

時間複雜度

定義

衡量一個算法的快慢，一定要考慮數據規模的大小。所謂數據規模，一般指輸入的數字個數、輸入中給出的圖的點數與邊數等等。一般來説，數據規模越大，算法的用時就越長。而在算法競賽中，我們衡量一個算法的效率時，最重要的不是看它在某個數據規模下的用時，而是看它的用時隨數據規模而增長的趨勢，即 時間複雜度。

引入

考慮用時隨數據規模變化的趨勢的主要原因有以下幾點：

  1. 現代計算機每秒可以處理數億乃至更多次基本運算，因此我們處理的數據規模通常很大。如果算法 A 在規模為 \(n\) 的數據上用時為 \(100n\) 而算法 B 在規模為 \(n\) 的數據上用時為 \(n^2\)，在數據規模小於 \(100\) 時算法 B 用時更短，但在一秒鐘內算法 A 可以處理數百萬規模的數據，而算法 B 只能處理數萬規模的數據。在允許算法執行時間更久時，時間複雜度對可處理數據規模的影響就會更加明顯，遠大於同一數據規模下用時的影響。
  2. 我們採用基本操作數來表示算法的用時，而不同的基本操作實際用時是不同的，例如加減法的用時遠小於除法的用時。計算時間複雜度而忽略不同基本操作之間的區別以及一次基本操作與十次基本操作之間的區別，可以消除基本操作間用時不同的影響。

當然，算法的運行用時並非完全由輸入規模決定，而是也與輸入的內容相關。所以，時間複雜度又分為幾種，例如：

  1. 最壞時間複雜度，即每個輸入規模下用時最長的輸入對應的時間複雜度。在算法競賽中，由於輸入可以在給定的數據範圍內任意給定，我們為保證算法能夠通過某個數據範圍內的任何數據，一般考慮最壞時間複雜度。
  2. 平均（期望）時間複雜度，即每個輸入規模下所有可能輸入對應用時的平均值的複雜度（隨機輸入下期望用時的複雜度）。

所謂「用時隨數據規模而增長的趨勢」是一個模糊的概念，我們需要藉助下文所介紹的 漸進符號 來形式化地表示時間複雜度。

漸進符號的定義

漸進符號是函數的階的規範描述。簡單來説，漸進符號忽略了一個函數中增長較慢的部分以及各項的係數（在時間複雜度相關分析中，係數一般被稱作「常數」），而保留了可以用來表明該函數增長趨勢的重要部分。

一個簡單的記憶方法是，含等於（非嚴格）用大寫，不含等於（嚴格）用小寫，相等是 \(\Theta\)，小於是 \(O\)，大於是 \(\Omega\)。大 \(O\) 和小 \(o\) 原本是希臘字母 Omicron，由於字形相同，也可以理解為拉丁字母的大 \(O\) 和小 \(o\)。

在英文中，詞根「-micro-」和「-mega-」常用於表示 10 的負六次方（百萬分之一）和六次方（百萬），也表示「小」和「大」。小和大也是希臘字母 Omicron 和 Omega 常表示的含義。

大 Θ 符號

對於函數 \(f(n)\) 和 \(g(n)\)，\(f(n)=\Theta(g(n))\)，當且僅當 \(\exists c_1,c_2,n_0>0\)，使得 \(\forall n \ge n_0, 0\le c_1\cdot g(n)\le f(n) \le c_2\cdot g(n)\)。

也就是説，如果函數 \(f(n)=\Theta(g(n))\)，那麼我們能找到兩個正數 \(c_1, c_2\) 使得 \(f(n)\) 被 \(c_1\cdot g(n)\) 和 \(c_2\cdot g(n)\) 夾在中間。

例如，\(3n^2+5n-3=\Theta(n^2)\), 這裏的 \(c_1, c_2, n_0\) 可以分別是 \(2, 4, 100\)。\(n\sqrt {n} + n{\log^5 n} + m{\log m} +nm=\Theta(n\sqrt {n} + m{\log m} + nm)\)，這裏的 \(c_1, c_2, n_0\) 可以分別是 \(1, 2, 100\)。

大 O 符號

\(\Theta\) 符號同時給了我們一個函數的上下界，如果只知道一個函數的漸進上界而不知道其漸進下界，可以使用 \(O\) 符號。\(f(n)=O(g(n))\)，當且僅當 \(\exists c,n_0\)，使得 \(\forall n \ge n_0,0\le f(n)\le c\cdot g(n)\)。

研究時間複雜度時通常會使用 \(O\) 符號，因為我們關注的通常是程序用時的上界，而不關心其用時的下界。

需要注意的是，這裏的「上界」和「下界」是對於函數的變化趨勢而言的，而不是對算法而言的。算法用時的上界對應的是「最壞時間複雜度」而非大 \(O\) 記號。所以，使用 \(\Theta\) 記號表示最壞時間複雜度是完全可行的，甚至可以説 \(\Theta\) 比 \(O\) 更加精確，而使用 \(O\) 記號的主要原因，一是我們有時只能證明時間複雜度的上界而無法證明其下界（這種情況一般出現在較為複雜的算法以及複雜度分析），二是 \(O\) 在電腦上輸入更方便一些。

大 Ω 符號

同樣的，我們使用 \(\Omega\) 符號來描述一個函數的漸進下界。\(f(n)=\Omega(g(n))\)，當且僅當 \(\exists c,n_0\)，使得 \(\forall n \ge n_0,0\le c\cdot g(n)\le f(n)\)。

小 o 符號

如果説 \(O\) 符號相當於小於等於號，那麼 \(o\) 符號就相當於小於號。

小 \(o\) 符號大量應用於數學分析中，函數在某點處的泰勒展開式擁有皮亞諾餘項，使用小 \(o\) 符號表示嚴格小於，從而進行等價無窮小的漸進分析。

\(f(n)=o(g(n))\)，當且僅當對於任意給定的正數 \(c\)，\(\exists n_0\)，使得 \(\forall n \ge n_0,0\le f(n)< c\cdot g(n)\)。

小 ω 符號

如果説 \(\Omega\) 符號相當於大於等於號，那麼 \(\omega\) 符號就相當於大於號。

\(f(n)=\omega(g(n))\)，當且僅當對於任意給定的正數 \(c\)，\(\exists n_0\)，使得 \(\forall n \ge n_0,0\le c\cdot g(n)< f(n)\)。

常見性質

  • \(f(n) = \Theta(g(n))\iff f(n)=O(g(n))\land f(n)=\Omega(g(n))\)
  • \(f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n)))\)
  • \(f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n))\)
  • \(\forall a \neq 1, \log_a{n} = O(\log_2 n)\)。由換底公式可以得知，任何對數函數無論底數為何，都具有相同的增長率，因此漸進時間複雜度中對數的底數一般省略不寫。

簡單的時間複雜度計算的例子

for 循環

1
2
3
4
5
6
7
8
9
int n, m;
std::cin >> n >> m;
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    for (int k = 0; k < m; ++k) {
      std::cout << "hello world\n";
    }
  }
}

1
2
3
4
5
6
n = int(input())
m = int(input())
for i in range(0, n):
    for j in range(0, n):
        for k in range(0, m):
            print("hello world")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int n, m;
n = input.nextInt();
m = input.nextInt();
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < m; ++k) {
            System.out.println("hello world");
        }
    }
}

如果以輸入的數值 \(n\) 和 \(m\) 的大小作為數據規模，則上面這段代碼的時間複雜度為 \(\Theta(n^2m)\)。

DFS

在對一張 \(n\) 個點 \(m\) 條邊的圖進行 DFS 時，由於每個節點和每條邊都只會被訪問常數次，複雜度為 \(\Theta(n+m)\)。

哪些量是常量？

當我們要進行若干次操作時，如何判斷這若干次操作是否影響時間複雜度呢？例如：

1
2
3
4
const int N = 100000;
for (int i = 0; i < N; ++i) {
  std::cout << "hello world\n";
}

1
2
3
N = 100000
for i in range(0, N):
    print("hello world")

1
2
3
4
final int N = 100000;
for (int i = 0; i < N; ++i) {
    System.out.println("hello world");
}

如果 \(N\) 的大小不被看作輸入規模，那麼這段代碼的時間複雜度就是 \(O(1)\)。

進行時間複雜度計算時，哪些變量被視作輸入規模是很重要的，而所有和輸入規模無關的量都被視作常量，計算複雜度時可當作 \(1\) 來處理。

需要注意的是，在進行時間複雜度相關的理論性討論時，「算法能夠解決任何規模的問題」是一個基本假設（當然，在實際中，由於時間和存儲空間有限，無法解決規模過大的問題）。因此，能在常量時間內解決數據規模有限的問題（例如，對於數據範圍內的每個可能輸入預先計算出答案）並不能使一個算法的時間複雜度變為 \(O(1)\)。

主定理 (Master Theorem)

我們可以使用 Master Theorem 來快速求得關於遞歸算法的複雜度。 Master Theorem 遞推關係式如下

\[ T(n) = a T\left(\frac{n}{b}\right)+f(n)\qquad \forall n > b \]

那麼

\[ T(n) = \begin{cases}\Theta(n^{\log_b a}) & f(n) = O(n^{\log_b (a)-\epsilon}),\epsilon > 0 \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b (a)+\epsilon}),\epsilon\ge 0\\ \Theta(n^{\log_b a}\log^{k+1} n) & f(n)=\Theta(n^{\log_b a}\log^k n),k\ge 0 \end{cases} \]

需要注意的是，這裏的第二種情況還需要滿足 regularity condition, 即 \(a f(n/b) \leq c f(n)\)，for some constant \(c < 1\) and sufficiently large \(n\)。

證明思路是是將規模為 \(n\) 的問題，分解為 \(a\) 個規模為 \((\frac{n}{b})\) 的問題，然後依次合併，直到合併到最高層。每一次合併子問題，都需要花費 \(f(n)\) 的時間。

證明

依據上文提到的證明思路，具體證明過程如下

對於第 \(0\) 層（最高層），合併子問題需要花費 \(f(n)\) 的時間

對於第 \(1\) 層（第一次劃分出來的子問題），共有 \(a\) 個子問題，每個子問題合併需要花費 \(f\left(\frac{n}{b}\right)\) 的時間，所以合併總共要花費 \(a f\left(\frac{n}{b}\right)\) 的時間。

層層遞推，我們可以寫出類推樹如下：

這棵樹的高度為 \({\log_b n}\)，共有 \(n^{\log_b a}\) 個葉子，從而 \(T(n) = \Theta(n^{\log_b a}) + g(n)\)，其中 \(g(n) = \sum_{j = 0}^{\log_{b}{n - 1}} a^{j} f(n / b^{j})\)。

針對於第一種情況：\(f(n) = O(n^{\log_b a-\epsilon})\)，因此 \(g(n) = O(n^{\log_b a})\)。

對於第二種情況而言：首先 \(g(n) = \Omega(f(n))\)，又因為 \(a f(\dfrac{n}{b}) \leq c f(n)\)，只要 \(c\) 的取值是一個足夠小的正數，且 \(n\) 的取值足夠大，因此可以推導出：\(g(n) = O(f(n)\))。兩側夾逼可以得出，\(g(n) = \Theta(f(n))\)。

而對於第三種情況：\(f(n) = \Theta(n^{\log_b a})\)，因此 \(g(n) = O(n^{\log_b a} {\log n})\)。\(T(n)\) 的結果可在 \(g(n)\) 得出後顯然得到。

下面舉幾個例子來説明主定理如何使用。

  1. \(T(n) = 2T\left(\frac{n}{2}\right) + 1\)，那麼 \(a=2, b=2, {\log_2 2} = 1\)，那麼 \(\epsilon\) 可以取值在 \((0, 1]\) 之間，從而滿足第一種情況，所以 \(T(n) = \Theta(n)\)。

  2. \(T(n) = T\left(\frac{n}{2}\right) + n\)，那麼 \(a=1, b=2, {\log_2 1} = 0\)，那麼 \(\epsilon\) 可以取值在 \((0, 1]\) 之間，從而滿足第二種情況，所以 \(T(n) = \Theta(n)\)。

  3. \(T(n) = T\left(\frac{n}{2}\right) + {\log n}\)，那麼 \(a=1, b=2, {\log_2 1}=0\)，那麼 \(k\) 可以取值為 \(1\)，從而滿足第三種情況，所以 \(T(n) = \Theta(\log^2 n)\)。

  4. \(T(n) = T\left(\frac{n}{2}\right) + 1\)，那麼 \(a=1, b=2, {\log_2 1} = 0\)，那麼 \(k\) 可以取值為 \(0\)，從而滿足第三種情況，所以 \(T(n) = \Theta(\log n)\)。

均攤複雜度

算法往往是會對內存中的數據進行修改的，而同一個算法的多次執行，就會通過對數據的修改而互相影響。

例如快速排序中的「按大小分類」操作，單次執行的最壞時間複雜度，看似是 \(O(n)\) 的，但是由於快排的分治過程，先前的「分類」操作每次都減小了數組長度，所以實際的總複雜度 \(O(n \log n)\)，分攤在每一次「分類」操作上，是 \(O(\log n)\)。

多次操作的總複雜度除以操作次數，就是這種操作的 均攤複雜度。

勢能分析

勢能分析，是一種求均攤複雜度上界的方法。

求均攤複雜度，關鍵是表達出先前操作對當前操作的影響。勢能分析用一個函數來表達此種影響。

定義「狀態」\(S\)：即某一時刻的所有數據。在快排的例子中，一個「狀態」就是當前過程需要排序的下標區間

定義「初始狀態」\(S_0\)：即未進行任何操作時的狀態。在快排的例子中，「初始狀態」就是整個數組

假設存在從狀態到數的函數 \(F\)，且對於任何狀態 \(S\)，\(F(S) \geq F(S_0)\)，則有以下推論：

設 \(S_1,S_2, \cdots ,S_m\) 為從 \(S_0\) 開始連續做 \(m\) 次操作所得的狀態序列，\(c_i\) 為第 \(i\) 次操作的時間開銷。

記 \(p_i = c_i + F(S_i) - F(S_{i-1})\)，則 \(m\) 次操作的總時間花銷為

\[ \sum_{i=1}^m p_i + F(S_0) - F(S_m) \]

（正負相消，證明顯然）

又因為 \(F(S) \geq F(S_0)\)，所以有

\[ \sum_{i=1}^m p_i \geq \sum_{i=1}^m c_i \]

因此，若 \(p_i = O(T(n))\)，則 \(O(T(n))\) 是均攤複雜度的一個上界。

勢能分析在實際應用中有很多技巧，在此不詳細展開。

空間複雜度

類似地，算法所使用的空間隨輸入規模變化的趨勢可以用 空間複雜度 來衡量。

計算複雜性

本文主要從算法分析的角度對複雜度進行了介紹，如果有興趣的話可以在 計算複雜性 進行更深入的瞭解。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：linehk, persdre
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用