時間複雜度分析教材(PPT 48頁)

時間複雜度分析
算法時間複雜度的數學意義
從數學上定義，給定算法A，如果存在函數f(n)，當n=k時，
f(k)表示算法A在輸入規模為k的情況下的運行時間，則稱f(n)為算法A的時間複雜度。
其中：輸入規模是指算法A所接受輸入的自然獨立體的大小，
我們總是假設算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,……
對於同一個算法，每次執行的時間不僅取決於輸入規模，
還取決於輸入的特性和具體的硬件環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)
是不可能的。為此，通常做法：1.忽略硬件及環境因素，假設每次執行時硬件條件和環境條件是完全一致的。
2.對於輸入特性的差異，我們將從數學上進行精確分析並帶入函數解析式。
算法的漸近時間複雜度很多時候，我們不需要進行如此精確的分析，究其原因：
1.在較複雜的算法中，進行精確分析是非常複雜的。
2.實際上，大多數時候我們並不關心F(n)的精確度量，而隻是關心其量級。
算法複雜度的考察方法
（1）考察一個算法的複雜度，一般考察的是當問題複雜度n的增加時，運算所需時間、空間代價f(n)的上下界。
（2）進一步而言，又分為最好情況、平均情況、最壞情況三種情況。通常最壞情況往往是我們最關注的。
（1）上界函數
..............................