數據結構之算法和算法分析[4]

　　一個算法是由控制結構和原操作構成的其執行時間取決於兩者的綜合效果為了便於比較同一問題的不同的算法通常的做法是從算法中選取一種對於所研究的問題來說是基本運算的原操作以該原操作重復執行的次數作為算法的時間度量一般情況下算法中原操作重復執行的次數是規模n的某個函數T(n)

　　許多時候要精確地計算T(n)是困難的我們引入漸進時間復雜度在數量上估計一個算法的執行時間也能夠達到分析算法的目的

　　定義(大Ο記號)如果存在兩個正常數c和n使得對所有的nn≥n有

　　f(n) ≤ cg(n)

　　則有

　　f(n) = Ο(g(n))

　　例如一個程序的實際執行時間為T(n)=n+n+則T(n)=Ο(n)

　　使用大Ο記號表示的算法的時間復雜度稱為算法的漸進時間復雜度(Asymptotic Complexity)

　　通常用Ο()表示常數計算時間常見的漸進時間復雜度有

　　Ο()<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n)<Ο(n)<Ο(n)

[]  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23946.html