演算法分析演算法分析複雜度(Complexity)三種狀況通常，我們只專注在找出最差狀況運行時間(worst-caserunningtime)理由:是運行時間的上限(upperbound)。最差狀況也經常發生。平均狀況常常和最差狀況一樣差。例如:插入排序(insertionsort)以及二次函數(quadraticfunction)。一個用以測試質數的演算法我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime2需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作-2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime2只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。分析演算法Prime1分析演算法Prime2漸進記號(AsymptoticNotation)量級(Order)大O記號(Big-ONotation)定義大O記號Def:f(n)=O(g(n))“上限(upperbound)"iffc,n0|f(n)|c|g(n)|nn0e.g.f(n)=3n2+2g(n)=n2n0=2,c=4f(n)=O(n2)e.g.f(n)=n3+n=O(n3)e.g.f(n)=3n2+2=O(n3)orO(n100)漸近式上限(AsymptoticUpperBound)Def:f(n)=(g(n))“下限(lowerbound)”iffc,andn0,|f(n)|c|g(n)|nn0e.g.f(n)=3n2+2=(n2)or(n)漸近式下限(AsymptoticLowerBound)Def:f(n)=(g(n))iffc1,c2,andn0,c1|g(n)||f(n)|c2|g(n)|nn0e.g.f(n)=3n2+2=(n2)f(n)=(g(n))Theorem盡可能將量級降低量級的比較演算法時間複雜度的大O記號表示及其量級演算法各種時間複雜度的執行步驟對照數值演算法各種時間複雜度量級成長圖演算法各種時間複雜度量級成長圖(對數圖)多項式時間演算法vs.指數時間演算法上高斯符號(ceiling)與下高斯符號(floor)模數運算(modularoperation)