鐵人檔案
一些經典的傳統演算法，在資料量逐漸變大、一台電腦不足以負擔全部的計算量的時候，加入一些新的想法和新的觀察，便能夠提昇效率、解決問題。我想要試著分享一些不同的計算模型、以及在這些計算模型底下大家對傳統的演算法所作的修改。
目標，當然就是努力寫完 30 天份量的內容~(￣▽￣)~！
今天來跟大家聊聊動態規劃當中的一大經典：最長嚴格遞增子序列 Longest Increasing Subsequence：給你 n 個不相同的數字排成一列，對於...
圖論上的拓撲排序 今天我們來討論討論在圖（Graph）上面的平行演算法。一個圖，是由一些節點（通常被稱為 Vertex 或 Node）以及一些連接兩個點之間的邊...
Work Optimality 前天我們得到一個 時間複雜度的最長嚴格遞增子序列演算法，其中 輸入序列長度、 LIS 的長度、 處理器的數量。但這個演算法在...
線上計算模型與先前介紹的幾種計算模型（隨機存取模型、外部存取模型、平行計算模型）不太一樣。線上計算模型主要聚焦在資料的變化，而非計算工具的改變。 Online...
今天來講講眾所皆知、經典到不能再經典的、除了陣列以外的線性資料結構代表：堆疊和佇列。堆疊 (Stack) 是一種先進後出的資料結構，它支援 push() 和 p...
對於一個線上計算模型的問題來說，如果我們說每一個操作的均攤時間是 f(n)，那麼對於任意「從頭開始」的 m 個操作來說，花費的總時間不能超過 。感覺有一點像是說...
今天來試試看農場標題XD 在分析某個演算法或資料結構 A 的時候，如果我們能找到另一個相似的資料結構 B 來描述這個資料結構發生的事情，那麼分析效能的方法也可以...
如果現在有一個大小為 2N 的空陣列，然後連續進行加入 N 筆資料的操作。這些資料都有一個主要的鍵值可以拿來比較大小。但是插入資料的順序並不固定。在資料逐漸一筆...
如果能夠事先得知未來的所有 update，設計出對應的演算法，這就叫做「離線演算法」。顯然在能夠得知未來 update 的情形下，總是可能得出更有效率的演算法。...
為了最後十天的內容，我們今天先來聊一下隨機演算法。絕對不是拖台前，絕對不是，絕對（被拖走）。 假想一下，我們有真正的隨機位元產生器。每詢問一次這個產生器，拿到...
