iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 1
6

前言


在這個資訊大爆炸的時代裡,每個人或多或少都有聽過 演算法(Algorithm) 這三個字。

演算法並非是程式語言,而在電腦出現之前,演算法在數學界已經進行得如火如荼了!你知道嗎?國中所學的輾轉相除法是目前公認的世界上第一個演算法喔!

那到底什麼是演算法呢?根據 Wiki 的定義是

為任何良定義的具體計算步驟的一個序列,常用於計算、資料處理和自動推理。精確而言,演算法是一個表示爲有限長列表的有效方法。演算法應包含清晰定義的指令用於計算函式。

換句話說,演算法是

可以解決某些問題的有效方法之有限集合。

是不是經過解釋還是看不懂?那我就舉生活例子吧!

「有什麼方法可以得到食物?」

Example 1:

1. 走路去餐飲店
2. 點餐
3. 得到相對應的食物

Example 2:

1. 騎車去全聯
2. 買食材
3. 煮剛剛買的食材
4. 得到相對應的食物

你就可以說,以上兩個範例的步驟與解法就是 有什麼方法可以得到食物? 的演算法。


特徵


根據 Wiki 的定義

1. 輸入: 一個演算法必須有0 個或以上的input。

2. 輸出: 一個演算法應有1個或以上輸出量,輸出量是演算法計算的結果。

3. 明確性: 演算法的描述必須無歧義,以保證演算法的實際執行結果是精確地符合要求或期望,通常要求實際執行結果是確定的。

  • 例如:「天氣變熱了,就要開冷氣。」 是一個很不明確的敘述。什麼樣的情況叫熱?每個人對熱的定義都不一樣,所以這個問題沒有明確性。
  • 若是改成 「溫度若高於攝氏28度,就要開冷氣。」,這樣敘述就非常明確了。

4. 有限性: 依據圖靈的定義,一個演算法是能夠被任何圖靈完備系統類比的一串運算,而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函式(指令)。而一些定義更規定演算法必須在有限個步驟內完成任務

  • 換句話說,每個演算法必須在有限的步驟上完成或終止,不能無限期的執行。

5. 有效性: 又稱可行性。能夠實現,演算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。


範例


1. 「找出輸入的月份的季節」
2. 「且輸入的月份須合法(1~12月)」
3. 「若不合法則回傳錯誤。」

流程圖

C#

string FindSeason (int month)
{
    if (month >= 1 && month <= 3)
        return "Spring";
    else if (month >= 4 && month <= 6)
        return "Summer";
    else if (month >= 7 && month <= 9)
        return "Fall";
    else if (month >= 10 && month <= 12)
        return "Winter";
    else
        return "Error";
}

由上述範例可得知

1. 明確性: 問題描述非常明確,並沒有疑慮。

2. 有效性: 在流程圖上可以看出若演算法(FindSeason)發現Month月份(輸入) 不在合法範圍1~12月之間,則回傳錯誤;反之,則判斷輸入的月份,回傳相對應的季節(輸出)。

3. 有限性: 執行一次就結束。


以上就是我對演算法的簡單介紹啦!
如果其它人有更棒的想法及意見,請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉 /images/emoticon/emoticon07.gif


下一篇
[Day 2] 演算法複雜度分析──時間複雜度(Time Complexity)、空間複雜度(Space Complexity)
系列文
透過 LeetCode 解救美少女工程師的演算法人生31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言