還記得以前在學校,算時間複雜度是我最痛苦的經驗之一,我永遠搞不懂,為什麼不把程式碼就打進電腦裡讓它跑,它跑得動,那就好了,沒有問題;不過現在身為一個遊戲程式設計師,還是console game的程式設計師,這股任性就沒辦法再這樣揮灑了...。
那,一個演算法基礎的分析,大概會是怎樣呢?
我們可以想像成這樣:如果我宣告了一個變數,那就要給它一段記憶體空間,然後對它進行了一連串的運算,這些運算需要一段時間,所以一個演算法,我們可以把它分析為兩個部份:時間複雜度和空間複雜度,時間複雜度代表的是這個演算法執行時間的長短,同常會計算最簡單的加法運算的次數,空間複雜度是它所需要的儲存大小;所以一個演算法的分析,也可以看成是對一個函式的效能評估,也是作遊戲的人一直要跟硬體爭取的東西。
我們通常會使用Big-O這個工具來表示一個函式的效能,接下來講得會針對時間複雜度的部份。下面是三個簡單的範例 。