演算法討論-第一場討論:
演算法的最基礎

演算法學習 - HackMD

演算法學習

最近原先想要參加有關演算法的線上課程,結果好像沒有參加到╮(╯_╰)╭。
為了彌補這份失敗,接下來幾天都是演算法強化日。有興趣的人一起學習吧。

什麼是演算法

首先不免熟的甚麼飾演算法呢?
關於這點最簡單最快速的就是維基百科這句

維基百科: 經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態

白話一點:演算法就是透過非無限循環不含糊的計算出一個結果
還是不明白嗎?
我們可以先回憶一下小時候我們上數學課解題目,最後我們不是會用一行又一行的算式解出題目嗎?那個算式就是演算法表現的一種。

演算法條件

理解了剛剛的解釋後我們再將剛剛的東西簡要分成下面五點。
分別是輸入、輸出、明確性、有限性、有效性

  • 輸入: 0或多個輸入資料,輸入必須要有清楚的表述
  • 輸出: 至少有一個輸出結果,不可沒結果
  • 明確性: 每個指令必須或步驟必須簡潔明確
  • 有限性: 在有限步驟後一定要結束
  • 有效性: 步驟清楚且可行

讀到這邊後我突然覺得我小時候超強的啦,寫出來的解題方法更本就是演算法了。

演算法的評估

知道了演算法的條件後,我們要怎麼知道這個演算法是好還是不好的呢?
這邊主要有兩個計算方法可以去評估這個演算法跟另一個演算法哪邊比較好。

  • 時間複雜度
  • 空間複雜度

時間複雜度

時間複雜度用來出略估計該演算法或該function執行時間,執行時間的單位不是常見的分、秒,而是用t計算。
計算方法個人理解為計算需要執行的行數即可
下面直接用簡單的範例算看看

private void fun1(){ int x = 0; //一個時間單位 }

fun1用了一行去做完一件事,一行一個時間單位因此算1個時間單位。

private int fun2(){ int x = 0; //一個時間單位 for (int i = 0; i < 100; i++){ x = x + 1; //總共會執行100次,所以+100時間單位 } }

fun2 看起來總共用了三行,但表示使用for迴圈的部分不算,因此看起來像是用了兩行。但由於第四行會執行100次,因此算起來會是1+100=101。

private void fun3(int x){ int y = 0; for (int i = 0; i < x; i++){ y++; //會執行x次 } }

fun3 會執行1 + x個時間單位

空間複雜度

空間複雜度其實就更好計算了,主要計算有幾個變數及陣列內容有幾個元素

public void fun1(){ int x = 0; }

以fun1來說的話,總共建立一個變數,所以空間複雜度為1

public void fun2(){ int x = 0; x = x + 1; }

fun2雖然有再加入運算,但由於還是使用相同的變數,因此空間複雜度還是1

public void fun3(int y){ String[] x = new String[y]; }

fun3雖然只有用到一個陣列,但該陣列是利用輸入的變數y設定元素數量,因此空間複雜度是y

以上就是演算法的第一場討論啦。
雖然有點想要把這些東西討論的更有趣更活潑一點。
但最一開始的部份真的就只有啃書而已。
下場開始會用到更多的程式,應該可以聊的比較愉快了吧。

歡迎大家透過下方的留言功能一起討論。如果喜歡的話也歡迎大家分享喔
那麼我們下次見!!!

留言

這個網誌中的熱門文章

基本 Spring security 快速入門

記帳專案說明

JMSTemplate 的教學