iT邦幫忙

2021 iThome 鐵人賽

DAY 2
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 2

Day-2 演算法介紹

演算法(Algorithms)

大致上來說,演算法為具有明確定義的計算過程,根據輸入得到不同的輸出,演算法就是一個將輸入變成輸出的一連串的計算過程,且須要具備五個特性。
輸入 + 演算法 = 輸出

來源:http://ms2.ctjh.ntpc.edu.tw/~luti/107-2/images/01.jpeg

  1. 輸入(input):演算法會有零或一個輸出。
  2. 輸出(output):演算法會有一個或多個輸出。
  3. 有限性(finiteness):演算法應在有限的步驟內完成。
  4. 明確性(definiteness):演算法的每一個步驟應明確而不含糊的。
  5. 有效性(effectiveness):演算法的每一個步驟應可被執行且有效。

一個演算法雖然我們非常注重他的效能,但也有一些比效能更為重要的議題需要注意

  • 正確性(Correctness)
  • 簡潔性(Simplicity)
  • 可維護性(Maintainability)
  • 穩定性(Stability)
  • 模組化(Modularity) : 讓我們只要修改局部程式碼,就能改變其功能
  • 安全性(security) :
  • 可擴充性(Scalability)

舉例,Java雖然比C效率慢了許多,但由於提供物件導向和異常檢查等功能,我們願意犧牲一些效能換取到這些東西。

我們也可以將演算法是為解決特定問題的工具,例如我們要將一連串的沒有順序的數字進行排序,由小排到大,這是一個非常常見的問題,我們可以試著正式定義一下這個問題。

演算法問題定義

Input: 一連串正整數,從https://chart.googleapis.com/chart?cht=tx&chl=a_1https://chart.googleapis.com/chart?cht=tx&chl=a_n 所構成的集合{https://chart.googleapis.com/chart?cht=tx&chl=%20%7B%20a_1%2Ca_2%2C...%2Ca_n%7D}
Output: 一連串重新排列的正整數 {https://chart.googleapis.com/chart?cht=tx&chl=%7B%20a_1'%2Ca_2'%2C....%2Ca_n'%20%7D},且 https://chart.googleapis.com/chart?cht=tx&chl=a_1'%20%3C%3D%20a_2'%20%3C%3D%20...%20%3C%3D%20a_n'

舉例來說,給定一連串正整數集合 {https://chart.googleapis.com/chart?cht=tx&chl=%7B%2031%2C41%2C59%2C26%2C41%2C58%20%7D},經過排序演算法會得到輸出
{ https://chart.googleapis.com/chart?cht=tx&chl=26%2C31%2C41%2C41%2C58%2C59 }。對於這樣的輸入,我們稱為這個輸入為排序問題的實例(instance),一般來說,一個問題的實例由輸入所構成,且這些輸入需要滿足這個演算法的輸入條件,以這個例子來說,輸入的條件為正整數所構成的集合,我們給定的實例就必須皆為正整數。

要使用哪一種演算法,會取決於我們輸入的多寡,或是根據電腦架構等因素,會影響到我們演算法的選擇。

一個演算法要說他是正確的,必須要有以下條件 : 對於每一個輸入的實例,都會輸出如演算法預期的輸出,且在輸入完成時,該演算法就會隨之停止。那這個演算法就可以稱為能夠解決某問題的正確演算法。對於一個不正確的演算法來說,會發生在輸入完成後,演算法卻沒有停止,或是輸出結果不符合預期。

要描述一個演算法,我們可以直接使用虛擬碼進行描述,或是程式碼,HDL等,唯一需要遵守的原則就是必須精確的描述每一個計算步驟的行為。

資料結構

資料結構是一種儲存資料的方式,將這些資料以特定的方式進行阻止以方便我們進行修改和存取。當然,沒有一種資料結構可以有效率的達成我們所有的目的,因此了解每一種資料結構的優勢和劣勢是十分重要的。

演算法效率(Algorithms Efficiency)

一個問題我們設計了不同的演算法是因為在不同的輸入,硬體或是軟體條件之下,會有不同的效率。

舉例來說,針對排序,我們知道有插入排序演算法(insertion sort),在排列n個物件的情況所需花費的時間大約為https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2https://chart.googleapis.com/chart?cht=tx&chl=c_1為常數,且不受到n的影響。也就是說,這個演算法所需花費的時間大約和https://chart.googleapis.com/chart?cht=tx&chl=n%5E2呈線性關係。

第二種為合併排序法(merge sort),所需花費的時間大約為https://chart.googleapis.com/chart?cht=tx&chl=c_2nlg_nhttps://chart.googleapis.com/chart?cht=tx&chl=c_2為常數,且不受到n的影響。(https://chart.googleapis.com/chart?cht=tx&chl=lg的意思為https://chart.googleapis.com/chart?cht=tx&chl=log_2)

我們假設插入排序法需要的時間為https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2,合併排序法要花費的時間為https://chart.googleapis.com/chart?cht=tx&chl=c_2nlg_n,我們試著分析這兩種演算法所需要花費的時間。

一般來說,插入排序法的常數https://chart.googleapis.com/chart?cht=tx&chl=c_1,會小於合併排序法的https://chart.googleapis.com/chart?cht=tx&chl=c_2。插入排序法所需要的時間受到n所影響,合併排序法受到https://chart.googleapis.com/chart?cht=tx&chl=log_n所影響,我們可以試著比較,如果https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%2010時,https://chart.googleapis.com/chart?cht=tx&chl=lg_n大約為3.2,https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%201000時,https://chart.googleapis.com/chart?cht=tx&chl=lg_n大約為10,當https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%201000000時,https://chart.googleapis.com/chart?cht=tx&chl=lg_n大約為20。我們可以看到在n足夠大時,合併排序法所花費的時間相較於插入排序法要少的非常多,但在n較小時,反而插入排序法比合併排序法還要來的快,因為常數的關係,n夠大時,補償了常數所產生的差異。不論https://chart.googleapis.com/chart?cht=tx&chl=c_1https://chart.googleapis.com/chart?cht=tx&chl=c_2小多少,一定會在測資達到n筆時,合併排序法的速度大於插入排序法。

我們假設在一個環境下,有兩部電腦,一台為A電腦,速度非常的快,執行插入排序法。另一台為B電腦,速度比A電腦還要慢,執行合併排序法。讓這兩部電腦去針對一個陣列進行排序,陣列中有一千萬個元素,假定A電腦每一秒鐘可以處理https://chart.googleapis.com/chart?cht=tx&chl=10%5E%7B10%7D 筆指令,B電腦每一秒鐘可以處理https://chart.googleapis.com/chart?cht=tx&chl=10%5E7筆指令,所以,大致上我們可以說A電腦比B電腦快了1000倍。我們可以大致上計算一下A電腦和B電腦所需要花費的時間,如下圖所示


由此可見,A電腦需要超過5.5個小時才能夠完成排序的工作,而B電腦需要的時間只需要20分鐘以內就能夠完成排序的工作,可見一個好的演算法的重要性。

在資料量足夠大時,電腦效能帶來的影響大約就是一個常數因子而已,

對於θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)和θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E3),總會存在一點n使得θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E3)的增長率大於θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)

但這也不表示我們棄用一些低速的演算法,假設n要足夠大時,才會導致θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E3)的增長率大於θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2),而這個n大到電腦無法負荷,也就是電腦的效能根本達不到n這樣的資料量處理,這時候我們就會考慮使用這些低速的演算法,我們可以看到在資料規模夠小時,θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)是要比θhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E3)來的更加快速。

(p.s : 編輯器居然不支援LaTex...,還是我的問題XD 麻煩底下留言告知 感恩~)
參考資料: Introduction to algorithms 3rd


上一篇
Day-1 簡介與參賽動機
下一篇
Day-3 insertion sort與循環不變式
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言