數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度的計(jì)算

1、數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度的計(jì)算for(i=1;i<=n;i+)for(j=1;j<=i;j+)for(k=1;k<=j;k+)x+;它的時(shí)間復(fù)雜度是多少？自己計(jì)算了一下，數(shù)學(xué)公式忘得差不多了，郁悶；(1)時(shí)間復(fù)雜性是什么？時(shí)間復(fù)雜性就是原子操作數(shù)，最里面的循環(huán)每次執(zhí)行j次，中間循環(huán)每次執(zhí)行ai=1+2+3+.+i=i*(i+1)/2次，所以總的時(shí)間復(fù)雜性=a1+.+ai+.+an;a1+.+ai+.+an=1+(1+2)+(1+2+3)+.+(1+2+3+.+n)=1*n+2*(n-1)+3*(n-2)+.+n*(n-(n-1)=n+2n+3n+.+n*n-(2*1+3*2+4*3

2、+.+n*(n-1)=n(1+2+.+n)-(2*(2-1)+3*(3-1)+4*(4-1)+.+n*(n-1)=n(n(n+1)/2-(2*2+3*3+.+n*n)-(2+3+4+.+n)=n(n(n+1)/2-(1*1+2*2+3*3+.+n*n)-(1+2+3+4+.+n)=n(n(n+1)/2-n(n+1)(2n+1)/6+n(n+1)/2所以最后結(jié)果是O(nA3)o【轉(zhuǎn)】時(shí)間復(fù)雜度的計(jì)算算法復(fù)雜度是在數(shù)據(jù)結(jié)構(gòu)這門(mén)課程的第一章里出現(xiàn)的，因?yàn)樗晕⑸婕暗揭恍?shù)學(xué)問(wèn)題，所以很多同學(xué)感覺(jué)很難，加上這個(gè)概念也不是那么具體，更讓許多同學(xué)復(fù)習(xí)起來(lái)無(wú)從下手，下面我們就這個(gè)問(wèn)題給各位考生進(jìn)行分析。首先

3、了解一下幾個(gè)概念。一個(gè)是時(shí)間復(fù)雜度，一個(gè)是漸近時(shí)間復(fù)雜度。前者是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)，而后者是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度，因此，在算法分析時(shí)，往往對(duì)兩者不予區(qū)分，經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n)簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度，其中的f(n)般是算法中頻度最大的語(yǔ)句頻度。此外，算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。但是我們總是考慮在最壞的情況下的時(shí)間復(fù)雜度。以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。常見(jiàn)的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、

4、對(duì)數(shù)階O(log2n)、線(xiàn)性階O(n)、線(xiàn)性對(duì)數(shù)階O(nlog2n)、平方階O(nA2)、立方階O(nP)、k次方階O(nAk)、指數(shù)階0(2切)。下面我們通過(guò)例子加以說(shuō)明，讓大家碰到問(wèn)題時(shí)知道如何去解決。1設(shè)三個(gè)函數(shù)f,g,h分別為f(n)=100nA3+nA2+1000,g(n)=25nA3+5000nA2,h(n)=nA1.5+5000nlgn請(qǐng)判斷下列關(guān)系是否成立：(1)f(n)=O(g(n)(2)g(n)=O(f(n)(3)h(n)=O(nA1.5)(4)h(n)=O(nlgn)這里我們復(fù)習(xí)一下漸近時(shí)間復(fù)雜度的表示法T(n)=O(f(n)，這里的"O"是數(shù)學(xué)符號(hào)，

5、它的嚴(yán)格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)=O(f(n)表示存在正的常數(shù)C和n0,使得當(dāng)nnO時(shí)都滿(mǎn)足OWT(n)<C?f(n>"用容易理解的話(huà)說(shuō)就是這兩個(gè)函數(shù)當(dāng)整型自變量n趨向于無(wú)窮大時(shí)，兩者的比值是一個(gè)不等于O的常數(shù)。這么一來(lái)，就好計(jì)算了吧。 (1)成立。題中由于兩個(gè)函數(shù)的最高次項(xiàng)都是nA3，因此當(dāng)ns時(shí)，兩個(gè)函數(shù)的比值是一個(gè)常數(shù)，所以這個(gè)關(guān)系式是成立的。 (2)成立。與上同理。 (3)成立。與上同理。 (4)不成立。由于當(dāng)ns時(shí)nAl.5比nlgn遞增的快，所以h(n)與nlgn的比值不是常數(shù)，故不成立。2、設(shè)n為正整數(shù)

6、，利用大"O"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。(1) i=1;k=Owhile(i<n)k=k+1O*i;i+;解答：T(n)=n-1，T(n)=O(n)，這個(gè)函數(shù)是按線(xiàn)性階遞增的。(2) x=n;/n>1while(x>=(y+1)*(y+1)y+;解答：T(n)=n1/2，T(n)=0(n1/2)，最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個(gè)按平方根階遞增的函數(shù)。(3) x=91;y=100;while(y>0)if(x>100)x=x-10;y-;elsex+;解答：T(n)=O(1)，這個(gè)程序看起來(lái)有點(diǎn)嚇人，總共

7、循環(huán)運(yùn)行了1000次，但是我們看到n沒(méi)有?沒(méi)這段程序的運(yùn)行是和n無(wú)關(guān)的，就算它再循環(huán)一萬(wàn)年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。1.1 大O表示法上學(xué)的時(shí)候就學(xué)習(xí)了大O表示法表示一個(gè)算法的效率，也大概明白怎么回事，知道如果沒(méi)有循環(huán)的一段程序的復(fù)雜度是常數(shù)，一層循環(huán)的復(fù)雜度是0(n),兩層循環(huán)的復(fù)雜度是O(nT)?(我用人2表示平方，同理人3表示立方)。但是一直對(duì)于嚴(yán)格的定義和用法稀里糊涂。1.1.1 定義設(shè)一個(gè)程序的時(shí)間復(fù)雜度用一個(gè)函數(shù)T(n)來(lái)表示，對(duì)于一個(gè)查找算法，如下：intseqsearch(inta,constintn,constintx)inti=0;for(;ai!=x&

8、&i<n;i+);if(i=n)return-1;elsereturni;這個(gè)程序是將輸入的數(shù)值順序地與數(shù)組中地元素逐個(gè)比較，找出與之相等地元素。在第一個(gè)元素就找到需要比較一次，在第二個(gè)元素找到需要比較2次，在第n個(gè)元素找到需要比較n次。對(duì)于有n個(gè)元素的數(shù)組，如果每個(gè)元素被找到的概率相等，那么查找成功的平均比較次數(shù)為:f(n)=1/n(n+(n-1)+(n-2)+.+1)=(n+1)/2=O(n)這就是傳說(shuō)中的大O函數(shù)的原始定義。1.1.2 用大O來(lái)表述要全面分析一個(gè)算法，需要考慮算法在最壞和最好的情況下的時(shí)間代價(jià)，和在平均情況下的時(shí)間代價(jià)。對(duì)于最壞情況，采用大O表示法的一般提法

9、(注意，這里用的是“一般提法”)是：當(dāng)且僅當(dāng)存在正整數(shù)c和n0,使得T(n)<=c*f(n)對(duì)于所有的n>=n0都成立。則稱(chēng)該算法的漸進(jìn)時(shí)間復(fù)雜度為T(mén)(n)=O(f(n)這個(gè)應(yīng)該是高等數(shù)學(xué)里面的第一章極限里面的知識(shí)。這里f(n)=(n+1)/2,那么c*f(n)也就是一個(gè)一次函數(shù)。對(duì)于對(duì)數(shù)級(jí)，我們用大O記法記為O(log2N)就可以了。1.1.3 加法規(guī)則T(n,m)=T1(n)+T2(n)=O(max(f(n),g(m)1.1.4 乘法規(guī)則T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)1.1.5 一個(gè)特例在大0表示法里面有一個(gè)特例，如果T1(n)=0(c),c是一個(gè)與n無(wú)關(guān)的任意常數(shù)，T2(n)=O(f(n)則有T(n)=T1(n)*T2(n)=0(c*f(n)=0(f(n).也就是說(shuō)，在大0表示法中，任何非0正常數(shù)都屬于同一數(shù)量級(jí)，記為0(1)。1.1.6 一個(gè)經(jīng)驗(yàn)規(guī)則有如下復(fù)雜度關(guān)系c<log2N&l