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

1、時(shí)間復(fù)雜度的定義一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用 T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)， 則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=0(f(n)，稱O(f(n)為算法的漸進(jìn)時(shí)間復(fù)雜度(O是數(shù)量級(jí)的符號(hào))，簡(jiǎn)稱時(shí)間復(fù)雜度。根據(jù)定義，可以歸納出基本的計(jì)算步驟1計(jì)算出基本操作的執(zhí)行次數(shù) T(n)基本操作即算法中的每條語句(以；號(hào)作為分割)，語句的執(zhí)行次數(shù)也叫做語句的頻度。在做算法分析時(shí)，一般默認(rèn)為考慮最壞的情況。2計(jì)算出T(n)的數(shù)量級(jí)求T(n)的數(shù)量級(jí)，只要將 T(n)進(jìn)行如下一些操作

2、: 忽略常量、低次幕和最咼次幕的系數(shù)令f(n)=T(n)的數(shù)量級(jí)。3.用大0來表示時(shí)間復(fù)雜度當(dāng)n趨近于無窮大時(shí)，如果lim(T(n)/f(n)的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作 T(n)=O(f(n)。一個(gè)示例：(1) int nu ml, nu m2;(2) for(i nt i=0; i< n; i+)(3) numl += 1;(4) for(i nt j=1; j<=n; j*=2)(5) num2 += nu m1;分析：1.語句int num1, num2;的頻度為1;語句i=0;的頻度為1;語句 i<n; i+; num1+=1;

3、j=1;的頻度為 n;語句 j<=n; j*=2; num2+=num1;的頻度為 n*log2n ;T(n) = 2 + 4n + 3n *log2 n 2.忽略掉T(n)中的常量、低次幕和最高次幕的系數(shù)f(n) = n*log2n lim(T( n)/f(n) = (2+4 n+3 n*log2 n) / (n*log2 n)3.=2*(1/n)*(1/log2 n) + 4*(1/log2 n) + 3當(dāng)n趨向于無窮大，1/n趨向于0, 1/log2n趨向于0 所以極限等于3。T(n) = O(n *log2 n)簡(jiǎn)化的計(jì)算步驟再來分析一下，可以看出，決定算法復(fù)雜度的是執(zhí)行次數(shù)最多

4、的語句，這里是num2 += numl ,般也是最內(nèi)循環(huán)的語句。并且，通常將求解極限是否為常量也省略掉?于是，以上步驟可以簡(jiǎn)化為：1.找到執(zhí)行次數(shù)最多的語句2計(jì)算語句執(zhí)行次數(shù)的數(shù)量級(jí)3.用大O來表示結(jié)果繼續(xù)以上述算法為例，進(jìn)行分析:1.執(zhí)行次數(shù)最多的語句為 n um2 += numl2.T(n) = n*log2n f(n) = n*log2n 3./ lim(T( n)/f(n) = 1T(n) = O(n *log2 n)一些補(bǔ)充說明最壞時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度不僅與語句頻度有關(guān)，還與問題規(guī)模及輸入實(shí)例中各元素的取值有關(guān)。一般不特別說明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。這就保

5、證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。求數(shù)量級(jí)即求對(duì)數(shù)值(log)，默認(rèn)底數(shù)為10,簡(jiǎn)單來說就是 一個(gè)數(shù)用標(biāo)準(zhǔn)科學(xué)計(jì)數(shù)法表示后，10的指數(shù)”。例如，5000=5x10 3 (log5000=3)，數(shù)量級(jí)為3。另外，一個(gè)未知數(shù)的數(shù)量級(jí)為其最接 近的數(shù)量級(jí)，即最大可能的數(shù)量級(jí)。求極限的技巧要利用好1/n。當(dāng)n趨于無窮大時(shí)，1/n趨向于0一些規(guī)則(引自：時(shí)間復(fù)雜度計(jì)算)1)加法規(guī)則T(n,m) = T1( n) + T2( n) = O (max ( f(n), g(m)2)乘法規(guī)則T( n,m) = T1( n) * T2(m) = O (f(n) * g(m)3)一個(gè)特例(問題規(guī)模為常量的時(shí)間復(fù)雜度

6、)在大O表示法里面有一個(gè)特例，如果T1(n) = 0(c), c是一個(gè)與n無關(guān)的任意常數(shù)，T2(n)=0 ( f(n)則有T(n) = T1( n) * T2( n) = 0 ( c*f(n) ) = 0( f(n)也就是說，在大 O表示法中，任何非0正常數(shù)都屬于同一數(shù)量級(jí)，記為0(1)。4) 一個(gè)經(jīng)驗(yàn)規(guī)則復(fù)雜度與時(shí)間效率的關(guān)系：c < log2 n < n < n*log2n < n2 < n3 < 2n < 3n < n!(c 是一個(gè)常量)較好一般較差其中c是一個(gè)常量，如果一個(gè)算法的復(fù)雜度為c、 log2n、n、 n*log2n,那么這個(gè)算法

7、時(shí)間效率比較高，如果是2n , 3n ,n!,那么稍微大一些的n就會(huì)令這個(gè)算法不能動(dòng)了，居于中 間的幾個(gè)則差強(qiáng)人意。復(fù)雜情況的分析以上都是對(duì)于單個(gè)嵌套循環(huán)的情況進(jìn)行分析，但實(shí)際上還可能有其他的情況，下面將例舉說明。1并列循環(huán)的復(fù)雜度分析 將各個(gè)嵌套循環(huán)的時(shí)間復(fù)雜度相加。例如：for (i=1; i<=n; i+)x+;for (i=1; i<=n; i+)for (j=1; j<=n; j+)x+;解：第一個(gè)for循環(huán)T(n) = nf(n) = n時(shí)間復(fù)雜度為O (n)第二個(gè)for循環(huán)T(n) = n2f(n) = n2時(shí)間復(fù)雜度為O (n2)整個(gè)算法的時(shí)間復(fù)雜度為O (n

8、+n2) = O (n2)2函數(shù)調(diào)用的復(fù)雜度分析例如：public void prin tsum(i nt coun t)int sum = 1;for(i nt i= 0; i<n; i+)sum += i;System.out.pri nt(sum);分析：記住，只有可運(yùn)行的語句才會(huì)增加時(shí)間復(fù)雜度，因此，上面方法里的內(nèi)容除了循環(huán)之外，其 余的可運(yùn)行語句的復(fù)雜度都是0(1)。所以printsum的時(shí)間復(fù)雜度 =for的O(n)+O(1)=忽略常量 =O(n)*這里其實(shí)可以運(yùn)用公式num = n*(n +1)/2，對(duì)算法進(jìn)行優(yōu)化，改為：public void prin tsum(i nt

9、 coun t)int sum = 1;sum = count * (co un t+1)/2;System.out.pri nt(sum);這樣算法的時(shí)間復(fù)雜度將由原來的0(n)降為0(1)，大大地提高了算法的性能。3.混合情況(多個(gè)方法調(diào)用與循環(huán))的復(fù)雜度分析例如：public void suixia ngMethod(i nt n)prin tsum( n);/1.1for(i nt i= 0; i<n; i+)prin tsum( n); /1.2for(i nt i= 0; i<n; i+)for(i nt k=0; kSystem.out.pri nt(i,k); /1

10、.3suixiangMethod方法的時(shí)間復(fù)雜度需要計(jì)算方法體的各個(gè)成員的復(fù)雜度。也就是 1.1+1.2+1.3 = 0(1)+0(n)+0(n2)->忽略常數(shù) 和 非主要項(xiàng) =0(n2)更多的例子0(1)交換i和j的內(nèi)容temp=i;i=j；j=temp;以上三條單個(gè)語句的頻度為 1，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作 T(n)=0(1)。如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語句， 其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是0(1)。0(n 2)/*執(zhí)行次數(shù)1 */*執(zhí)行次數(shù)n2 */sum=0;f

11、or(i=1;i<=n ;i+)for(j=1;j<=n ;j+)sum+ ；解：T(n) = 1 + n2 = 0(n2)for (i=1;i< n;i+)y=y+1;for (j=0;j<=(2* n);j+) x+;解： 語句1的頻度是n-1語句 2 的頻度是(n-1)*(2n+1) = 2n2-n-1T(n) = 2n2-n-1+( n-1) = 2n 2-2f(n) = n2lim(T( n)/f(n) = 2 + 2*(1/n2) = 2T( n) = 0(n 2).0(n)a=0;b=1;for (i=1;i<=n ;i+)s=a+b;b=a;a=s

12、;解：語句1的頻度：2,語句2的頻度：n,語句3的頻度：n,語句4的頻度：n,語句5的頻度：n,T(n) = 2+4nf(n) = nlim(T( n)/f(n) = 2*(1/n) + 4 = 4T( n) = 0(n).O(log2 n)i=1;while (i<=n)i=i*2;解：語句1的頻度是1,設(shè)語句2的頻度是t,貝U: nt<=n; t<=log2n考慮最壞情況，取最大值t=log2 n,T(n) = 1 + log2 nf(n) = log2 nlim(T( n)/f(n) = 1/log2n + 1 = 1T(n) = O(log2 n)O(n3)for(i=0;i <n ;i+)for(j=0;j<i;j+)for(k=0;k<j;k+)x=x+2;解：