線上教材：資料結構使用蟒蛇

比較演算法好壞的標準之一是時間複雜度，當然你也可以做空間複雜度的比較，概念非常相似，在本篇就不贅述。而在定義時間複雜度之前，我們要先提及兩個在分析上的預設觀念：

比較處理同一個問題的不同演算法時，預設考慮輸入數量 n 很大的狀況：例如以不同的排序演算法而言，要被排序的陣列長度 n 比較短的時候，可能會是演算法 A 跑得比較快；但是若當 n 夠大的時候，演算法 B 會穩定勝出；則在尚未被告知 n 是多少的情況下，我們會先說演算法 B 比較好。

比較同一個演算法面對不同輸入的狀況時，優先關注「平均而言」和「最壞」的狀況，並在必要時明確地表示出你正在考慮的狀況：例如在前一節中，我們看到 insertion sort 在最好、平均和最壞的情況下，花費和次數的乘積加起來分別是一次、二次和二次多項式；則此時我們會說 insertion sort 花費和次數的乘積加起來，平均而言是二次多項式。又例如某知名演算法，在最好、平均和最壞的情況下，花費和次數的乘積加起來的 leading term 分別是 n lg n、n lg n 以及 n²，則我們會優先討論平均情況的那個 n lg n，以及最壞情況的 n²。

那麼，我們到底要怎麼比較不同演算法或者不同狀況的時間複雜度呢？你應該已經在數學或程式語言中，學過「<」、「≤」、「==」、「≥」以及「>」這五個符號，而比較時間複雜度也有類似的概念，我們直接來看定義，當你把某個演算法的花費和次數的乘積加起來表示成 n 的函數 f(n)，而你要拿他跟 g(n) 比較時：

記號與用法記號讀法類比的運算定義（一般版）定義（極限版）定義（口語描述版）

f(n) = o(g(n)) Little-oh < o(g(n)) = {f(n): ∀ positive constant c, ∃ n₀ s.t. 0 ≤ f(n) < c * g(n) ∀ n ≥ n₀} lim_{n → ∞} ( f(n) / g(n) ) = 0 對所有正數 c，當 n 夠大的時候，0 ≤ f(n) < c * g(n) 都會成立

f(n) = O(g(n)) Big-oh ≤ O(g(n)) = {f(n): ∃ positive constant c and n₀ s.t. 0 ≤ f(n) ≤ c * g(n) ∀ n ≥ n₀} lim sup_{n → ∞} ( f(n) / g(n) ) < ∞ 可以找到一個固定的正數 c，讓 n 只要夠大的時候，0 ≤ f(n) ≤ c * g(n) 都會成立

f(n) = Θ(g(n)) Big-theta == Θ(g(n)) = {f(n): ∃ positive constant c₁, c₂ and n₀ s.t. 0 ≤ c₁ * g(n) ≤ f(n) ≤ c₂ * g(n) ∀ n ≥ n₀} 0 < lim inf_{n → ∞} ( f(n) / g(n) ), and
lim sup_{n → ∞} ( f(n) / g(n) ) < ∞ 可以找到兩個固定的正數 c₁、c₂，讓 n 只要夠大的時候，0 ≤ c₁ * g(n) ≤ f(n) ≤ c₂ * g(n) 都會成立

f(n) = Ω(g(n)) Big-omega ≥ Ω(g(n)) = {f(n): ∃ positive constant c and n₀ s.t. 0 ≤ c * g(n) ≤ f(n) ∀ n ≥ n₀} lim inf_{n → ∞} ( f(n) / g(n) ) > 0 可以找到一個固定的正數 c，讓 n 只要夠大的時候，0 ≤ c * g(n) ≤ f(n) 都會成立

f(n) = ω(g(n)) Little-omega > ω(g(n)) = {f(n): ∀ positive constant c, ∃ n₀ s.t. 0 ≤ c * g(n) < f(n) ∀ n ≥ n₀} lim_{n → ∞} ( f(n) / g(n) ) = ∞ 對所有正數 c，當 n 夠大的時候，0 ≤ c * g(n) < f(n) 都會成立

在上面的表格中：

雖然在「記號與用法」一欄，我們在表示兩者關係時使用了等號，但因為等號右側是個集合，所以比較正式的寫法是表示「屬於」的「∈」。而在以口語讀出算式時，則該部份讀做「是」或「屬於」都可以。

標示紅色的部分，是為了讓各位容易看出差異或需留意之處，並不是數學上的特殊用途。

因為演算法的執行時間不可能為負數，所以在極限版定義中不另外正式強調；但如果你套用了該定義在演算法分析以外的情況，則可能需要自行留意。

lim sup 以及 lim inf 可以大致想像為數列極限的上下界，而當數列的上下極限相等時，若且唯若此數列收斂。

複雜度的概念，在不同的嚴格程度下有不同的定義；前述的定義，是以本課程分析所需的嚴格程度為主。

這些記號在使用上，有下列慣例。此處以 big-oh 說明如下，但另外四個記號亦同：

界線要盡可能地貼近：例如 n² + 2 * n + 1 = O(2ⁿ + n³) 雖然在數學上是正確的，但一般應寫 n² + 2 * n + 1 = O(n²)。

g(n) 只寫 leading term，並且不加係數：例如 n² + 2 * n + 1 = O(5 * n² + 4 * n + 3) 雖然在數學上是正確的，但一般應寫 n² + 2 * n + 1 = O(n²)。

指數函數中，若有 n 加上某個常數，則常數可省略：例如 2ⁿ⁺¹ = 2 * 2ⁿ = O(2ⁿ)

對數函數中，因為可以換底，所以 log 的底數不影響複雜度：例如 log₁₀ n = lg n / lg 10 = O(lg n)

此外，這些記號有以下性質，雖然這些性質在分析演算複雜度時不一定會直接用上，但若對其有所了解，比較不會在看到不同的寫法時愣住：

遞移性 transitivity

f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))

f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))

f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))

f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))

f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))

反身性 reflexivity：f(n) = Θ(f(n)) = O(f(n)) = Ω(f(n))

對稱性 symmetry：f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n))

對稱轉換 transpose symmetry

f(n) = O(g(n)) ⇔ g(n) = Ω(f(n))

f(n) = o(g(n)) ⇔ g(n) = ω(f(n))

因此，對於先前看過的幾個程式片段，其時間複雜度如下（對於其他演算法的分析，會在後續篇章陸續說明）：
這個的複雜度是 O(n)
# 						Cost	Times
n = 10 #				C1		1
result = 0 #			C2		1
for i in range(10): # 	C3		n
	result += i + 1 #	C4		n
這個的複雜度是 O(1)
# 							Cost	Times
n = 10 #					C1		1
result = n * (n + 1) / 2 #	C2		1
這個的複雜度是 O(n³)
# 											Cost	Times
for i in range(n): #						C1		n
	for j in range(n): # 					C2		n * n
		for k in range(n): #				C3		n * n * n
			c[i, j] += a[i, k] * b[k, j] #	C4		n * n * n
這個的複雜度，在最好、平均、最壞的狀況分別是 O(n)、O(n²)、O(n²)
# 										Cost	Times
n = len(a) #							C1		1
for i in range(1, n): # 				C2		n - 1
	key = a[i] # 						C3		n - 1
	j = i - 1 # 						C4		n - 1
	while j >= 0 and a[j] > key: #		C5		Σ_i t_i
		a[j + 1] = a[j] #				C6		Σ_i (t_i - 1)
		j -= 1 #						C7		Σ_i (t_i - 1)
	a[j + 1] = key #					C8		n - 1
這個的複雜度是 O(lg n)
# 										Cost	Times
low = 0 #								C1		1
high = len(a) - 1 #						C2		1
result = -1 #							C3		1
while low <= high: #					C4		t s.t.  n // 2 ** t == 1 ==> t = lg n
	mid = (low + high) // 2 #			C5		lg n
	if a[mid] == target: #				C6		lg n
		result = mid #					C7		1
		break #							C8		1
	elif a[mid] < target: #				C9		s
		low = mid + 1 #					C10		s
	else: #								C11		lg n - s - 1
		high = mid - 1 #				C12		lg n - s - 1
在上述的說明中，你可能會發現，應該要用 Θ(g(n)) 來描述會比較精確；但在實務上，為了書寫與溝通方便等理由，通常會優先使用 O(g(n))。

複雜度的分析，在實務上也可以幫助你在面對特定問題時，選擇或設計適當的演算法，以求在可接受的時間內處理問題。以目前（2026 年八月）的一般家用電腦規格來說：

n 小於 10 時，O(n!) 的演算法有機會處理該問題。

n 在 10~20 左右時，O(2ⁿ) 的演算法有機會處理該問題。

n 在大約 10³ 以內時，可試試看 O(n³) 或 O(n²) 的演算法。

n 在大約 10⁵ 或 10⁶ 以內時，要試著設計出 O(n lg n) 或 O(n) 的演算法。

n 在 10⁷ 以上時，可能會需要 O(lg n) 甚至更低複雜度的演算法。

上述的說明，也同時代表了複雜度高低的排序：O(n!) > O(2ⁿ) > O(n³) > O(n²) > O(n lg n) > O(n) > O(lg n) > O(1)。其中的「>」是「成長較快」的口語表達，比較嚴謹的數學符號應該是「⊋」，代表左邊的集合包含了右邊，且左右兩者不相等，專業講法為「左邊是右邊的真超集」。

而至於 Python 當中，常用內建功能的時間複雜度則列出如下：

串列：

in：需要看過所有元素，為 O(n)。

append：很倒楣的狀況是 O(n)，但平均下來而言，每次呼叫是 O(1)。

pop：視 pop 位置後面還有幾個元素而定，例如 pop 尾端是 O(1)，pop 頭端是 O(n)。

sort：內部混合了多種方法，但整體而言是 O(n lg n)。

字典與集合：

字典的 get 和 del：處理雜湊表（有興趣的同學請自行了解），可視為 O(1)。

兩者的 in：查詢雜湊表，可視為 O(1)。

記號與用法	記號讀法	類比的運算	定義（一般版）	定義（極限版）	定義（口語描述版）
f(n) = o(g(n))	Little-oh	<	o(g(n)) = {f(n): ∀ positive constant c, ∃ n₀ s.t. 0 ≤ f(n) < c * g(n) ∀ n ≥ n₀}	lim_{n → ∞} ( f(n) / g(n) ) = 0	對所有正數 c，當 n 夠大的時候，0 ≤ f(n) < c * g(n) 都會成立
f(n) = O(g(n))	Big-oh	≤	O(g(n)) = {f(n): ∃ positive constant c and n₀ s.t. 0 ≤ f(n) ≤ c * g(n) ∀ n ≥ n₀}	lim sup_{n → ∞} ( f(n) / g(n) ) < ∞	可以找到一個固定的正數 c，讓 n 只要夠大的時候，0 ≤ f(n) ≤ c * g(n) 都會成立
f(n) = Θ(g(n))	Big-theta	==	Θ(g(n)) = {f(n): ∃ positive constant c₁, c₂ and n₀ s.t. 0 ≤ c₁ * g(n) ≤ f(n) ≤ c₂ * g(n) ∀ n ≥ n₀}	0 < lim inf_{n → ∞} ( f(n) / g(n) ), and lim sup_{n → ∞} ( f(n) / g(n) ) < ∞	可以找到兩個固定的正數 c₁、c₂，讓 n 只要夠大的時候，0 ≤ c₁ * g(n) ≤ f(n) ≤ c₂ * g(n) 都會成立
f(n) = Ω(g(n))	Big-omega	≥	Ω(g(n)) = {f(n): ∃ positive constant c and n₀ s.t. 0 ≤ c * g(n) ≤ f(n) ∀ n ≥ n₀}	lim inf_{n → ∞} ( f(n) / g(n) ) > 0	可以找到一個固定的正數 c，讓 n 只要夠大的時候，0 ≤ c * g(n) ≤ f(n) 都會成立
f(n) = ω(g(n))	Little-omega	>	ω(g(n)) = {f(n): ∀ positive constant c, ∃ n₀ s.t. 0 ≤ c * g(n) < f(n) ∀ n ≥ n₀}	lim_{n → ∞} ( f(n) / g(n) ) = ∞	對所有正數 c，當 n 夠大的時候，0 ≤ c * g(n) < f(n) 都會成立