已發布·持續改進
Algorithm
學習用大 O 符號分析演算法的執行時間與記憶體如何隨輸入規模成長，並透過實際量測來驗證分析結果。
複雜度分析描述的是：當輸入變大時，演算法所需的時間與記憶體會成長多少。它不使用會隨硬體與語言改變的秒數，而是把基本操作次數寫成輸入規模 n 的函數，只保留最高階的項。結果以漸近符號表示：大 O 表示上界，大 Ω 表示下界，大 Θ 表示緊確界。
資料量一大，不同成長階之間的差距就會超過任何常數倍，這正是複雜度分析重要的原因。處理一千個元素沒問題的 O(n²) 程式碼，面對一百萬個元素可能要跑上好幾個小時，而 O(n log n) 的程式碼幾秒鐘就能完成。選擇資料結構、解讀程式題的輸入範圍、在程式碼審查中找出隱藏成本、估計系統能否擴展，都需要複雜度分析。
先從數清簡單迴圈的操作次數開始，熟悉常見的複雜度類別：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 與 O(n!)。接著學習最佳、平均與最差情況，攤銷分析，空間複雜度，以及用主定理求解遞迴式。學習過程中要養成用倍增實驗檢驗分析的習慣：分別在 n 與 2n 下計時，再比較兩者的比值。
O、Ω 與 Θ 忽略常數倍與低階項，分別給出成長速度的上界、下界與緊確界。
依序執行的程式碼把成本相加，巢狀迴圈把成本相乘，每一步把問題規模減半就會得到對數。
把一連串操作的總成本平均到每次操作上。這就是動態陣列附加元素偶爾要整體複製，卻仍是 O(1) 的原因。
輔助記憶體與遞迴深度同樣計入成本，分治演算法的遞迴式可以用主定理求解。
腳本用兩種方法解決同一個問題：檢查所有數對，或只走訪一次並用字典記住已經看過的值。用 timeit 在 n = 500、1,000、2,000 時分別計時，可以看到 n 每增加一倍，平方版本大約慢 4 倍，線性版本大約慢 2 倍。
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.py共六章，帶你從安裝一步步認識 複雜度分析 的核心概念。
在這裡提問、分享經驗，交流關於 複雜度分析 的看法。
還沒有討論。來發起第一則吧。
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。