[CS101] 新手計算機概論:演算法

簡單的定義演算法就是解決問題的方法。 輸入 → 方法 → 輸出

•5 min read
medium

演算法是什麼?

簡單的定義演算法就是解決問題的方法。

輸入 → 方法 → 輸出

範例

問題:給一個數字,看它是不是質數
輸入:37
演算法:把每個小於它的數拿來除,看能否整除
輸出:YES
問題:給一個數字,求所有的排列組合
輸入:123
演算法:把數字的位置調換,直到出現所有組合
輸出:123, 132, 213, 231, 312, 321

演算法只是解決問題的方法,不一定要懂程式(但懂了會比較聽得懂)

問題:在一堆數字裡找出某個數字
輸入:1, 3, 4, 5, 9, 10 裡找出 9
演算法:從頭找到尾,看看有沒有
輸出:有,第五個

怎麼衡量演算法的好壞

有兩種指標

時間複雜度,一個演算法平均需要多少時間來完成。

問題:在一堆數字裡找出某個數字
輸入:1, 3, 4, 5, 9, 10 裡找出 9
演算法:從頭找到尾,看看有沒有
輸出:有,第五個

假設有 n 個數字

這個演算法要找 n 次

時間複雜度就是 O(n) 參考資料

空間複雜度:一個演算法平均需要多少空間來完成。

時間換空間

空間換時間

問題:n 個數字,m 次查詢
輸入:1, 3, 4, 5, 9, 10
找出有沒有 9,找出有沒有 20,找出有沒有 30
演算法:從頭找到尾,看看有沒有
輸出:有,沒有,沒有
//這個解法是 O(n*m) 的時間複雜度

這邊解法,假設我用一個表格建立結果

n 個數字,要填表需要 n 個步驟

m 次查詢,每次只要一個步驟(查表)

O(n+m)

這個解法就是空間換取時間,因為這個解法省時間,但是需要建立這個表格的空間,指要建立起表格之後,每次查詢都只須要看這個表就好,步驟會少很多。

今天,這個問題的數字是排序過的,那有沒有更好的方法呢?

終極密碼,最快的方法是甚麼?切半猜,每次猜都可以最大範圍的減少可能的答案

1, 2, 4, 10, 11, 12, 38, 93, 94, 102
一共十個數字,假設現在要找 3 有沒有在裡面?
解法:
先找最中間的數字,12,發現 3 < 12
所以如果 3 在數列裡範圍一定是 12 的左邊
再找範圍內最中間的數字:4,發現 3 < 4,所以如果 3 在數列裡,範圍一定是 4 的左邊
再找範圍內最中間的數字:2,發現 2 > 3,所以如果 3 再數列裡
範圍一定是 2 的右邊,4 的左邊
發現範圍裡面沒數字了,所以找不到

藉由排序過後的特性,一職從中間切切切切,就不必從頭到尾找數字,而是能夠有方法、效率的去找。

排序方式的簡介

排序就是在一堆沒有順序的數字裡面,將之按順序排列。

選擇排序法(Selection Sort)

從還排序的數列裡面找到最小的然後移到最左邊

排序演算法展示網站

它會找全部的數字找到最小值之後在把它跟 index 0 交換
在找剩下的全部,把最小值跟剩餘的第一個元素交換
接著再找一次,再用同樣的模式替換。 參考網站:選擇 SEL 就可以看到

泡沫排序法(Bubble Sort)

由左到右兩兩比較,把比較大的數字往右邊移,可以想像成是比較大的數字會浮上來。

從頭開始 n=1,比較兩位數 n 與 n+1 位,兩位比較完之後,比較大的數字往右。
然後 n +1 之後再來做比較,回到上步驟的方式比較,比較直到最後一位數。這時候最大數再最後面了。
再回到最前排重新開始比較。

插入排序法(Insertion Sort)

就是玩撲克牌的時候,會用到排序法,從左邊開始,把每一張牌都放在正確的位置。

設置有 n 位,n = 1
從 n 位開始排序,此時 n = 1 無從比較,所以排定第一位。
排序 n + 1 位,往前比較,插入適合的位置,重複執行,直到全部排序完成

能夠寫出泡沫排序法的步驟嗎?

1. 從頭開始 n = 1,總共用 Max 位要排序
2. 比較 n 與 n+1 位
3. 如果 n > n+1 就把 n 跟 n + 1 的位置對調,如果 n < n+1,則維持原始位置。
4. 把 n 值 + 1。
5. 如果 n 值大於 Max 則排序結束,如果沒有則回到第 2 步驟,繼續執行。

排序法的簡介:分割技巧

合併排序法簡單來說就是:你要排一個數列,你就先把左半邊排好,右半邊也排好,再合併起來不就好了嗎?那你要怎麼把左半邊排好?就把左半邊的左半邊排好,再把左半邊的右半邊排好。

把大問題分割成很多小問題,結果小問題之後再去合併成大問題的解答的解法,就是分割技巧。

合併排序法(Merge Sort)

把一個數列切成左右兩半,個別排序之後在合併起來。

那要如何排序,就是再次切割,一值切到剩下一個數字,在開始做比較排序,之後合併產生一個新數列,合併的方法是各自比較數列最小值,然後排列到新的數組,然後在跟別的合併的合併,值到完成整組的排序。參考網站

快速排序法(Quick Sort)

挑選一個基準點(pivot),讓左邊的數字都小於它,右邊的數字都大於它,然後對左右兩邊重複此操作。

先挑選一個數字,作為基準點(pivot),比如說第一位,然後一一比較後面有比它小的數字就先往前排,搜尋完之後把這些數字的最後一位,跟基準點(pivot)對調,接著把那些比它小的數字做排序這些數字的大小,就會得到排序完成的一部份,接著再從這個數的下一位開始當基準點往後找,排序大小,比較小的就往前放,之後在排序這些比較小的數字,然後就一直往後面找值到所有的數字排序完成。參考網站

收穫:

完成這個章節之後,我對於演算法有了基本的概念,老是聽到演算法,都不知道是甚麼,原來演算法的概念就是這麼簡單而已。當然演算法也可以講得很難就像維基百科那樣,但很多東西我們都只要從很簡單的概念開始就行了,沒必要一開始就直接鑽研最難的東西,只會死得更快而已,也還好這課程都會對於這些很深奧的東西有著最簡單的解釋。後面學到排序的方法,原來排序的方式,也是很深奧的一門學問,之前看得十分鐘快速入門電腦科技,也有講到排序法的事情,當時只知道 Google 那些大公司會很重視這件事情而已,現在在這邊明白到說,為什麼這些不同的演算法,可以幫 Google 省下大筆的開銷,簡單就是速度以及資源使用的問題。