1.2.2算法分析算法分析的兩個(gè)主要方面是算法的時(shí)間復(fù)雜度和空底復(fù)雜度，其目的主要是考察算法的時(shí)間和空間效率.以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較?一般情況下，崟于運(yùn)算空間(內(nèi)存)較為充足，所以把算法的時(shí)間復(fù)雜度作為分析的重點(diǎn).所謂一個(gè)語(yǔ)句的頻度，即指該語(yǔ)句在算法中被重豆執(zhí)行的次數(shù)。算法中所有語(yǔ)句的頻度之和記做T(n),它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)阿題的規(guī)模d趨向無(wú)窮大時(shí)，T(n)的數(shù)量級(jí)稱(chēng)為漸近時(shí)間復(fù)雜度，置稱(chēng)為時(shí)間復(fù)雜度，記作T(n)-O(fln))e上述表達(dá)式中“0”的含義是T(n)的數(shù)量級(jí)，其嚴(yán)格的數(shù)學(xué)定義是，若T(n)和Rn)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則存在正的常數(shù)C和n。，使得當(dāng)nNnc時(shí)，總是滿(mǎn)足OWT(n)WC?Rn)°但是我們總是考慮在最壞情況下的時(shí)間復(fù)雜度，以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。Function

NamecConstantlogNLogarithmiclog2NLog-squaredNlinearNlogNN'ogNN?QuadraticN，Cubic2可ExponentialInputSize(N)(CApuooag)OE一-SLqllcnHa10002000

3000

40005000

6000

7000B00090001000CInputSize(N)(5)▲若Ti(n)-nk)g2n+l0001og2nf丁血>-亦)凈3-100010既，T^n^-lOWlo^nT4(n)=2nlofi2n-1000kg涕中,則其中漸進(jìn)時(shí)間最小的是T血)&提示：T|(n)=nhg2n+1000iog2n=0(nlogzii),T血戶(hù)nk)*3】0001d&n?0(ii)，T?n戶(hù)r?-1OOOlogjnKMn2).T^nhlnlofcn-lOOOlQ^n-CXnlogzn).【練習(xí)12】

▲下述函數(shù)中漸近時(shí)間最小的是嘿些？(1)TL(nhnlog^nH-1OOOhgiD(2)T如)=n?'T000k)g：n(3)Tj(n>n2-10001og2n(4)T4(n)=2nlog2n^1OOOlogan【解】I](n>O(nlag^)iT血)=0(撲小)T3(n)=O(n^T4(n)=O(nlog2n)fl從中看到.Ti(n)xT/ti)最小"但Ti(nXnT000)k>g2n，T4(n)=(2n-1000)log2n?顯然,n足夠大時(shí),Ti(n)vT4(fi)?所以，漸近時(shí)間最小的是T](心0(1)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)=0(1)。如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模

n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，

其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。

此類(lèi)算法的時(shí)間復(fù)雜度是0(1)。O(nA2)2.1.交換i和j的內(nèi)容