時(shí)間復(fù)雜度-經(jīng)典解說課件

時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度--經(jīng)典解說課件算法時(shí)間復(fù)雜度的數(shù)學(xué)意義

從數(shù)學(xué)上定義，給定算法A，如果存在函數(shù)f(n)，當(dāng)n=k時(shí)，f(k)表示算法A在輸入規(guī)模為k的情況下的運(yùn)行時(shí)間，則稱f(n)為算法A的時(shí)間復(fù)雜度。其中：輸入規(guī)模是指算法A所接受輸入的自然獨(dú)立體的大小，我們總是假設(shè)算法的輸入規(guī)模是用大于零的整數(shù)表示的，即n=1,2,3,……,k,……算法時(shí)間復(fù)雜度的數(shù)學(xué)意義對(duì)于同一個(gè)算法，每次執(zhí)行的時(shí)間不僅取決于輸入規(guī)模，還取決于輸入的特性和具體的硬件環(huán)境在某次執(zhí)行時(shí)的狀態(tài)。所以想要得到一個(gè)統(tǒng)一精確的F(n)是不可能的。為此，通常做法：

1.忽略硬件及環(huán)境因素，假設(shè)每次執(zhí)行時(shí)硬件條件和環(huán)境條件是完全一致的。

2.對(duì)于輸入特性的差異，我們將從數(shù)學(xué)上進(jìn)行精確分析并帶入函數(shù)解析式。

對(duì)于同一個(gè)算法，每次執(zhí)行的時(shí)間不僅取決例子：x=1;

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

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

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

x++;

x++運(yùn)行次數(shù)：

例子：算法的漸近時(shí)間復(fù)雜度

很多時(shí)候，我們不需要進(jìn)行如此精確的分析，究其原因：

1.在較復(fù)雜的算法中，進(jìn)行精確分析是非常復(fù)雜的。

2.實(shí)際上，大多數(shù)時(shí)候我們并不關(guān)心F(n)的精確度量，而只是關(guān)心其量級(jí)。算法的漸近時(shí)間復(fù)雜度

很多時(shí)候，我們不需要進(jìn)行如算法復(fù)雜度的考察方法（1）考察一個(gè)算法的復(fù)雜度，一般考察的是當(dāng)問題復(fù)雜度n的增加時(shí)，運(yùn)算所需時(shí)間、空間代價(jià)f(n)的上下界。（2）進(jìn)一步而言，又分為最好情況、平均情況、最壞情況三種情況。通常最壞情況往往是我們最關(guān)注的。算法復(fù)雜度的考察方法（1）上界函數(shù)定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|T(n)|≤c|f(n)|則記作T(n)=Ο(f(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|f(n)|的一個(gè)常數(shù)倍。所以f(n)是計(jì)算時(shí)間T(n)的一個(gè)上界函數(shù)。試圖求出最小的f(n)，使得T(n)=Ο(f(n))。

（1）上界函數(shù)定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有時(shí)間復(fù)雜度--經(jīng)典解說課件在分析算法的時(shí)間復(fù)雜度時(shí)，我們更關(guān)心最壞情況而不是最好情況，理由如下：（1）最壞情況給出了算法執(zhí)行時(shí)間的上界，我們可以確信，無論給什么輸入，算法的執(zhí)行時(shí)間都不會(huì)超過這個(gè)上界，這樣為比較和分析提供了便利。（2）雖然最壞情況是一種悲觀估計(jì)，但是對(duì)于很多問題，平均情況和最壞情況的時(shí)間復(fù)雜度差不多，比如插入排序這個(gè)例子，平均情況和最壞情況的時(shí)間復(fù)雜度都是輸入長(zhǎng)度n的二次函數(shù)。在分析算法的時(shí)間復(fù)雜度時(shí)，我們更關(guān)心最壞情況而不是最好情況，定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|T(n)|≥c|g(n)|則記作T(n)=Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間T(n)的一個(gè)下界函數(shù)。試圖求出“最大”的g(n)，使得T(n)=Ω(g(n))。（2）下界函數(shù)定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0定義1.3如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有c1|g(n)|≤|T(n)|≤c2|g(n)|則記作含義：算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔蠺(n)=Ω(g(n))，又有T(n)=Ο(g(n))（3）“平均情況”限界函數(shù)定義1.3如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥時(shí)間復(fù)雜度--經(jīng)典解說課件常見算法時(shí)間復(fù)雜度：

O(1):表示算法的運(yùn)行時(shí)間為常量

O(n):表示該算法是線性算法

O(㏒2n):二分搜索算法

O(n㏒2n):快速排序算法O(n2):對(duì)數(shù)組進(jìn)行排序的各種簡(jiǎn)單算法，例如直接插入排序的算法。

O(n3):做兩個(gè)n階矩陣的乘法運(yùn)算

O(2n):求具有n個(gè)元素集合的所有子集的算法

O(n!):求具有N個(gè)元素的全排列的算法

優(yōu)<---------------------------<劣O(1)<O(㏒2n)<O(n)<O(n㏒2n):<O(n2)<O(2n)常見算法時(shí)間復(fù)雜度：

O(1):表示算法的運(yùn)行時(shí)間為常量

典型的計(jì)算時(shí)間函數(shù)曲線典型的計(jì)算時(shí)間函數(shù)曲線計(jì)算算法時(shí)間復(fù)雜度過程：（1）確定基本操作（2）構(gòu)造基于基本操作的函數(shù)解析式（3）求解函數(shù)解析式

計(jì)算算法時(shí)間復(fù)雜度過程：如果構(gòu)建的是遞推關(guān)系式，那么常用的求解方法有：（1）前向替換法可以從初始條件給出的序列初始項(xiàng)開始，使用遞推方程生成序列的前面若干項(xiàng)，寄希望于從中找出一個(gè)能夠用閉合公式表示的模式。如果找到了這樣的公式，我們可以用兩種方法對(duì)它進(jìn)行驗(yàn)證：第一，將它直接代入遞歸方程和初始條件中。第二，用數(shù)學(xué)歸納法來證明。如果構(gòu)建的是遞推關(guān)系式，那么常用的求解例如，考慮如下遞推式：X(n)=2X(n-1)+1n>1X(1)=1x(1)=1x(2)=2x(1)+1=2*1+1=3x(3)=2x(2)+1=2*3+1=7x(4)=2x(3)+1=2*7+1=15X(n)=2^n-1n>0例如，考慮如下遞推式：（2）反向替換法例如：X(n)=x(n-1)+n使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個(gè)結(jié)果代入原始方程，來把x(n)表示為x(n-2)的函數(shù)。重復(fù)這一過程。X(n)=x(0)+1+2+3+4+5…+n=0+1+2+3=4=n(n+1)/2（2）反向替換法X(n)=x(0)+1+2+3+4+5…+n（3）換名上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡(jiǎn)化為n/k規(guī)模的問題，為了方便求解，我們通常設(shè)定：n=km，則，上面的求解過程可簡(jiǎn)化為：f(n)=f(km-1)+b=f(km-2)+2b=…=f(k0)+mb=f(1)+blogn（3）換名上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為幾種常見復(fù)雜度舉例：O(logn)我們學(xué)過的算法，二分搜索intBinSrch(TypeA[],inti,intn,Typex)//A[i..n]是非遞減排列且1<=i<=n;{if(n==i){if(x==A[i])returni;elsereturn0;}else{intmid=(i+n)/2;if(x==A[mid])returnmid;----基本操作elseif(x<A[mid])returnBinSrh(A,i,mid-1,x);——遞歸調(diào)用elseif(x>A[mid])returnBinSrh(A,mid+1,n,x);——遞歸調(diào)用}}幾種常見復(fù)雜度舉例：intBinSrch(TypeA[]遞歸關(guān)系式：因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來的1/2，所以采用換名方法求解，設(shè)n=2k：C(n)=C(2k)=C(2k-1)+1=C(2k-2)+2=…=C(2k-k)+k=C(1)+k=logn+1遞歸關(guān)系式：因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來的1/2，所39172134576984921039172157698492103172157699210691021391721345769849210391721576984觀察遞歸調(diào)用的過程以及遞推關(guān)系式：（1）在遞歸關(guān)系式中：遞歸調(diào)用共有k次，我們?cè)O(shè)n=2k，k=logn（2）遞歸調(diào)用的二叉樹型結(jié)構(gòu)中，調(diào)用次數(shù)為二叉樹的深度。觀察遞歸調(diào)用的過程以及遞推關(guān)系式：2.O(n):表示該算法是線性算法

目前所學(xué)的算法中有：線性選擇算法intSelect(intdata[],intp,intr,intk){

if(p>r)return-1;//p不能大于r

if(p==r)returndata[p];//p<r

ints=partion(data,p,r);--------基本操作

if(s==k)returndata[s];

else

if(s>k){

intr1=Select(data,p,s-1,k);-----遞歸調(diào)用

returnr1;}

else

//s<k{

intr1=Select(data,s+1,r,k-s);-----遞歸調(diào)用

returnr1;}}2.O(n):表示該算法是線性算法

目前所25可編輯25可編輯如果遞歸調(diào)用，每次規(guī)模是原來的1/2：因?yàn)槊恳淮我?guī)模都減到原來的1/2，所以用換名的方法設(shè)n=2k：T(n)=T(n/2)+(n-1)=T(2k-1)+(2k-1)=[T(2k-2)+(2k-1-1)]+(2k-1)=…=[T(2k-k)+(21-1)]+…+(2k-1-1)+(2k-1)=T(1)+[(2k+1-2)-k]=2n-logn-1如果遞歸調(diào)用，每次規(guī)模是原來的1/2：因?yàn)槊恳淮我?guī)模都減到原算法時(shí)間復(fù)雜度：O(n)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是n。算法時(shí)間復(fù)雜度：O(n)算法的復(fù)雜度有兩部分決定：遞歸和合并3.O(nlogn)所學(xué)過的算法：快速排序、堆排序等，分治法中的平面中最接近點(diǎn)對(duì)問題。遞推關(guān)系式：3.O(nlogn)T(n)=2T(n/2)+n設(shè)n=2k =2T(2k-1)+2k=2[2T(2k-2)+2k-1]+2k=22T(2k-2)+2*2k=…=2k-1T(2k-(k-1))+(k-1)*2k=n/2+(logn-1)*nT(n)=2T(n/2)+n設(shè)n=2k不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個(gè)子問題，設(shè)n=mk，則：不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個(gè)子問題，設(shè)nT(n)=mT(n/m)+n =mT(mk-1)+mk=m[mT(mk-2)+mk-1]+mk=m2T(mk-2)+2*mk=…=mkT(2k-k)+k*mk=n+logn*nT(n)=mT(n/m)+n算法時(shí)間復(fù)雜度：O(nlogn)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是nlogn。算法時(shí)間復(fù)雜度：O(nlogn)算法的復(fù)雜度有兩部分決定：遞4.O(n2)通常的兩層嵌套循環(huán)，內(nèi)層的運(yùn)算執(zhí)行次數(shù)，學(xué)過的例子有：比賽日程4.O(n2)T(n)=T(n/m)+(n/m)2設(shè)n=mk=T(mk-1)+m2(k-1)=[T(mk-2)+m2(k-2)]+m2(k-1)

=…=[T(mk-k)+m0]+…+m2(k-2)+m2(k-1)

=1+(m2k-1)/(m2-1)=(n2-1)/(m2-1)+1所以：O(n2)T(n)=T(n/m)+(n/m)2設(shè)n=mk4.O(nk)所學(xué)過的：大整數(shù)乘法Recursive_Miltiply(x,y){

ifn=1

if(X=1)and(Y=1)return(1)

elsereturn(0)

x1=X的左邊n/2位;

x0=X的右邊n/2位;

y1=Y的左邊n/2位;

y0=Y的右邊n/2位; p=Recursive_Miltiply(x1+x0,y1+y0);——遞歸調(diào)用 x1y1=Recursive_Miltiply(x1,y1);——遞歸調(diào)用 x0y0=Recursive_Miltiply(x0,y0);——遞歸調(diào)用 returnx1y1*2n+(p-x1y1-x0y0)*2n/2+x0y0;——基本操作}4.O(nk)Recursive_Miltiply(x,y)設(shè)，n=2k,用反向替換法對(duì)它求解：設(shè)，n=2k,用反向替換法對(duì)它求解：分析：在這個(gè)遞推關(guān)系式中，算法每次遞歸調(diào)用3個(gè)規(guī)模為1/2的子問題，那么總的規(guī)模3/2，大小，所以，粗略估算要在O(nlogn)、O(n2)之間。分析：相關(guān)習(xí)題求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10nn2/10+2n21+1/nlogn310log3n=O(n2)=O(2n)=O(1)=O(logn)=O(n)相關(guān)習(xí)題=O(n2)2.討論O(1)和O(2)區(qū)別：定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)|≤c|g(n)|則記作f(n)=Ο(g(n))O(1)=O(2)相差的只是常數(shù)因子2.討論O(1)和O(2)區(qū)別：定義1如果存在兩個(gè)正常數(shù)3.算法效率（1）假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t?，F(xiàn)在有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問題，則：t=3*2n1/64=3*2n1-6所以，n1=n+63.算法效率設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問題，則：(2)若上述的算法改為T(n)=n2，其他條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問題？n12=64n2=(8n)2能解規(guī)模為8n的問題(2)若上述的算法改為T(n)=n2，其他條件不變，則在新(3)若上述的算法改為T(n)=8，其他條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問題？由于T(n)是常數(shù)，所以可以解任意規(guī)模的問題。(3)若上述的算法改為T(n)=8，其他條件不變，則在新機(jī)4.對(duì)于下列各組函數(shù)f(n)g(n)，確定f(n)=O(g(n)，或f（n)=(g(n)，或f(n)=(g(n))f(n)=logn2g(n)=logn+5f(n)=logn2g(n)=f(n)=ng(n)=log2nf(n)=nlogng(n)=log(n)f(n)=10g(n)=log10f(n)=log2ng(n)=lognf(n)=2ng(n)=100n2f(n)=2ng(n)=3n4.對(duì)于下列各組函數(shù)f(n)g(n)，確定f(n)=O(5.螺釘和螺母問題假設(shè)我們有n個(gè)直徑各不相同的螺釘，以及n個(gè)相應(yīng)的螺母。我們一次只能比較一對(duì)螺釘和螺母，來判斷螺母是大于螺釘、小于螺釘還是正好合適螺釘。然而，我們不能拿兩個(gè)螺母作比較，也不能拿兩個(gè)螺釘作比較。我們的問題是要找到每一對(duì)匹配的螺釘和螺母，為該問題設(shè)計(jì)算法，他的平均效率符合(nlogn)5.螺釘和螺母問題6.設(shè)n個(gè)不同的整數(shù)排好序后存于t[0:n-1]中。若存在一個(gè)下標(biāo)i，0<=i<=n-1，使得t[i]=i，設(shè)計(jì)一個(gè)算法找到這個(gè)下標(biāo)，最壞的情況下計(jì)算時(shí)間O(logn)。6.設(shè)n個(gè)不同的整數(shù)排好序后存于t[0:n-1]中。若存在一7.輸油管道問題某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過一個(gè)有n口油井的油田。從每口油井都要有一條輸油管道沿最短路徑(或南或北)與主管道相連。如果給定n口油井的位置，即它們的x坐標(biāo)和y坐標(biāo)，應(yīng)如何確定主管道的最優(yōu)位置，即使各油井到主管道之間的輸油管道長(zhǎng)度總和最小的位置？7.輸油管道問題時(shí)間復(fù)雜度--經(jīng)典解說課件時(shí)間復(fù)雜度--經(jīng)典解說課件時(shí)間復(fù)雜度--經(jīng)典解說課件50可編輯50可編輯時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度--經(jīng)典解說課件算法時(shí)間復(fù)雜度的數(shù)學(xué)意義

從數(shù)學(xué)上定義，給定算法A，如果存在函數(shù)f(n)，當(dāng)n=k時(shí)，f(k)表示算法A在輸入規(guī)模為k的情況下的運(yùn)行時(shí)間，則稱f(n)為算法A的時(shí)間復(fù)雜度。其中：輸入規(guī)模是指算法A所接受輸入的自然獨(dú)立體的大小，我們總是假設(shè)算法的輸入規(guī)模是用大于零的整數(shù)表示的，即n=1,2,3,……,k,……算法時(shí)間復(fù)雜度的數(shù)學(xué)意義對(duì)于同一個(gè)算法，每次執(zhí)行的時(shí)間不僅取決于輸入規(guī)模，還取決于輸入的特性和具體的硬件環(huán)境在某次執(zhí)行時(shí)的狀態(tài)。所以想要得到一個(gè)統(tǒng)一精確的F(n)是不可能的。為此，通常做法：

1.忽略硬件及環(huán)境因素，假設(shè)每次執(zhí)行時(shí)硬件條件和環(huán)境條件是完全一致的。

2.對(duì)于輸入特性的差異，我們將從數(shù)學(xué)上進(jìn)行精確分析并帶入函數(shù)解析式。

對(duì)于同一個(gè)算法，每次執(zhí)行的時(shí)間不僅取決例子：x=1;

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

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

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

x++;

x++運(yùn)行次數(shù)：

例子：算法的漸近時(shí)間復(fù)雜度

很多時(shí)候，我們不需要進(jìn)行如此精確的分析，究其原因：

1.在較復(fù)雜的算法中，進(jìn)行精確分析是非常復(fù)雜的。

2.實(shí)際上，大多數(shù)時(shí)候我們并不關(guān)心F(n)的精確度量，而只是關(guān)心其量級(jí)。算法的漸近時(shí)間復(fù)雜度

很多時(shí)候，我們不需要進(jìn)行如算法復(fù)雜度的考察方法（1）考察一個(gè)算法的復(fù)雜度，一般考察的是當(dāng)問題復(fù)雜度n的增加時(shí)，運(yùn)算所需時(shí)間、空間代價(jià)f(n)的上下界。（2）進(jìn)一步而言，又分為最好情況、平均情況、最壞情況三種情況。通常最壞情況往往是我們最關(guān)注的。算法復(fù)雜度的考察方法（1）上界函數(shù)定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|T(n)|≤c|f(n)|則記作T(n)=Ο(f(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|f(n)|的一個(gè)常數(shù)倍。所以f(n)是計(jì)算時(shí)間T(n)的一個(gè)上界函數(shù)。試圖求出最小的f(n)，使得T(n)=Ο(f(n))。

（1）上界函數(shù)定義1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有時(shí)間復(fù)雜度--經(jīng)典解說課件在分析算法的時(shí)間復(fù)雜度時(shí)，我們更關(guān)心最壞情況而不是最好情況，理由如下：（1）最壞情況給出了算法執(zhí)行時(shí)間的上界，我們可以確信，無論給什么輸入，算法的執(zhí)行時(shí)間都不會(huì)超過這個(gè)上界，這樣為比較和分析提供了便利。（2）雖然最壞情況是一種悲觀估計(jì)，但是對(duì)于很多問題，平均情況和最壞情況的時(shí)間復(fù)雜度差不多，比如插入排序這個(gè)例子，平均情況和最壞情況的時(shí)間復(fù)雜度都是輸入長(zhǎng)度n的二次函數(shù)。在分析算法的時(shí)間復(fù)雜度時(shí)，我們更關(guān)心最壞情況而不是最好情況，定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|T(n)|≥c|g(n)|則記作T(n)=Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間T(n)的一個(gè)下界函數(shù)。試圖求出“最大”的g(n)，使得T(n)=Ω(g(n))。（2）下界函數(shù)定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0定義1.3如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有c1|g(n)|≤|T(n)|≤c2|g(n)|則記作含義：算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔蠺(n)=Ω(g(n))，又有T(n)=Ο(g(n))（3）“平均情況”限界函數(shù)定義1.3如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥時(shí)間復(fù)雜度--經(jīng)典解說課件常見算法時(shí)間復(fù)雜度：

O(1):表示算法的運(yùn)行時(shí)間為常量

O(n):表示該算法是線性算法

O(㏒2n):二分搜索算法

O(n㏒2n):快速排序算法O(n2):對(duì)數(shù)組進(jìn)行排序的各種簡(jiǎn)單算法，例如直接插入排序的算法。

O(n3):做兩個(gè)n階矩陣的乘法運(yùn)算

O(2n):求具有n個(gè)元素集合的所有子集的算法

O(n!):求具有N個(gè)元素的全排列的算法

優(yōu)<---------------------------<劣O(1)<O(㏒2n)<O(n)<O(n㏒2n):<O(n2)<O(2n)常見算法時(shí)間復(fù)雜度：

O(1):表示算法的運(yùn)行時(shí)間為常量

典型的計(jì)算時(shí)間函數(shù)曲線典型的計(jì)算時(shí)間函數(shù)曲線計(jì)算算法時(shí)間復(fù)雜度過程：（1）確定基本操作（2）構(gòu)造基于基本操作的函數(shù)解析式（3）求解函數(shù)解析式

計(jì)算算法時(shí)間復(fù)雜度過程：如果構(gòu)建的是遞推關(guān)系式，那么常用的求解方法有：（1）前向替換法可以從初始條件給出的序列初始項(xiàng)開始，使用遞推方程生成序列的前面若干項(xiàng)，寄希望于從中找出一個(gè)能夠用閉合公式表示的模式。如果找到了這樣的公式，我們可以用兩種方法對(duì)它進(jìn)行驗(yàn)證：第一，將它直接代入遞歸方程和初始條件中。第二，用數(shù)學(xué)歸納法來證明。如果構(gòu)建的是遞推關(guān)系式，那么常用的求解例如，考慮如下遞推式：X(n)=2X(n-1)+1n>1X(1)=1x(1)=1x(2)=2x(1)+1=2*1+1=3x(3)=2x(2)+1=2*3+1=7x(4)=2x(3)+1=2*7+1=15X(n)=2^n-1n>0例如，考慮如下遞推式：（2）反向替換法例如：X(n)=x(n-1)+n使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個(gè)結(jié)果代入原始方程，來把x(n)表示為x(n-2)的函數(shù)。重復(fù)這一過程。X(n)=x(0)+1+2+3+4+5…+n=0+1+2+3=4=n(n+1)/2（2）反向替換法X(n)=x(0)+1+2+3+4+5…+n（3）換名上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡(jiǎn)化為n/k規(guī)模的問題，為了方便求解，我們通常設(shè)定：n=km，則，上面的求解過程可簡(jiǎn)化為：f(n)=f(km-1)+b=f(km-2)+2b=…=f(k0)+mb=f(1)+blogn（3）換名上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為幾種常見復(fù)雜度舉例：O(logn)我們學(xué)過的算法，二分搜索intBinSrch(TypeA[],inti,intn,Typex)//A[i..n]是非遞減排列且1<=i<=n;{if(n==i){if(x==A[i])returni;elsereturn0;}else{intmid=(i+n)/2;if(x==A[mid])returnmid;----基本操作elseif(x<A[mid])returnBinSrh(A,i,mid-1,x);——遞歸調(diào)用elseif(x>A[mid])returnBinSrh(A,mid+1,n,x);——遞歸調(diào)用}}幾種常見復(fù)雜度舉例：intBinSrch(TypeA[]遞歸關(guān)系式：因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來的1/2，所以采用換名方法求解，設(shè)n=2k：C(n)=C(2k)=C(2k-1)+1=C(2k-2)+2=…=C(2k-k)+k=C(1)+k=logn+1遞歸關(guān)系式：因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來的1/2，所39172134576984921039172157698492103172157699210691021391721345769849210391721576984觀察遞歸調(diào)用的過程以及遞推關(guān)系式：（1）在遞歸關(guān)系式中：遞歸調(diào)用共有k次，我們?cè)O(shè)n=2k，k=logn（2）遞歸調(diào)用的二叉樹型結(jié)構(gòu)中，調(diào)用次數(shù)為二叉樹的深度。觀察遞歸調(diào)用的過程以及遞推關(guān)系式：2.O(n):表示該算法是線性算法

目前所學(xué)的算法中有：線性選擇算法intSelect(intdata[],intp,intr,intk){

if(p>r)return-1;//p不能大于r

if(p==r)returndata[p];//p<r

ints=partion(data,p,r);--------基本操作

if(s==k)returndata[s];

else

if(s>k){

intr1=Select(data,p,s-1,k);-----遞歸調(diào)用

returnr1;}

else

//s<k{

intr1=Select(data,s+1,r,k-s);-----遞歸調(diào)用

returnr1;}}2.O(n):表示該算法是線性算法

目前所75可編輯25可編輯如果遞歸調(diào)用，每次規(guī)模是原來的1/2：因?yàn)槊恳淮我?guī)模都減到原來的1/2，所以用換名的方法設(shè)n=2k：T(n)=T(n/2)+(n-1)=T(2k-1)+(2k-1)=[T(2k-2)+(2k-1-1)]+(2k-1)=…=[T(2k-k)+(21-1)]+…+(2k-1-1)+(2k-1)=T(1)+[(2k+1-2)-k]=2n-logn-1如果遞歸調(diào)用，每次規(guī)模是原來的1/2：因?yàn)槊恳淮我?guī)模都減到原算法時(shí)間復(fù)雜度：O(n)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是n。算法時(shí)間復(fù)雜度：O(n)算法的復(fù)雜度有兩部分決定：遞歸和合并3.O(nlogn)所學(xué)過的算法：快速排序、堆排序等，分治法中的平面中最接近點(diǎn)對(duì)問題。遞推關(guān)系式：3.O(nlogn)T(n)=2T(n/2)+n設(shè)n=2k =2T(2k-1)+2k=2[2T(2k-2)+2k-1]+2k=22T(2k-2)+2*2k=…=2k-1T(2k-(k-1))+(k-1)*2k=n/2+(logn-1)*nT(n)=2T(n/2)+n設(shè)n=2k不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個(gè)子問題，設(shè)n=mk，則：不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個(gè)子問題，設(shè)nT(n)=mT(n/m)+n =mT(mk-1)+mk=m[mT(mk-2)+mk-1]+mk=m2T(mk-2)+2*mk=…=mkT(2k-k)+k*mk=n+logn*nT(n)=mT(n/m)+n算法時(shí)間復(fù)雜度：O(nlogn)分析：算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是nlogn。算法時(shí)間復(fù)雜度：O(nlogn)算法的復(fù)雜度有兩部分決定：遞4.O(n2)通常的兩層嵌套循環(huán)，內(nèi)層的運(yùn)算執(zhí)行次數(shù)，學(xué)過的例子有：比賽日程4.O(n2)T(n)=T(n/m)+(n/m)2設(shè)n=mk=T(mk-1)+m2(k-1)=[T(mk-2)+m2(k-2)]+m2(k-1)

=…=[T(mk-k)+m0]+…+m2(k-2)+m2(k-1)

=1+(m2k-1)/(m2-1)=(n2-1)/(m2-1)+1所以：O(n2)T(n)=T(n/m)+(n/m)2設(shè)n=mk4.O(nk)所學(xué)過的：大整數(shù)乘法Recursive_Miltiply(x,y){

ifn=1

if(X=1)and(Y=1)return(1)

elsereturn(0)

x1=X的左邊n/2位;

x0=X的右邊n/2位;

y1=Y的左邊n/2位;

y0=Y的右邊n/2位; p=Recursive_Miltiply(x1+x0,y1+y0);——遞歸調(diào)用 x1y1=Recursive_Miltiply(x1,y1);——遞歸調(diào)用 x0y0=Recursive_Miltiply(x0,y0);——遞歸調(diào)用 returnx1y1*2n+(p-x1y1-x0y0)*2n/2+x0y0;——基本操作}4.O(nk)Recursive_Miltiply(x,y)設(shè)，n=2k,用反向替換法對(duì)它求解：設(shè)，n=2k,用反向替換法對(duì)它求解：分析：在這個(gè)遞推關(guān)系式中，算法每次遞歸調(diào)用3個(gè)規(guī)模為1/2的子問題，那么總的規(guī)模3/2，大小，所以，粗略估算