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

1、數(shù)據(jù)結(jié)構(gòu)時間復(fù)雜度的計(jì)算for(i=1;i<=n;i+)for(j=1;j<=i;j+)for(k=1;k<=j;k+)x+;它的時間復(fù)雜度是多少？自己計(jì)算了一下，數(shù)學(xué)公式忘得差不多了，郁悶；(1)時間復(fù)雜性是什么？時間復(fù)雜性就是原子操作數(shù)，最里面的循環(huán)每次執(zhí)行j次，中間循環(huán)每次執(zhí)行ai=1+2+3+.+i=i*(i+1)/2次，所以總的時間復(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)】時間復(fù)雜度的計(jì)算算法復(fù)雜度是在數(shù)據(jù)結(jié)構(gòu)這門課程的第一章里出現(xiàn)的，因?yàn)樗晕⑸婕暗揭恍?shù)學(xué)問題，所以很多同學(xué)感覺很難，加上這個概念也不是那么具體，更讓許多同學(xué)復(fù)習(xí)起來無從下手，下面我們就這個問題給各位考生進(jìn)行分析。首先

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

4、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(nA2)、立方階O(nP)、k次方階O(nAk)、指數(shù)階0(2切)。下面我們通過例子加以說明，讓大家碰到問題時知道如何去解決。1設(shè)三個函數(shù)f,g,h分別為f(n)=100nA3+nA2+1000,g(n)=25nA3+5000nA2,h(n)=nA1.5+5000nlgn請判斷下列關(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í)一下漸近時間復(fù)雜度的表示法T(n)=O(f(n)，這里的"O"是數(shù)學(xué)符號，

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

6、，利用大"O"記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。(1) i=1;k=Owhile(i<n)k=k+1O*i;i+;解答：T(n)=n-1，T(n)=O(n)，這個函數(shù)是按線性階遞增的。(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次，這是一個按平方根階遞增的函數(shù)。(3) x=91;y=100;while(y>0)if(x>100)x=x-10;y-;elsex+;解答：T(n)=O(1)，這個程序看起來有點(diǎn)嚇人，總共

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

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

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