演算法建置的基礎


人們通常會用建置軟體來解決問題,但有時候太專注於解決問題而並不會去思考是否已經有解決方法的存在。即使在知道可以解決相關問題的解法時,也不能夠確定是否為最佳解。

許多工程師會在網路或是書上尋找演算法,怎麼去針對問題並且快速尋找到正確且快速的演算法才是重點。

最佳、平均與最糟情況分析

其實對於許多問題來說,並不存在絕對最佳解的演算法。演算法的選用取決於:清楚明白需要解決的問題與可能作為實例內容的淺在機率分布,以及考量演算法的行為。

為了提供某些指引,演算法通常會以三種常見的情況來呈現:

最糟情況(Worst Case)

針對演算法顯現的最糟執行行為。通常是由演算法設計師描述輸入內容的屬性,而這些屬性會阻礙演算法的高校執行。

平均情況(Average Case)

針對隨意問題實例執行演算法而定義的預期行為。因為某些特殊情況,需要較多的時間完成處理,但十之八九不會發生這樣的情形。這種情況是一般會抱有的期待的內容。

最佳情況(Best Case)

針對特定問題而有最佳執行其行為的演算法。對於這些實例問題而言,演算法所做的工作量是最少的。事實上,最佳情況的發生率並不高。

簡單的演算法範例:

其中所有變數用小寫字元命名,而陣列則用大寫字母。 而虛擬碼中的內容以縮牌來描述條件 if 與迴圈 for 和 while 的區域範圍。

圖示範例

常見的演算法作法

我們必須要了解用來解決問題的主要策略。 常見的做法:

  • 貪婪法
  • 分治法
  • 動態規劃法 等。

以上會在以後的文章中詳細介紹。


圖片
圖片
圖片
圖片
圖片
圖片
(使用 Facebook 留言外掛程式 留言無法滿足本網站參加活動之資格,僅供非會員討論使用)
互動地圖
interactive taiwan map