演算法(Algorithm)簡單介紹

什麼是演算法(Algorithm) ?

演算法是一種處理程序(procedure)，透過輸入參數(input)來，經過一系列的程序，來得到一個輸出(output)結果。(ex: 像是數學上的函數(function)，料理的食譜……等等。)

演算法的正確性(Correctness):

如何判斷這個演算法是正確的，可以透過數學上的歸納法(induction)來進行驗證，因為演算法是一種處理程序，不管輸入的值為多少，都只會回傳一個結果，若輸入相同的值，其結果也必定相同，所以對於驗證演算法的正確性來說，只要輸入定義內的值，其返回的結果都成立，其就是一個正確的演算法。

演算法的效率(Efficiency):

由於演算法是一種處理程序，對於相同的問題，事實上是可以有多種演算法來處理，然而哪種演算法才是最好的，其所需探討的就是演算法的效率，演算法的效率取決於電腦的性能與輸入的資料量大小，其中一般在探討效率都著重於輸入的資料量大小，意即對於相同的問題，且相同的資料量大小中，哪種演算法的處理時間最短，花費的時間最短，即是最優的演算法。

漸進符號(Asymptotic Notation):

漸進符號是一種用來表示演算法效率的方法，其中有三種符號，而一般以O(Big-O Notation)來表示。

Notation	簡單描述
O(Big-O)	表示上界(upper bounds)
Ω(Big-Omega)	表示下界(lower bounds)
Θ(Big-Theta)	表示介於上界與下界(tight bounds)

一些常見的O(f(n)):

input	Constant	Logarithmic	Linear	log-linear	Quadratic
n	O(1)	O(log n)	O(n)	O(n log n)	O(n2)

(Source: Daniel Miessler)