一、定義

（1）如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數(shù) T(n)稱為這一算法的“時間復雜性”。我們常用大O表示法表示時間復雜性，稱之為大O記法。
（2）一個問題本身也有它的復雜性，如果某個算法的復雜性到達了這個問題復雜性的下界，那就稱這樣的算法是最佳算法。常見的時間復雜度高低順序如下：
O(1) 常數(shù)階 < O(logn) 對數(shù)階 < O(n) 線性階 < O(nlogn) < O(n^2) 平方階 < O(n^3) < O(2^n) < O(n!) < O(n^n)

二、時間復雜度計算步驟

⑴ 找出算法中的基本語句；
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。
⑵ 計算基本語句的執(zhí)行次數(shù)的數(shù)量級；
只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。
⑶ 用大Ο記號表示算法的時間性能。
將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中。
如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時間復雜度相加。

三、時間復雜度計算規(guī)則

（1）對于一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間
（2）對于順序結構,需要依次執(zhí)行一系列語句所用的時間可采用大O下"求和法則"
求和法則:是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))
特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))
（3）對于選擇結構,如if語句,它的主要時間耗費是在執(zhí)行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間
（4）對于循環(huán)結構,循環(huán)語句的運行時間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗循環(huán)條件的時間耗費,一般可用大O下"乘法法則"
乘法法則: 是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n))
（5）對于復雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術整個算法的時間復雜度

最新評論