MIT演算法開放式課程 Lecture 1: Algorithmic Thinking, Peak Finding
這系列是記錄我自己從MIT的開放式課程：Introdution to Algorithms中之所學
相信很多跟我一樣自學程式語言的人很常聽到人講：演算法跟資料結構很重要
但這兩個東西到底要怎麼學？隨便拿一本原文書都是厚厚一本，看完不知道要到民國幾年，而且也不知道重點在哪
看影音課程我認為是個比較好的方法，一來一堂課不到一個小時不會看到恍神，二來有真人講解比較容易理解與抓到重點
這個課程算是非常的淺顯易懂，講師由兩位教授輪流授課，兩位講解得都算很清楚，速度也不會太快
非常適合跟我一樣完全無基礎的人自學
雖然課程中有說他在這堂課使用的語言是Python，但其實只是偶爾會寫幾行這個演算法的Python實作出來，不懂Python也沒什麼影響
我的文章主要是把他每堂課中我認為的重點抓出來，以及補充一些我自己的心得
一些課堂上太細節的東西我就不會寫了以免模糊了焦點
那麼底下就開始進入第一堂課
課程連結：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/
第一堂課沒有講到太多技術性的東西，所以我會花比較多篇幅介紹所謂的複雜度(Complexity)
首先講師提到了什麼是演算法
演算法就是處理一大群輸入資料來得到我們想要的結果的過程
一個演算法我們主要在意的有以下兩點：
Efficient：這應該很好理解，就是演算法的速度，另外也包含記憶體的使用效率
Scalability︰這個詞我想不到比較好的中文翻譯(Google翻譯為可擴展性)，意思就是當輸入資料的數量變得越來越多時，這個演算法的運作情況是否能一樣好，而不會不成比例的變慢
例如資料從一萬個變成兩萬個時，演算法的速度是不是只是從10ms變成20ms
另外我們評斷一個演算法的好壞時，常常用$T(n)$代表一個演算法的效率
$n$是輸入資料的數量，$T(n)$代表這個演算法的複雜度，複雜度又分時間複雜度(計算速度)及空間複雜度(所需記憶體空間)
那這個$T(n)$的單位究竟是什麼呢？例如$T(n)=1$的$1$是什麼意思？
答案是：與輸入資料的大小無關的部分
$T(n)=1$，代表是不管你給的資料量有多大，這個演算法的執行時間永遠都是固定的常數
例如現在輸入資料是一個長度為n的陣列，而我們的目的是要印出這個陣列的某一項(假設這個陣列支援random access)
那麼這個操作執行時間$T(n)$當然就是$T(n)=1$了
因為不論陣列大小多少，我們都只需要印出其中一項，自然執行時間就跟n無關了
常數的大小其實無關緊要，我們更在意的是當$n$變得越來越大時$T(n)$的變化
又例如我們想要找出這個陣列裡面任意一個大於10的數字的位置
在這個情況下若我們採用的演算法是＂從第一個元素開始逐個檢查到最後一個＂
我們的$T(n)$可能等於$1$到$n$中的任何值，那究竟要用哪一個？
這得談到我們在談論演算法的速度時有幾種情況
第一個worst case時的速度
第二個是best case時的速度
第三個是average的速度
在沒有特別提及時，因為輸入資料的狀態可以是任意的，通常我們都是關心演算法在worst case的速度較為實際
在討論複雜度時我們通常不會去追求$T(n)$精確的表達式
比較常採用的是被稱為漸近複雜度(Asymptotic Complexity)的表示法
其中又為$O$(Big-O)、$\Omega$(Omega)、$\Theta$(Theta)
先看看Big-O的正式數學定義：
若且為若存在一組實數$c$及$n_0$，能使得所有$n\geq n_0$的$n$，滿足$cf(n)\geq T(n)$
則我們就說$T(n)\in O(f(n))$
我們可以從$n_0$及$c$這兩個常數去理解Big-O的定義
當$n_0$變得足夠大時，$T(n)$中除了最高冪次以外其餘的項次都可以忽略不計
而$c$的存在則讓我們可以忽略最高冪次的係數
如果$T(n)=5n^2+100n+3$，那麼$T(n)\in O(n^2)$、$O(n^3)$、$O(n^4)$等等
$O(f(n))$意味著一個演算法的上限，當$n$很大時複雜度成長的趨勢不會高於或至多近似於與$f(n)$成比例
$\Omega(f(n))$意味著一個演算法的下限，當$n$很大時複雜度成長的趨勢不會低於或至少近似於與$f(n)$成比例
$\Theta(f(n))$則是以上兩者的交集，當$n$很大時複雜度成長的趨勢近似於與$f(n)$成比例
複雜度的表示法介紹完了，在課堂的後半講師介紹了一個沒什麼實用性，但卻能表達演算法精神的問題：
在一個一維陣列中尋找峰值(peak)的位置
在這邊峰值的定義是若有一個位置其兩側的值都$\leq$它，那麼它就是峰值，若是在邊緣則只要確認一邊即可
根據這個定義，任何一個陣列至少有一個峰值，但若$\leq$變成$\lt$的話就不一定了，各位可以思考看看為什麼
這個問題最直接的解法就是從第一項開始一路找到最後一項
或是如果你夠聰明，知道可以從中間開始往變大的那個方向找，可以將複雜度從$\Theta(n)$降低為$\Theta(n/2)$
比較好的作法是採用演算法中的divide and conquer策略，將一個比較大的問題切割成一個較小的問題，小到其解答為Trivial時，就解決了原來的問題
在這個例子中我們可以從中間的位置開始搜尋，比較其左右兩側的值，比較大的那一側一定存在至少一個峰值
於是我們可以把那一側分離開變成大小只有一半的陣列，再重複一樣的動作，直至找到峰值
這種作法在實作時可以用遞迴寫得很簡潔，每做一次這個動作相當於將$n$減半
也就是$T(n)=T(n/2)+\Theta(1)=T(n/4)+2\Theta(1) ...$
常數項的複雜度代表你在每次切割前所需做的兩個比較
此作法的worst case就是你不斷地分割這個陣列直到大小變成1時才找到峰值，而$T(1)$我們稱作base case，base case就是指不需要再作任何處理即可直接得到解答的情況
從$T(n)$到$T(1)$切割的次數為$lg(n)$(寫$lg$代表以2為底的$log$)，即$T(n)=T(1)+lg(n)\Theta(1) \in O(lg(n))$
一維的陣列我們解決了，現在讓我們把問題推廣的二維的陣列(或稱矩陣)
給定一個大小為$n*m$，要怎麼找出其峰值
最直覺的方法很簡單，從任意一點開始，比較其四周的值比往最大的值移動，直至找到峰值
這種作法稱為貪婪演算法(Greedy Algorithm)，俗稱暴力解，貪婪演算法的精神就是在每一個步驟內都去找到局部最佳解，很直覺也實作起來很簡單
但貪婪演算法的缺點也很明顯，其時間複雜度為$O(n*m)$，於是我們希望能像一維的時候一樣
採用divde and conquer策略將一個大的問題不斷地簡化為較小的問題以求增進速度
首先講師給了一個很簡單很有效率的方法如下：
令$i,j$代表列與行的索引值，從(j=m/2)，也就是中間那一行開始，找到那一行的一維峰值
再由峰值所在的那一列再找一次該列的一維峰值
這樣做的速度僅需一維版本的兩倍，複雜度依然為$O(lg(n))$(這樣寫有個前提是$m$與$n$在同一個order)
但仔細想想很容易就會發現這個演算法得到的答案很可能是錯的，例子在課堂裡面講師有給了幾個
接下來試試看另一個做法，一樣從(j=m/2)的那一行開始，但這次我們要找的不是該行的一維峰值，而是該行的全域最大值，假設他的位置是$(i,j)$
然後比較$(i+1,j)$與$(i-1,j)$與$(i,j)$的值，並往比較大那一半陣列抓出來，再進行一樣的步驟
思考一下為什麼要找到全域最大值而不是一維峰值就好，因為當我們把全域最大值與隔壁行比較時，若隔壁行的值比較大那我們可以確保這個值是比原本那行的全部值都還大
這樣周而復始的操作就越來越往擁有較大值的行靠近，也自然就容易找到峰值了
接下來再分析這個算法的複雜度，先把遞迴關係式寫下$T(n,m)=T(n,m/2)+\Theta(n)$
$\Theta(n)$是因為某一行的全域最大值需要掃描過該行的所有元素
跟一維的一樣，相同的操作我們必須重複$lg(m)$次才能把$m$變成$1$，講師將這稱作base case
於是$T(n)=T(n,1)+lg(m)\Theta(n)=\Theta(nlg2m)$
第一堂課就到這結束了
課堂最後提到他有給學生們四種不同的演算法code要他們分析
但我在Lecture Note裡沒看到，不知道是沒有上傳上去還是放在別的地方
如果有看到的人麻煩告訴我一下！
相信很多跟我一樣自學程式語言的人很常聽到人講：演算法跟資料結構很重要
但這兩個東西到底要怎麼學？隨便拿一本原文書都是厚厚一本，看完不知道要到民國幾年，而且也不知道重點在哪
看影音課程我認為是個比較好的方法，一來一堂課不到一個小時不會看到恍神，二來有真人講解比較容易理解與抓到重點
這個課程算是非常的淺顯易懂，講師由兩位教授輪流授課，兩位講解得都算很清楚，速度也不會太快
非常適合跟我一樣完全無基礎的人自學
雖然課程中有說他在這堂課使用的語言是Python，但其實只是偶爾會寫幾行這個演算法的Python實作出來，不懂Python也沒什麼影響
我的文章主要是把他每堂課中我認為的重點抓出來，以及補充一些我自己的心得
一些課堂上太細節的東西我就不會寫了以免模糊了焦點
那麼底下就開始進入第一堂課
課程連結：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/
第一堂課沒有講到太多技術性的東西，所以我會花比較多篇幅介紹所謂的複雜度(Complexity)
首先講師提到了什麼是演算法
演算法就是處理一大群輸入資料來得到我們想要的結果的過程
一個演算法我們主要在意的有以下兩點：
Efficient：這應該很好理解，就是演算法的速度，另外也包含記憶體的使用效率
Scalability︰這個詞我想不到比較好的中文翻譯(Google翻譯為可擴展性)，意思就是當輸入資料的數量變得越來越多時，這個演算法的運作情況是否能一樣好，而不會不成比例的變慢
例如資料從一萬個變成兩萬個時，演算法的速度是不是只是從10ms變成20ms
另外我們評斷一個演算法的好壞時，常常用$T(n)$代表一個演算法的效率
$n$是輸入資料的數量，$T(n)$代表這個演算法的複雜度，複雜度又分時間複雜度(計算速度)及空間複雜度(所需記憶體空間)
那這個$T(n)$的單位究竟是什麼呢？例如$T(n)=1$的$1$是什麼意思？
答案是：與輸入資料的大小無關的部分
$T(n)=1$，代表是不管你給的資料量有多大，這個演算法的執行時間永遠都是固定的常數
例如現在輸入資料是一個長度為n的陣列，而我們的目的是要印出這個陣列的某一項(假設這個陣列支援random access)
那麼這個操作執行時間$T(n)$當然就是$T(n)=1$了
因為不論陣列大小多少，我們都只需要印出其中一項，自然執行時間就跟n無關了
常數的大小其實無關緊要，我們更在意的是當$n$變得越來越大時$T(n)$的變化
又例如我們想要找出這個陣列裡面任意一個大於10的數字的位置
在這個情況下若我們採用的演算法是＂從第一個元素開始逐個檢查到最後一個＂
我們的$T(n)$可能等於$1$到$n$中的任何值，那究竟要用哪一個？
這得談到我們在談論演算法的速度時有幾種情況
第一個worst case時的速度
第二個是best case時的速度
第三個是average的速度
在沒有特別提及時，因為輸入資料的狀態可以是任意的，通常我們都是關心演算法在worst case的速度較為實際
在討論複雜度時我們通常不會去追求$T(n)$精確的表達式
比較常採用的是被稱為漸近複雜度(Asymptotic Complexity)的表示法
其中又為$O$(Big-O)、$\Omega$(Omega)、$\Theta$(Theta)
先看看Big-O的正式數學定義：
若且為若存在一組實數$c$及$n_0$，能使得所有$n\geq n_0$的$n$，滿足$cf(n)\geq T(n)$
則我們就說$T(n)\in O(f(n))$
我們可以從$n_0$及$c$這兩個常數去理解Big-O的定義
當$n_0$變得足夠大時，$T(n)$中除了最高冪次以外其餘的項次都可以忽略不計
而$c$的存在則讓我們可以忽略最高冪次的係數
如果$T(n)=5n^2+100n+3$，那麼$T(n)\in O(n^2)$、$O(n^3)$、$O(n^4)$等等
$O(f(n))$意味著一個演算法的上限，當$n$很大時複雜度成長的趨勢不會高於或至多近似於與$f(n)$成比例
$\Omega(f(n))$意味著一個演算法的下限，當$n$很大時複雜度成長的趨勢不會低於或至少近似於與$f(n)$成比例
$\Theta(f(n))$則是以上兩者的交集，當$n$很大時複雜度成長的趨勢近似於與$f(n)$成比例
複雜度的表示法介紹完了，在課堂的後半講師介紹了一個沒什麼實用性，但卻能表達演算法精神的問題：
在一個一維陣列中尋找峰值(peak)的位置
在這邊峰值的定義是若有一個位置其兩側的值都$\leq$它，那麼它就是峰值，若是在邊緣則只要確認一邊即可
根據這個定義，任何一個陣列至少有一個峰值，但若$\leq$變成$\lt$的話就不一定了，各位可以思考看看為什麼
這個問題最直接的解法就是從第一項開始一路找到最後一項
或是如果你夠聰明，知道可以從中間開始往變大的那個方向找，可以將複雜度從$\Theta(n)$降低為$\Theta(n/2)$
比較好的作法是採用演算法中的divide and conquer策略，將一個比較大的問題切割成一個較小的問題，小到其解答為Trivial時，就解決了原來的問題
在這個例子中我們可以從中間的位置開始搜尋，比較其左右兩側的值，比較大的那一側一定存在至少一個峰值
於是我們可以把那一側分離開變成大小只有一半的陣列，再重複一樣的動作，直至找到峰值
這種作法在實作時可以用遞迴寫得很簡潔，每做一次這個動作相當於將$n$減半
也就是$T(n)=T(n/2)+\Theta(1)=T(n/4)+2\Theta(1) ...$
常數項的複雜度代表你在每次切割前所需做的兩個比較
此作法的worst case就是你不斷地分割這個陣列直到大小變成1時才找到峰值，而$T(1)$我們稱作base case，base case就是指不需要再作任何處理即可直接得到解答的情況
從$T(n)$到$T(1)$切割的次數為$lg(n)$(寫$lg$代表以2為底的$log$)，即$T(n)=T(1)+lg(n)\Theta(1) \in O(lg(n))$
一維的陣列我們解決了，現在讓我們把問題推廣的二維的陣列(或稱矩陣)
給定一個大小為$n*m$，要怎麼找出其峰值
最直覺的方法很簡單，從任意一點開始，比較其四周的值比往最大的值移動，直至找到峰值
這種作法稱為貪婪演算法(Greedy Algorithm)，俗稱暴力解，貪婪演算法的精神就是在每一個步驟內都去找到局部最佳解，很直覺也實作起來很簡單
但貪婪演算法的缺點也很明顯，其時間複雜度為$O(n*m)$，於是我們希望能像一維的時候一樣
採用divde and conquer策略將一個大的問題不斷地簡化為較小的問題以求增進速度
首先講師給了一個很簡單很有效率的方法如下：
令$i,j$代表列與行的索引值，從(j=m/2)，也就是中間那一行開始，找到那一行的一維峰值
再由峰值所在的那一列再找一次該列的一維峰值
這樣做的速度僅需一維版本的兩倍，複雜度依然為$O(lg(n))$(這樣寫有個前提是$m$與$n$在同一個order)
但仔細想想很容易就會發現這個演算法得到的答案很可能是錯的，例子在課堂裡面講師有給了幾個
接下來試試看另一個做法，一樣從(j=m/2)的那一行開始，但這次我們要找的不是該行的一維峰值，而是該行的全域最大值，假設他的位置是$(i,j)$
然後比較$(i+1,j)$與$(i-1,j)$與$(i,j)$的值，並往比較大那一半陣列抓出來，再進行一樣的步驟
思考一下為什麼要找到全域最大值而不是一維峰值就好，因為當我們把全域最大值與隔壁行比較時，若隔壁行的值比較大那我們可以確保這個值是比原本那行的全部值都還大
這樣周而復始的操作就越來越往擁有較大值的行靠近，也自然就容易找到峰值了
接下來再分析這個算法的複雜度，先把遞迴關係式寫下$T(n,m)=T(n,m/2)+\Theta(n)$
$\Theta(n)$是因為某一行的全域最大值需要掃描過該行的所有元素
跟一維的一樣，相同的操作我們必須重複$lg(m)$次才能把$m$變成$1$，講師將這稱作base case
於是$T(n)=T(n,1)+lg(m)\Theta(n)=\Theta(nlg2m)$
第一堂課就到這結束了
課堂最後提到他有給學生們四種不同的演算法code要他們分析
但我在Lecture Note裡沒看到，不知道是沒有上傳上去還是放在別的地方
如果有看到的人麻煩告訴我一下！
留言
張貼留言