一次一個主題,
把演算法真的學進去。
每個主題底下是一組相關的演算法。每一篇都有相同的結構:概念、步驟、可以親手按的互動示範、程式碼,以及對應的練習題。
資料結構
7 個主題 · 29 篇怎麼衡量一個演算法好不好。全站的共同語言。
用在:為什麼程式在測試機很快、上線就超時、為什麼動態陣列的 push 算 O(1)、把問題交給「更小的自己」
最基本的兩種容器:靠位置存取,或靠鍵存取。
用在:資料庫的快取與 Session、「這個字母出現幾次」、報表的區間加總、影像與棋盤
用指標把節點串起來。插入刪除 O(1),但不能跳著存取。
用在:瀏覽器的上一頁/下一頁、LRU 快取、判斷有沒有環
後進先出與先進先出。順序本身就是資訊。
用在:編輯器的括號配對與 undo、印表機與訊息佇列、股價「下一次比今天高是哪天」、監控儀表板的視窗最大值
隨時拿到最大或最小的那個,只要 O(log n)。
用在:作業系統的工作排程、熱門文章 Top 10、即時中位數
沒有環的階層結構。遞迴在這裡最自然。
用在:檔案系統與網頁 DOM、資料庫索引與有序集合、搜尋列的自動補全、即時排行與區間統計
怎麼在程式裡存一張圖,以及怎麼快速回答「連在一起嗎」。
用在:社群網路的好友關係、網路是否還連通、相片裡的人臉分群
演算法
10 個主題 · 64 篇把資料排好順序。從 O(n²) 到 O(n log n),比較的邊界在哪裡。
用在:電商與排行榜、資料庫的 ORDER BY 與外部排序、排序是很多演算法的前置、整數資料的特殊情況
在資料裡找東西。有序的資料能讓每一步砍掉一半。
用在:git bisect 找出壞掉的 commit、「最少要多快才來得及」、監控系統的「過去 5 分鐘平均」、有序陣列裡找兩數之和
把所有可能都試一遍,但走不通就立刻回頭。
用在:自動排課與座位安排、密碼強度與組合列舉、解數獨與填字遊戲
切成小塊各自解決,再把答案合起來。
用在:為什麼切一半就能變快、加密與大數運算、統計「有多少對是反的」
每一步都選當下最好的。什麼時候這樣做會是全域最佳?
用在:會議室與課表排程、zip 與 JPEG 裡的壓縮、找零與作業系統排程、能不能跳到終點
從走訪開始,延伸到最短路徑、相依順序與連通性。
用在:地圖導航、社群平台的「你可能認識」、套件安裝與編譯順序、鋪設網路線路
把大問題拆成重疊的子問題,記住答案就不用重算。
用在:拼字檢查與自動校正、Git diff 與版本比對、預算與資源分配、為什麼不能只用遞迴
比對、搜尋與雜湊。前綴函數是這裡的關鍵工具。
用在:編輯器的 Ctrl+F 與 grep、抄襲與重複內容偵測、DNA 序列分析、搜尋引擎的關鍵字比對
直接操作 0 與 1。又快又省,還能表示集合。
用在:權限與功能開關、找出落單的那一個、網路遮罩與雜湊
演算法題裡最常用到的幾個數學工具。
用在:HTTPS 背後的 RSA、螢幕比例與分數化簡、「有幾種走法」