學習筆記：演算法（1）

演算法的定義，是在有限的時間內，
使用一步一步的程序來執行某項工作。

在評估演算法的執行時間時，
會掉入繁複的細節中，
因此發展了漸進式表示法，
讓我們可以描述最主要影響執行時間的主要因素，
而不必掉入「某執行時間為常數的程式，究竟需要多少基本運算」 這種細節，

「Big-O」表示法

f(n)≦cg(n) 通常讀作「f(n) is big-Oh of g(n)」

其意義是，某個n的函數的常數倍(c)，
「小於或等於」另一個函數，
並在n趨近於無窮大時(足夠大時)，漸近於該函數。

在big-O表示法中，我們不喜歡包含常數項或低次項，
雖然那也正確，但是我們都極力要求最簡式。

以下的比喻，可以用來說明漸進表示法的精神：
一個飢餓的遊客在鄉間道路上駕駛了很長時間的車 ，
碰巧遇到了一個剛從市場走回家的農夫，
這個駕駛問農夫還要多久可以買到東西吃，
農夫告訴他「不會超過十二個小時」。

這個答案並沒有錯，但是如果農夫回答「再開幾分鐘就到了」，
如此會更精確，也更有幫助。

big-O表示法中，已經含有「小於或等於」的概念，
因此「f(n)=O(g(n))」的講法雖然常見，卻不完全正確，
而應該用「f(n)是O(g(n))」來理解會更為合適。