在忽略機(jī)器性能的基礎(chǔ)上我們用算法時(shí)間復(fù)雜度來(lái)衡量算法執(zhí)行的時(shí)間。
1、時(shí)間頻度
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。
2、時(shí)間復(fù)雜度
在剛才提到的時(shí)間頻度中，n稱(chēng)為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),稱(chēng)O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。

在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O(n^2)。
按數(shù)量級(jí)遞增排列，常見(jiàn)的時(shí)間復(fù)雜度有：
常數(shù)階O(1),對(duì)數(shù)階O(log2n)(以2為底n的對(duì)數(shù)，下同),線性階O(n),
線性對(duì)數(shù)階O(nlog2n),平方階O(n^2)，立方階O(n^3),…，
k次方階O(n^k),指數(shù)階O(2^n)。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。
算法的時(shí)間性能分析
（1）算法耗費(fèi)的時(shí)間和語(yǔ)句頻度

一個(gè)算法所耗費(fèi)的時(shí)間=算法中每條語(yǔ)句的執(zhí)行時(shí)間之和

每條語(yǔ)句的執(zhí)行時(shí)間=語(yǔ)句的執(zhí)行次數(shù)(即頻度(Frequency Count))×語(yǔ)句執(zhí)行一次所需時(shí)間

算法轉(zhuǎn)換為程序后，每條語(yǔ)句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。

若要獨(dú)立于機(jī)器的軟、硬件系統(tǒng)來(lái)分析算法的時(shí)間耗費(fèi)，則設(shè)每條語(yǔ)句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語(yǔ)句的頻度之和。
求兩個(gè)n階方陣的乘積 C=A×B,其算法如下:

　　# define n 100 // n 可根據(jù)需要定義,這里假定為100 　　void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n]) 　　{ //右邊列為各語(yǔ)句的頻度 　　int i ,j ,k; 　　 for(i=0; i<n;j++) n+1 　　 for (j=0;j<n;j++) { n(n+1) 　　 C[i][j]=0; n 　　 for (k=0; k<n; k++) nn(n+1) 　　 C[i][j]=C[i][j]+A[i][k]*B[k][j];n 　　} 　　}

該算法中所有語(yǔ)句的頻度之和(即算法的時(shí)間耗費(fèi))為：

T(n)=nn(n+1) (1.1)

分析：

語(yǔ)句(1)的循環(huán)控制變量i要增加到n，測(cè)試到i=n成立才會(huì)終止。故它的頻度是n+1。但是它的循環(huán)體卻只能執(zhí)行n次。語(yǔ)句(2)作為語(yǔ)句(1)循環(huán)體內(nèi)的語(yǔ)句應(yīng)該執(zhí)行n次，但語(yǔ)句(2)本身要執(zhí)行n+1次，所以語(yǔ)句(2)的頻度是n(n+1)。同理可得語(yǔ)句(3)，(4)和(5)的頻度分別是n，nn(n+1)和n。

算法MatrixMultiply的時(shí)間耗費(fèi)T(n)是矩陣階數(shù)n3的函數(shù)。

（2）問(wèn)題規(guī)模和算法的時(shí)間復(fù)雜度
算法求解問(wèn)題的輸入量稱(chēng)為問(wèn)題的規(guī)模(Size),一般用一個(gè)整數(shù)表示。

矩陣乘積問(wèn)題的規(guī)模是矩陣的階數(shù)。

一個(gè)圖論問(wèn)題的規(guī)模則是圖中的頂點(diǎn)數(shù)或邊數(shù)。

一個(gè)算法的時(shí)間復(fù)雜度(Time Complexity, 也稱(chēng)時(shí)間復(fù)雜性)T(n)是該算法的時(shí)間耗費(fèi)，是該算法所求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度。

算法MatrixMultidy的時(shí)間復(fù)雜度T(n)如(1.1)式所示，當(dāng)n趨向無(wú)窮大時(shí)，顯然有T(n)~O(n3);

這表明，當(dāng)n充分大時(shí)，T(n)和n3之比是一個(gè)不等于零的常數(shù)。即T(n)和n3是同階的，或者說(shuō)T(n)和n3的數(shù)量級(jí)相同。記作T(n)=O(n3)是算法MatrixMultiply的漸近時(shí)間復(fù)雜度。

（3）漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能

主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能。
算法MatrixMultiply的時(shí)間復(fù)雜度一般為T(mén)(n)=O(n3)，f(n)=n3是該算法中語(yǔ)句(5)的頻度。下面再舉例說(shuō)明如何求算法的時(shí)間復(fù)雜度。

交換i和j的內(nèi)容。

Temp=i; i=j; j=temp;

　　以上三條單個(gè)語(yǔ)句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)?！　?br />注意：如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)。
變量計(jì)數(shù)之一：

　　 x=0;y=0; 　　 for(k-1;k<=n;k++) 　　 x++; 　　 for(i=1;i<=n;i++) 　　 for(j=1;j<=n;j++) 　　 y++;

一般情況下，對(duì)步進(jìn)循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)，忽略該語(yǔ)句中步長(zhǎng)加1、終值判別、控制轉(zhuǎn)移等成分。因此，以上程序段中頻度最大的語(yǔ)句是(6)，其頻度為f(n)=n2，所以該程序段的時(shí)間復(fù)雜度為T(mén)(n)=O(n2)。

當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。

變量計(jì)數(shù)之二：

x=1; for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++;

該程序段中頻度最大的語(yǔ)句是(5)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問(wèn)題規(guī)模n沒(méi)有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語(yǔ)句(5)的執(zhí)行次數(shù)：

則該程序段的時(shí)間復(fù)雜度為T(mén)(n)=O(n3/6+低次項(xiàng))=O(n3)。

（4）算法的時(shí)間復(fù)雜度不僅僅依賴(lài)于問(wèn)題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)。

在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下：

i=n-1; while(i>=0&&(A[i]!=k))  i--; return i;

此算法中的語(yǔ)句(3)的頻度不僅與問(wèn)題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān):

①若A中沒(méi)有與K相等的元素，則語(yǔ)句(3)的頻度f(wàn)(n)=n；

②若A的最后一個(gè)元素等于K,則語(yǔ)句(3)的頻度f(wàn)(n)是常數(shù)0。