# [APCS] 演算法簡介

###### tags: `APCS`

## 演算法是什麼
**演算法**（algorithm）是為了完成某個特定的任務，所設計出的一組**有限**的**有序**指令集。

也就是說，演算法是一個有效方法，包含**一系列**定義清晰的指令（有序），並可於**有限的時間及空間**內清楚的表述出來（有限）。

### 演算法的五個要素
1. 輸入（input）
演算法需要包含0個以上的輸入值，可能需要也可能不需要。
2. 輸出（output）
演算法至少會產生一個量值。
3. 定義明確性（definiteness）
演算法的每一個步驟，必須要有明確定義，不可以含糊不清（ambigious）。
4. 有限性（finiteness）
按照演算法的步驟進行，則對於每一個可能的輸入，在有限步驟內都能夠終止。
5. 有效性（effectiveness）
演算法的每一個指令，必須夠基本，且能夠有效執行。

:::warning
**演算法跟程式的不同**：程式可以不滿足 4. 有限性。例如：作業系統、具有無限迴圈的程式等。
:::

## 演算法的表示方法
* 按照步驟逐一條列
使用自然語言（也就是向中文或英文這種我們平常說的語言），將演算法的步驟以條列式的方式寫出來。
* 流程圖
利用各種方塊圖形、線條及箭頭等符號來表達問題的解決問題的步驟及進行的順序。以下是幾種流程圖的圖形對應的圖例：
* 虛擬碼（pseudocode）
保留程式語言流程控制語法架構，再將填充於架構內的程式碼以文字說明或數學方程式取代，組織成描述演算法的說明文件。

* 程式碼
直接將演算法用可讀性高的高階程式語言來表示。

## 演算法的效能分析
分為空間和時間兩個面向，用於分析**空間複雜度**以及**時間複雜度**。
* 空間複雜度
空間複雜度是演算法執行時所花費的**記憶體空間**成本。這些所需的記憶體空間又可以分為：
* 固定空間記憶體
包括基本程式碼、變數、常數等。
* 變動空間記憶體
隨程式進行而改變大小的記憶體使用空間，例如參考型態變數。
由於硬體的發展以及所使用系統的不同，純粹從演算法來分析通常以時間複雜度為主。
* 時間複雜度
時間複雜度電腦執行演算法所需要耗費的時間成本。

### 時間複雜度的分析方法
* 事先預測（a priori estimate） --> 效能**分析**
在尚未執行程式，甚至尚未實作之前，就先針對演算法，事先估計其執行效率。若演算法不符合需求，則可以修改演算法和資料結構。好處是可以提前改善，避免實作出效率不佳的程式。
* 事後測試（a priori estimate） --> 效能**測量**
在機器上直接執行已經實作好的程式。

然而，電腦的執行速度受到處理器速度、計算機組織結構、處理器的指令集、使用的程式語言、編譯器等因素的影響，因此，我們基本上很難準確估計一個程式的執行時間。

所以我們會用這個演算法執行需要幾個**基本指令**來做計算，而每個指令當作一個花費常數時間的步驟。

### 隨機存取機（random access machine, RAM）模型
隨機存取機模型被用在時間複雜度分析當中，裡面包含有常見的基本指令，每個只需要花費常數時間，包括：
* 算術
加、減、乘、除、求餘數等
* 資料移動
複製、儲存、載入等
* 控制
條件與非條件分支、回傳等

RAM模型不考慮記憶體的層級，全部當成同樣的記憶體，不考慮快取、虛擬記憶體等架構。

在一般的演算法分析中，RAM模型可以有效分析一個演算法在真實電腦上的性能。

### 漸進式表示法（asymptotic notations）
由於精確計算演算法的執行步驟或時間的工作過於繁瑣，通常我們會用電腦處理的是大量的資料，因此，我們更關心在資料量非常大的時候，演算法是否夠好。

在計算複雜度的時候，我們不會去計算指令執行的精確次數，取而代之的是計算其**次數等級**，也就是所謂的**複雜度等級**。

我們將執行指令的次數是為輸入大小 $n$ 的函數，並分析這個函數隨著 $n$ 增加的增長情形。

我們一般來說會使用所謂的big-O記號來表示複雜度等級：