通常在演算法中,為了證明某個演算法執行 n 次項時所需要的時間,我們需要藉由一些比較視覺化的方式去展現出來。如果秉持著職人精神,我們可以把 n 帶入 1、2、3...、1000、...10000... 去跑,並將每次執行完成所需時間做成一張圖表,精神可貴,但時間不夠。為此我們需要以比較「數學化」的方式去分析每個演算法,這就是我們這章節需要介紹的 Asymptotic analysus 漸進分析了。
漸進分析的大綱是在於,當我執行的次數 n 接近於無限大的時候,我們的執行時間會是以何種趨勢去增長?可能是以對數形式 log ,也可能是以線性級數 ax+b,又或是以指數形式 $x^{2}$ 之類的形式去增長,找到他的最高上限 O,最低下限 Ω 以及平均上限下限 Θ。
O, Big-O Notation
Big-O 表示其演算法在「最壞情況」時所需要的時間上限,也是我們一般評定演算法速度的方法。
假設今天的演算法大致時間走勢趨近於方程式 $3n^{2} + 2n + 1$,那我們可以說他的 Big-O 表示法為 $O(n^{2})$,也同時為他的時間複雜度(time complexity)
Big-O 需要滿足方程式 $0 ≤ f(n) ≤ cg(n)$,其中 f(n) 為我們演算法的時間方程式,g(n) 為時間複雜度,c 為一常數。