數(shù)據(jù)結(jié)構(gòu)算法時(shí)間復(fù)雜度計(jì)算行業(yè)資料

1/1數(shù)據(jù)結(jié)構(gòu)算法時(shí)間復(fù)雜度計(jì)算-行業(yè)資料

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

時(shí)間簡(jiǎn)單度的定義

一般狀況下，算法中基本操作重復(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)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間簡(jiǎn)單度(O是數(shù)量級(jí)的符號(hào))，簡(jiǎn)稱時(shí)間簡(jiǎn)單度。

依據(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)行如下一些操作：

忽視常量、低次冪和最高次冪的系數(shù)

令f(n)=T(n)的數(shù)量級(jí)。

3.用大O來表示時(shí)間簡(jiǎn)單度

當(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)intnum1,num2;

(2)for(inti=0;in;i++){

(3)num1+=1;

(4)for(intj=1;j=n;j*=2){

(5)num2+=num1;

(6)}

(7)}

分析：

1.

語句intnum1,num2;的頻度為1；

語句i=0;的頻度為1；

語句in;i++;num1+=1;j=1;的頻度為n；

語句j=n;j*=2;num2+=num1;的頻度為n*log2n；

T(n)=2+4n+3n*log2n

2.

忽視掉T(n)中的常量、低次冪和最高次冪的系數(shù)

f(n)=n*log2n

3.

lim(T(n)/f(n))=(2+4n+3n*log2n)/(n*log2n)

1

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.

=2*(1/n)*(1/log2n)+4*(1/log2n)+3

當(dāng)n趨向于無窮大，1/n趨向于0，1/log2n趨向于0

所以極限等于3。

T(n)=O(n*log2n)

簡(jiǎn)化的計(jì)算步驟

再來分析一下，可以看出，打算算法簡(jiǎn)單度的是執(zhí)行次數(shù)最多的語句，這里是num2+=num1，一般也是最內(nèi)循環(huán)的語句。

并且，通常將求解極限是否為常量也省略掉？

于是，以上步驟可以簡(jiǎn)化為：

1.找到執(zhí)行次數(shù)最多的語句

2.計(jì)算語句執(zhí)行次數(shù)的數(shù)量級(jí)

3.用大O來表示結(jié)果

連續(xù)以上述算法為例，進(jìn)行分析：

1.

執(zhí)行次數(shù)最多的語句為num2+=num1

2.

T(n)=n*log2n

f(n)=n*log2n

3.

//lim(T(n)/f(n))=1

T(n)=O(n*log2n)

一些補(bǔ)充說明

最壞時(shí)間簡(jiǎn)單度

算法的時(shí)間簡(jiǎn)單度不僅與語句頻度有關(guān)，還與問題規(guī)模及輸入實(shí)例中各元素的取值有關(guān)。一般不特殊說明，爭(zhēng)論的時(shí)間簡(jiǎn)單度均是最壞狀況下的時(shí)間簡(jiǎn)單度。這就保證了算法的運(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ù)”。