轉(zhuǎn)載自?http://blog.csdn.net/eirlys_north/article/details/52959540

好的算法應(yīng)該具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)亥贸，這里只介紹前者

一耕肩、定義（理解不了沒(méi)關(guān)系磁餐，理解得了還寫(xiě)什么博客）

?????一般情況下尉桩，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)谷异，用T(n)表示仓手，若有某個(gè)輔助函數(shù)f(n)向瓷，使得當(dāng)n趨近于無(wú)窮大時(shí)睡互，T(n)/f(n)的極限值為不等于零的常數(shù)根竿，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))就珠，稱(chēng)O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度(O是數(shù)量級(jí)的符號(hào) )寇壳，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。

1妻怎、咱們來(lái)搞懂定義=w=

（1）時(shí)間頻度

????一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間壳炎，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道逼侦。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試匿辩，只需知道算法花費(fèi)的時(shí)間多少（魔鏡魔鏡告訴我，那個(gè)算法是跑得快的算法0.0）

????一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例榛丢，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多铲球，它花費(fèi)時(shí)間就多。

????一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度晰赞。記為T(mén)(n)稼病。

（2）時(shí)間復(fù)雜度

?????n稱(chēng)為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)宾肺，時(shí)間頻度T(n)也會(huì)不斷變化溯饵。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此锨用，我們引入時(shí)間復(fù)雜度概念丰刊。

?????一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)增拥，用T(n)表示啄巧，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)寻歧，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)秩仆。記作T(n)=Ｏ(f(n))

????稱(chēng)Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度码泛，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。

注意澄耍，時(shí)間頻度與時(shí)間復(fù)雜度是不同的噪珊，時(shí)間頻度不同但時(shí)間復(fù)雜度可能相同。

如：T(n)=n^2+3n+4與T(n)=4n2+2n+1它們的頻度不同齐莲，但時(shí)間復(fù)雜度相同痢站，都為O(n^2)。

常見(jiàn)的時(shí)間復(fù)雜度有：

常數(shù)階O(1)<對(duì)數(shù)階O(log2n)<線性階O(n),<線性對(duì)數(shù)階O(nlog2n)

<平方階O(n^2)<方階O(n3)

<指數(shù)階O(2^n)

?

?

?

?（3）最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 　最壞情況下的時(shí)間復(fù)雜度稱(chēng)最壞時(shí)間復(fù)雜度选酗。一般不特別說(shuō)明阵难，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界芒填，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)呜叫。

?????在最壞情況下的時(shí)間復(fù)雜度為T(mén)(n)=0(n)，它表示對(duì)于任何輸入實(shí)例,該算法的運(yùn)行時(shí)間不可能大于0(n)殿衰。 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下朱庆，算法的期望運(yùn)行時(shí)間。

指數(shù)階0(2n)闷祥，顯然椎工，時(shí)間復(fù)雜度為指數(shù)階0(2n)的算法效率極低，當(dāng)n值稍大時(shí)就無(wú)法應(yīng)用蜀踏。

2维蒙、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度

對(duì)于時(shí)間復(fù)雜度的分析，一般是這兩種方法：

（1）最壞時(shí)間復(fù)雜度

????最壞情況運(yùn)行時(shí)間(運(yùn)行時(shí)間將不會(huì)再壞了=A=)果覆。

通常颅痊，除非特別指定，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間

對(duì)于追問(wèn)為什么是最壞時(shí)間復(fù)雜度的好奇寶寶：

1局待、如果最差情況下的復(fù)雜度符合我們的要求斑响，我們就可以保證所有的情況下都不會(huì)有問(wèn)題。（完美=w=）

2钳榨、也許你覺(jué)得平均情況下的復(fù)雜度更吸引你（見(jiàn)下）舰罚，但是：第一，難計(jì)算第二薛耻，有很多算法的平均情況和最差情況的復(fù)雜度是一樣的. 第三营罢，而且輸入數(shù)據(jù)的分布函數(shù)很可能是你沒(méi)法知道。

?

(2)平均時(shí)間復(fù)雜度

平均時(shí)間復(fù)雜度也是從概率的角度看，更能反映大多數(shù)情況下算法的表現(xiàn)饲漾。當(dāng)然蝙搔，實(shí)際中不可能將所有可能的輸入都運(yùn)行一遍，因此平均情況通常指的是一種數(shù)學(xué)期望值考传，而計(jì)算數(shù)學(xué)期望值則需要對(duì)輸入的分布情況進(jìn)行假設(shè)吃型。平均運(yùn)行時(shí)間很難通過(guò)分析得到，一般都是通過(guò)運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來(lái)的僚楞。

3勤晚、閑聊

???到此，基本介紹已經(jīng)完成了=w=泉褐，下一部分就是怎么去計(jì)算了运翼，

當(dāng)你看到這里的時(shí)候，

你就能明白那些大犇所說(shuō)的時(shí)間復(fù)雜度是個(gè)什么鬼兴枯，

知道哪個(gè)算法跑得快也就是擇優(yōu)的標(biāo)準(zhǔn)（雖然你還不會(huì)求=。=）矩欠，

于是你也能知道在數(shù)據(jù)范圍下财剖，大概會(huì)選用哪種時(shí)間復(fù)雜度的方法以及你會(huì)不會(huì)TLE（雖然你還不會(huì)求=。=）

舉個(gè)栗子（就不給你吃）癌淮，比如我要求你在字典里查同一個(gè)字躺坟，告訴我這個(gè)字在字典的那一頁(yè)。如果一頁(yè)一頁(yè)的翻乳蓄，你需要多少時(shí)間呢咪橙？最優(yōu)的情況就是這個(gè)字在第一頁(yè)，最壞的情況就是這個(gè)字是整本字典的最后一個(gè)字虚倒。所以即使我故意為難你美侦，你也不會(huì)花費(fèi)比找整本字典最后一個(gè)字還長(zhǎng)的時(shí)間。

當(dāng)然魂奥，此時(shí)聰明的你就會(huì)想用部首菠剩、筆畫(huà)等去查，才不要傻乎乎的一頁(yè)一頁(yè)翻耻煤，此時(shí)的你就會(huì)擇優(yōu)選擇具壮，因?yàn)榇藭r(shí)你最壞得情況就是我給你部首筆畫(huà)最多、除部首外筆畫(huà)最多的一個(gè)超級(jí)復(fù)雜的一個(gè)字哈蝇，但顯然比翻整本字典快得多棺妓。

誒呀，一不小心已經(jīng)不僅會(huì)選擇而且還會(huì)優(yōu)化了呢=w=

二炮赦、求時(shí)間復(fù)雜度?

1怜跑、根據(jù)定義，可以歸納出基本的計(jì)算步驟

（1.）計(jì)算出基本操作的執(zhí)行次數(shù)T(n)

基本操作即算法中的每條語(yǔ)句的執(zhí)行次數(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來(lái)表示時(shí)間復(fù)雜度

例:

??for（i=1;i<=n;++i）

??{

?????for(j=1;j<=n;++j)

?????{

?????????c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^2

??????????for(k=1;k<=n;++k)

???????????????c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^3

?????}

??}

??則有 T（n）= n^2+n^3批旺，根據(jù)上面括號(hào)里的同數(shù)量級(jí)幌陕，我們可以確定 n^3為T(mén)（n）的同數(shù)量級(jí)

??則有f（n）= n^3，然后根據(jù)T（n）/f（n）求極限可得到常數(shù)c

??則該算法的 時(shí)間復(fù)雜度：T（n）=O（n^3)

2汽煮、于是我們發(fā)現(xiàn)根本沒(méi)必要都算搏熄，所以我們有了精簡(jiǎn)后的步驟：

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

2. 計(jì)算語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)3. 用大O來(lái)表示結(jié)果

eg:

(1) ??for(i=1;i<=n;i++) ????//循環(huán)了n*n次，當(dāng)然是O(n^2)

????????????for(j=1;j<=n;j++)

?????????????????s++;

（2）for(i=1;i<=n;i++) ??//循環(huán)了(n+n-1+...+1)≈(n^2)/2 ,同上 ?????????????????????????????????????????????

???????????for(j=i;j<=n;j++)

?????????????????s++;

(4) ??i=1;k=0;

??????while(i<=n-1){

???????????k+=10*i;

??????i++; ?????}

//循環(huán)了

//n-1≈n次暇赤，所以是O(n)

(5) ??for(i=1;i<=n;i++)

?????????????for(j=1;j<=i;j++)

?????????????????for(k=1;k<=j;k++)

???????????????????????x=x+1;

//循環(huán)了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3心例，

//即O（n^3)

（6)

x=91; y=100;

while(y>0) if(x>100) {x=x-10;y--;} else x++;

?//T(n)=O(1)，與n無(wú)關(guān)

（7）i=n-1; ???????????

while(i>=0&&(A[i]!=k)) ??????

??????i--; ???????

return i; ??

//此算法中的語(yǔ)句(3)的頻度不僅與問(wèn)題規(guī)模n有關(guān)鞋囊，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān): ①若A中沒(méi)有與K相等的元素止后，則語(yǔ)句(3)的頻度f(wàn)(n)=n； ②若A的最后一個(gè)元素等于K,則語(yǔ)句(3)的頻度f(wàn)(n)是常數(shù)0溜腐。

綜上：

1译株、取決于執(zhí)行次數(shù)最多的語(yǔ)句，如當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)挺益，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的歉糜。

2、如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)望众，即使算法中有上千條語(yǔ)句匪补，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)

3烂翰、算法的時(shí)間復(fù)雜度不僅僅依賴(lài)于問(wèn)題的規(guī)模夯缺，還與輸入實(shí)例的初始狀態(tài)有關(guān)。

好的算法應(yīng)該具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)甘耿，這里只介紹前者

一喳逛、定義（理解不了沒(méi)關(guān)系，理解得了還寫(xiě)什么博客）

?????一般情況下棵里，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)润文，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)殿怜，使得當(dāng)n趨近于無(wú)窮大時(shí)典蝌，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)头谜。記作T(n)=O(f(n))骏掀，稱(chēng)O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度(O是數(shù)量級(jí)的符號(hào) )，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。

1截驮、咱們來(lái)搞懂定義=w=

（1）時(shí)間頻度

????一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間笑陈，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道葵袭。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試涵妥，只需知道算法花費(fèi)的時(shí)間多少（魔鏡魔鏡告訴我，那個(gè)算法是跑得快的算法0.0）

????一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例坡锡，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多蓬网，它花費(fèi)時(shí)間就多。

????一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度鹉勒。記為T(mén)(n)帆锋。

（2）時(shí)間復(fù)雜度

?????n稱(chēng)為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)禽额，時(shí)間頻度T(n)也會(huì)不斷變化锯厢。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此脯倒，我們引入時(shí)間復(fù)雜度概念实辑。

?????一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)盔憨，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)讯沈，T（n)/f(n)的極限值為不等于零的常數(shù)郁岩，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n))

????稱(chēng)Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度缺狠，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度问慎。

注意，時(shí)間頻度與時(shí)間復(fù)雜度是不同的挤茄，時(shí)間頻度不同但時(shí)間復(fù)雜度可能相同如叼。

如：T(n)=n^2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同穷劈，都為O(n^2)笼恰。

常見(jiàn)的時(shí)間復(fù)雜度有：

常數(shù)階O(1)<對(duì)數(shù)階O(log2n)<線性階O(n),<線性對(duì)數(shù)階O(nlog2n)

<平方階O(n^2)<方階O(n3)

<指數(shù)階O(2^n)

?

?

?

?（3）最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 　最壞情況下的時(shí)間復(fù)雜度稱(chēng)最壞時(shí)間復(fù)雜度。一般不特別說(shuō)明歇终，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度社证。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)评凝。

?????在最壞情況下的時(shí)間復(fù)雜度為T(mén)(n)=0(n)追葡，它表示對(duì)于任何輸入實(shí)例,該算法的運(yùn)行時(shí)間不可能大于0(n)。 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間宜肉。

指數(shù)階0(2n)匀钧，顯然，時(shí)間復(fù)雜度為指數(shù)階0(2n)的算法效率極低谬返，當(dāng)n值稍大時(shí)就無(wú)法應(yīng)用之斯。

2、最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度

對(duì)于時(shí)間復(fù)雜度的分析朱浴，一般是這兩種方法：

（1）最壞時(shí)間復(fù)雜度

????最壞情況運(yùn)行時(shí)間(運(yùn)行時(shí)間將不會(huì)再壞了=A=)吊圾。

通常，除非特別指定翰蠢，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間

對(duì)于追問(wèn)為什么是最壞時(shí)間復(fù)雜度的好奇寶寶：

1项乒、如果最差情況下的復(fù)雜度符合我們的要求，我們就可以保證所有的情況下都不會(huì)有問(wèn)題梁沧。（完美=w=）

2檀何、也許你覺(jué)得平均情況下的復(fù)雜度更吸引你（見(jiàn)下），但是：第一廷支，難計(jì)算第二频鉴，有很多算法的平均情況和最差情況的復(fù)雜度是一樣的. 第三，而且輸入數(shù)據(jù)的分布函數(shù)很可能是你沒(méi)法知道恋拍。

?

(2)平均時(shí)間復(fù)雜度

平均時(shí)間復(fù)雜度也是從概率的角度看垛孔，更能反映大多數(shù)情況下算法的表現(xiàn)。當(dāng)然施敢，實(shí)際中不可能將所有可能的輸入都運(yùn)行一遍周荐，因此平均情況通常指的是一種數(shù)學(xué)期望值，而計(jì)算數(shù)學(xué)期望值則需要對(duì)輸入的分布情況進(jìn)行假設(shè)僵娃。平均運(yùn)行時(shí)間很難通過(guò)分析得到概作，一般都是通過(guò)運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來(lái)的。

3默怨、閑聊

???到此讯榕，基本介紹已經(jīng)完成了=w=，下一部分就是怎么去計(jì)算了匙睹，

當(dāng)你看到這里的時(shí)候愚屁，

你就能明白那些大犇所說(shuō)的時(shí)間復(fù)雜度是個(gè)什么鬼，

知道哪個(gè)算法跑得快也就是擇優(yōu)的標(biāo)準(zhǔn)（雖然你還不會(huì)求=痕檬。=）集绰，

于是你也能知道在數(shù)據(jù)范圍下，大概會(huì)選用哪種時(shí)間復(fù)雜度的方法以及你會(huì)不會(huì)TLE（雖然你還不會(huì)求=谆棺。=）

舉個(gè)栗子（就不給你吃）栽燕，比如我要求你在字典里查同一個(gè)字罕袋，告訴我這個(gè)字在字典的那一頁(yè)。如果一頁(yè)一頁(yè)的翻碍岔，你需要多少時(shí)間呢浴讯？最優(yōu)的情況就是這個(gè)字在第一頁(yè)，最壞的情況就是這個(gè)字是整本字典的最后一個(gè)字蔼啦。所以即使我故意為難你榆纽，你也不會(huì)花費(fèi)比找整本字典最后一個(gè)字還長(zhǎng)的時(shí)間。

當(dāng)然捏肢，此時(shí)聰明的你就會(huì)想用部首奈籽、筆畫(huà)等去查，才不要傻乎乎的一頁(yè)一頁(yè)翻鸵赫，此時(shí)的你就會(huì)擇優(yōu)選擇衣屏，因?yàn)榇藭r(shí)你最壞得情況就是我給你部首筆畫(huà)最多、除部首外筆畫(huà)最多的一個(gè)超級(jí)復(fù)雜的一個(gè)字辩棒，但顯然比翻整本字典快得多狼忱。

誒呀，一不小心已經(jīng)不僅會(huì)選擇而且還會(huì)優(yōu)化了呢=w=

二一睁、求時(shí)間復(fù)雜度?

1钻弄、根據(jù)定義，可以歸納出基本的計(jì)算步驟

（1.）計(jì)算出基本操作的執(zhí)行次數(shù)T(n)

基本操作即算法中的每條語(yǔ)句的執(zhí)行次數(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來(lái)表示時(shí)間復(fù)雜度

例:

??for（i=1;i<=n;++i）

??{

?????for(j=1;j<=n;++j)

?????{

?????????c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^2

??????????for(k=1;k<=n;++k)

???????????????c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^3

?????}

??}

??則有 T（n）= n^2+n^3瘤泪，根據(jù)上面括號(hào)里的同數(shù)量級(jí)，我們可以確定 n^3為T(mén)（n）的同數(shù)量級(jí)

??則有f（n）= n^3染坯，然后根據(jù)T（n）/f（n）求極限可得到常數(shù)c

??則該算法的 時(shí)間復(fù)雜度：T（n）=O（n^3)

2均芽、于是我們發(fā)現(xiàn)根本沒(méi)必要都算丘逸，所以我們有了精簡(jiǎn)后的步驟：

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

2. 計(jì)算語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)3. 用大O來(lái)表示結(jié)果

eg:

(1) ??for(i=1;i<=n;i++) ????//循環(huán)了n*n次单鹿，當(dāng)然是O(n^2)

????????????for(j=1;j<=n;j++)

?????????????????s++;

（2）for(i=1;i<=n;i++) ??//循環(huán)了(n+n-1+...+1)≈(n^2)/2 ,同上 ?????????????????????????????????????????????

???????????for(j=i;j<=n;j++)

?????????????????s++;

(4) ??i=1;k=0;

??????while(i<=n-1){

???????????k+=10*i;

??????i++; ?????}

//循環(huán)了

//n-1≈n次，所以是O(n)

(5) ??for(i=1;i<=n;i++)

?????????????for(j=1;j<=i;j++)

?????????????????for(k=1;k<=j;k++)

???????????????????????x=x+1;

//循環(huán)了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3深纲，

//即O（n^3)

（6)

x=91; y=100;

while(y>0) if(x>100) {x=x-10;y--;} else x++;

?//T(n)=O(1)仲锄，與n無(wú)關(guān)

（7）i=n-1; ???????????

while(i>=0&&(A[i]!=k)) ??????

??????i--; ???????

return i; ??

//此算法中的語(yǔ)句(3)的頻度不僅與問(wèn)題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān): ①若A中沒(méi)有與K相等的元素湃鹊，則語(yǔ)句(3)的頻度f(wàn)(n)=n儒喊； ②若A的最后一個(gè)元素等于K,則語(yǔ)句(3)的頻度f(wàn)(n)是常數(shù)0。

綜上：

1币呵、取決于執(zhí)行次數(shù)最多的語(yǔ)句怀愧，如當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)侨颈，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。

2芯义、如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)哈垢，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)扛拨。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)

3耘分、算法的時(shí)間復(fù)雜度不僅僅依賴(lài)于問(wèn)題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)绑警。