第二章算法分析基礎(chǔ)1234算法時間復(fù)雜性分析算法空間復(fù)雜性分析最優(yōu)算法小結(jié)公元5世紀(jì)末，我國古代數(shù)學(xué)家張丘建在他所撰寫的《算經(jīng)》中，提出了這樣一個問題：“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何？”意思是公雞每只5元、母雞每只3元、小雞3只1元，用100元錢買100只雞，求公雞、母雞、小雞的只數(shù)。案例一——百雞問題令a為公雞只數(shù)，b為母雞只數(shù)，c為小雞只數(shù)。列出約束方程：

a+b+c=100（1）

5a+3b+c/3=100（2）

c%3=0（3）分析:a、b、c的可能取值范圍為0~100，對a、b、c的所有組合進(jìn)行測試，滿足約束方程的組合是問題的解。把問題轉(zhuǎn)化為用n元錢買n只雞，則上式變?yōu)椋篴+b+c=n

（1'）

5a+3b+c/3=n

（2'）案例一——百雞問題算法1百雞問題1.voidchicken_question(intn,int&k,intg[],intm[],ints[])2.{3.inta,b,c;4.k=0; 5.for(a=0;a<=n;a++){6.for(b=0;b<=n;b++){7.for(c=0;c<=n;c++){8.if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)){9.g[k]=a;10.m[k]=b;11.s[k]=c;12.k++;13.}14.}15.}16.}17.}算法2改進(jìn)的百雞問題1.voidchicken_problem(intn,int&k,intg[],intm[],ints[])2.{inti,j,a,b,c;k=0;i=n/5;j=n/3;3.for(a=0;a<=i;a++){4.for(b=0;b<=j;b++){5.c=n–a–b;6.if((5*a+3*b+c/3==n)&&(c%3==0)){7.g[k]=a;8.m[k]=b;9.s[k]=c;10.k++;11.}12.}13.}14.}米開朗基羅創(chuàng)作的西斯廷教堂穹頂畫《創(chuàng)世紀(jì)》西斯廷教堂案例二——生活中處處存在算法PARTITION(A，p，q)//A是一個實數(shù)數(shù)組,p,q是該數(shù)組的上下限{x←A[p]；//A[p]被選中

i←p；

forj←p+1toqdo

if(A[j]≤x)then{i←i+1；

A[i]A[j]；}//交換A[i]和A[j]的內(nèi)容

A[p]A[i]

returni}思考下面程序段最后一次比第一個數(shù)小的下標(biāo)并置換書上其他例子以及閱讀材料#include"stdio.h"voidmain(){inta[6],i,j,x,p=1,q=5,c,s;a[0]=0;a[1]=200;a[2]=100;a[3]=10;a[4]=30;a[5]=120;x=a[p];i=p;for(j=p+1;j<=q;j++) if(a[j]<=x) {i=i+1;c=a[i];a[i]=a[j];a[j]=c; }c=a[p];a[p]=a[i];a[i]=c;

printf("i=%d,a[p]=%d\n",i,a[p]);for(i=1;i<=q;i++)printf("%d,",a[i]);}2.1算法分析——時間復(fù)雜性基本概念算法分析：對算法所需要的兩種計算機(jī)資源——時間和空間進(jìn)行估算。問題規(guī)模：指輸入量的多少。運(yùn)行算法所需要的時間T是問題規(guī)模n的函數(shù)，記作T(n)?；菊Z句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的語句。算法是解決問題的方法，一個問題可以有很多解決方法，不同的算法之間就有了優(yōu)劣之分。如何對算法進(jìn)行比較？算法可以比較的方面很多，如易讀性、健壯性、可維護(hù)性、可擴(kuò)展性等，但這些都不是最關(guān)鍵的方面，算法的核心和靈魂是效率！也就是解決問題的速度。試想，一個需要運(yùn)行很多年才能給出正確結(jié)果的算法，就是其他方面的性能再好，也只是一個不實用的算法。算法的時間復(fù)雜性分析是一種事前分析估算的方法，是對算法所消耗資源的一種漸進(jìn)分析方法。漸進(jìn)分析是指忽略具體機(jī)器、編譯語言和編譯器的影響，只關(guān)注輸入規(guī)模增大時算法運(yùn)行時間的增長趨勢。——減低了分析難度2.1算法分析——時間復(fù)雜性問題規(guī)模：指輸入量的多少。運(yùn)行算法所需要的時間T是問題規(guī)模n的函數(shù)，記作T(n)。n在不同的問題中有不同的表現(xiàn)形式。例如：在數(shù)組中找值為c的元素，問題的規(guī)模是數(shù)組中元素的個數(shù)。遍歷一棵二叉樹，問題的規(guī)模是樹中的結(jié)點(diǎn)數(shù)?；菊Z句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的語句。

基本語句對算法運(yùn)行時間貢獻(xiàn)最大是算法中最重要的操作。定義：若存在兩個正的常數(shù)c和n0,對于任意n≥n0,都有T(n)≤cf(n),則稱T(n)=O(f(n))。大O符號描述增長率的上限，表示T(n)的增長最多像f(n)增長的那樣快，換言之，當(dāng)輸入規(guī)模為n時，算法消耗時間的最大值，這個上限的階越低，結(jié)果越有價值。該算法的運(yùn)行時間至多是O(f(n))。1）漸進(jìn)符號——運(yùn)行時間的上界漸進(jìn)分析例如：當(dāng)有T(n)

≤100n＋n取n0＝5，對任意n≥n0，有：T(n)

≤100n＋n=101n令c＝101，f(n)=n，有：T(n)

≤cn=cf(n)所以T(n)=O(f(n))

=O(n)練習(xí)：當(dāng)有T(n)

≤19/15n2+161/15n+28則T(n)=O(？)1）漸進(jìn)符號——運(yùn)行時間的上界1）漸進(jìn)符號——運(yùn)行時間的上界例：對函數(shù)f(n)=8n+128。問題是能否把它表示成O(n2)。顯然，對所有n≥0的整數(shù)，f(n)非負(fù)。根據(jù)定義，需找到整數(shù)n0和正常數(shù)c，使得n≥n0時，f(n)≤cn2。設(shè)c=1，常數(shù)c的大小無關(guān)緊要，但一定要存在因為f(n)≤cn2，所以8n+128≤cn2

0≤n2-8n-128

0≤(n-16)(n+8)當(dāng)n≥0時，(n+8)≥0；所以有(n-16)≥0故n0=16。結(jié)論：存在c=1,n0=16，對一切n≥n0的整數(shù)有f(n)≤cn2。所以f(n)=O(n2)。也就是說，對n≥16的整數(shù)總有n2≥8n+128。對不同的c，會有不同的n0，但結(jié)論是成立的。例：試說明函數(shù)f(n)=3n,不是O(2n)。根據(jù)定義，需找到整數(shù)n0和正常數(shù)c，使得n≥n0時，3n≤c2n。則c≥（3n/2n

）即c≥(3/2)n隨著n→∞，(3/2)n→∞，(3/2)n

就會大于指定的c。因此c值不存在，函數(shù)f(n)=3n不能表達(dá)O(2n)。大O表示法中的誤區(qū)誤區(qū)1：如果f1(n)=O(g(n))與f2(n)=O(g(n))，則f1(n)=f2(n)。誤區(qū)2：如果f(n)=O(g(n))，那么g(n)=O-1(f(n))。f1(n)=n=O(n);f2(n)=8n+128=O(n)但f1(n)≠f2(n)。g(n)與f(n)是數(shù)量級的關(guān)系，不是數(shù)學(xué)上的可逆關(guān)系。f(n)=8n+128=O(n),而g(n)=O-1(f(n))是錯誤的。1）漸進(jìn)符號——運(yùn)行時間的上界常用的大O表達(dá)式名稱表達(dá)式常數(shù)

(1)對數(shù)

(log2n)對數(shù)的平方

(log22n)線性

(n)n倍對數(shù)

(nlog2n)平方

(n2)三次方

(n3)冪

(2n)階乘

(n！)形如的常用求和公式的大：11一月2023多項式階有:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)O(2n)<O(n!)<O(nn)指數(shù)階有:

對于問題輸入長度n取不同值，各種不同的時間復(fù)雜性函數(shù)的算法，在機(jī)器上的運(yùn)行所需時間如下所示：nlognnlognn2n32n100112212484428166416832464512256164642564096655363251601024327684294967296當(dāng)n很大時，運(yùn)行一個比O(nlogn)復(fù)雜性大的算法是很困難的。降低算法復(fù)雜性，而不能只提高計算機(jī)的速度！對規(guī)模較小的問題,決定算法工作效率的可能是算法的簡單性而不是算法執(zhí)行的時間.當(dāng)比較兩個算法的效率時,若兩個算法是同階的,必須進(jìn)一步考察階的常數(shù)因子才能辨別優(yōu)劣.

時間函數(shù)的增長率常數(shù)因子的影響：

T1（n）=1000n；

T2（n）=100nlog2n；

T3（n）=10n2；

T4（n）=n3；

T5（n）=2n；則當(dāng):2≤n≤9時，A5比A1、A2、A3、A4都好；

10≤n≤58時，A3比A1、A2、A4、A5都好；

59≤n≤1024時，A2比其它算法都好；

n>1024時，算法A1最好。定義若存在兩個正的常數(shù)c和n0,對于任意n≥n0,都有T(n)≥cg(n),則稱T(n)=Ω(g(n))。大Ω符號用來描述增長率的下限，也就是說，當(dāng)輸入規(guī)模為n時，算法消耗時間的最小值。與大Ｏ符號對稱，這個下限的階越高，結(jié)果就越有價值。該算法的運(yùn)行時間至少是Ω(g(n))。2）漸進(jìn)符號——運(yùn)行時間的下界例如：當(dāng)有T(n)≥

n2＋n≥n2取n0＝1，任意n≥n0，存在常數(shù)c=1，f(n)=n2，使得：T(n)

≥n2=cf(n)所以,T(n)=Ω(g(n))練習(xí)：當(dāng)有T(n)

≥19/15n2+161/15n+28則T(n)=Ω(？)2）漸進(jìn)符號——運(yùn)行時間的下界Θ符號(運(yùn)行時間的準(zhǔn)確界)定義1.3若存在三個正的常數(shù)c1、c2和n0，對于任意n≥n0，都有c1f(n)≥T(n)≥c2×f(n)，則稱T(n)=Θ(f(n))。Θ符號意味著T(n)與f(n)同階，用來表示算法的精確階。3）漸進(jìn)符號——運(yùn)行時間的準(zhǔn)確界例1.1T(n)＝3n-1【解答】當(dāng)n≥1時，3n-1≤3n＝O(n)當(dāng)n≥1時，3n-1≥3n-n＝2n＝Ω(n)當(dāng)n≥1時，3n≥3n-1≥2n，則3n-1＝Θ(n)例1.2T(n)＝5n2＋8n＋1【解答】當(dāng)n≥1時，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2)當(dāng)n≥1時，5n2＋8n＋1≥5n2＝Ω(n2)當(dāng)n≥1時，14n2≥5n2＋8n＋1≥5n2，則5n2＋8n＋1＝Θ(n2)3）漸進(jìn)符號——運(yùn)行時間的準(zhǔn)確界練習(xí)：1.T(n)=40962.T(n)=5n+23.T(n)=8n2+3n+24.T(n)=5×2n+n25.T(n)=logn2練習(xí)：1.T(n)=40962.T(n)=5n+23.T(n)=8n2+3n+24.T(n)=5×2n+n25.T(n)=logn2定理2.1

若T(n)=amnm+am-1nm-1+…+a1n+a0（am>0），則有T(n)=O(nm)，且T(n)=Ω(nm)，因此，有T(n)=Θ(nm)。4）算法時間復(fù)雜度分析——定理證明：

取n0=1,當(dāng)n≥n0時，利用A(n)的定義和一個簡單不等式，有

|A(n)|≤|am|nm+|am-1|nm-1+…+|a2|n2+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a1|/nm-1+|a0|/nm)nm≤(|am|+|am-1|+…+|a2|+|a1|+|a0|)nm選取c=(|am|+|am-1|+…+|a2|+|a1|+|a0|),定理即得證。事實上，將n0取得足夠大，可以證明只要是c比|am|大的任意一個常數(shù)，此定理都成立。結(jié)論：對多項式函數(shù)的復(fù)雜性，與多項式的最高階nm同階，即A(n)=O(nm)。5）最好、最壞和平均情況最好情況：不能作為算法性能的代表，因為發(fā)生概率太小。最壞情況：好處是可以知道算法的運(yùn)行時間最還能壞到什么程度。平均情況：根據(jù)不同輸入下，算法平均運(yùn)行時間。要先對不同輸入發(fā)生的概率，給于估算。6）非遞歸算法的分析

1.建立一個代表算法運(yùn)行時間的求和表達(dá)式;2.用漸進(jìn)符號表示這個求和表達(dá)式。intArrayMin(inta[],intn){

min=a[0];

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

if(a[i]<min)min=a[i];

returnmin;}算法有遞歸和非遞歸之分1.決定用哪個（或哪些）參數(shù)作為算法問題規(guī)模的度量可以從問題的描述中得到。2.找出算法中的基本語句通常是最內(nèi)層循環(huán)的循環(huán)體。3.檢查基本語句的執(zhí)行次數(shù)是否只依賴于問題規(guī)模如果基本語句的執(zhí)行次數(shù)還依賴于其他一些特性，則需要分別研究最好情況、最壞情況和平均情況的效率。4.建立基本語句執(zhí)行次數(shù)的求和表達(dá)式計算基本語句執(zhí)行的次數(shù)，建立一個代表算法運(yùn)行時間的求和表達(dá)式。5.用漸進(jìn)符號表示這個求和