Chapter II. 新手上路
基礎演算法
介紹
作者double

何謂演算法?


在日常生活中,如果我們要讓一個人學會某件事情,最簡單的方法之一就是「提供某系列定義清晰的步驟,要求他照做」。舉例來說,如果要讓某一個人學會製作一道料理,最簡單的方法之一就是「提供食譜,讓他照著食譜一步驟一步驟的做」。而在數學或者資訊領域之中,我們就把這種「透過一系列的步驟,找出給定問題的答案」裡面的步驟稱為「演算法」。

演算法的例子


舉例來說,當我們要解決的問題是「給定一個數字 $N$,判斷 $N$ 是不是質數」,我們就會有一個很明顯的演算法:「把 $2\sim N-1$ 之間的每個正整數 $i$ 拿來檢查 $N/i$ 是否能整除,能的話 $N$ 就不是質數,如果這裡面所有 $i$ 都不能整除 $N$,$N$ 就不是質數」。

但同時,我們也可以用一些數學性質來化簡他,例如我們知道「如果 $N$ 有 $1$ 和 $N$ 以外的因數,那他一定有至少一個因數 $\leq\sqrt{N}$」,那我們就可以提出另一個演算法:「把 $2\sim \sqrt{N}$ 之間的每個正整數 $i$ 拿來檢查 $N/i$ 是否能整除,能的話 $N$ 就不是質數,如果這裡面所有 $i$ 都不能整除 $N$,$N$ 就不是質數」。

這其中我們也能發現,雖然兩個演算法都能給出正確的答案,由於第二個演算法檢查的 $i$ 比較少,因此他能夠比較快地給出答案。換句話說,一個問題可能會有多種演算法都能解決它,但是不同演算法執行的速度可能會有所差異。事實上,大部分的問題都會有比較直觀但是要花很多時間的解法,而演算法的學問就在於如何盡可能快的解決問題。