算法設(shè)計(jì)與分析-1-15

計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版）電子工業(yè)出版社教材資料、課程情況計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版），王曉東編著，北京：電子工業(yè)出版社，2012——優(yōu)缺點(diǎn)IntrodocutiontoAlgotithms(2ndEd),Cormen,T.H,Leiserson,C.E.,Rivest,R.,Stein,C.北京：高等教育出版社，2002必修課，11/12/13/14年，增強(qiáng)解決問(wèn)題能力；

ACM程序設(shè)計(jì)競(jìng)賽，bupt；研究生復(fù)試；大公司應(yīng)聘筆試中國(guó)計(jì)算機(jī)學(xué)會(huì)(CCF)主辦的CCF計(jì)算機(jī)軟件能力認(rèn)證(CCFCSP

)

CertifiedSoftwareProfessional（CSP）目標(biāo)：重點(diǎn)考察軟件開(kāi)發(fā)者的實(shí)際編程能力，向企業(yè)和高校推薦合格的軟件人才發(fā)起單位：

1）華為、百度、阿里巴巴、騰訊、360、微軟、金山、金蝶、英特爾等9家知名IT企業(yè)

2）清華大學(xué)、北京航空航天大學(xué)、北京大學(xué)、上海交通大學(xué)、西安交通大學(xué)、哈爾濱工業(yè)大學(xué)、中國(guó)人民大學(xué)、天津大學(xué)、國(guó)防科技大學(xué)、華中科技大學(xué)、中山大學(xué)、山東大學(xué)、電子科技大學(xué)等13所著名高校清華大學(xué)等一批高校計(jì)算機(jī)專業(yè)將以該認(rèn)證考試取代研究生復(fù)試的上機(jī)考試。凡持有CCF軟件能力認(rèn)證成績(jī)單并達(dá)到一定水準(zhǔn)者可免于機(jī)考，直接進(jìn)入面試環(huán)節(jié)CCF計(jì)劃將認(rèn)證推廣到全國(guó)的高校和企業(yè)CCFCSP創(chuàng)立以來(lái)的第四次認(rèn)證于2015年3月29日舉行（3、9、12月）(CCFCSP)

認(rèn)證內(nèi)容：覆蓋大學(xué)計(jì)算機(jī)專業(yè)所學(xué)程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法，以及相關(guān)數(shù)學(xué)基礎(chǔ)知識(shí)。編程語(yǔ)言：C/C++或Java。

認(rèn)證方式：

1.采用上機(jī)編程方式，編制的程序在限定的時(shí)間、空間內(nèi)通過(guò)給定的數(shù)據(jù)測(cè)試后獲得相應(yīng)分?jǐn)?shù)。

2.卷面5道題，每題滿分100分，總分500分。

3.從第一題至第五題，難度依次遞進(jìn)，考試時(shí)間為4小時(shí)成績(jī)效力

認(rèn)證成績(jī)公布后，CCFCSP認(rèn)證中心會(huì)把被認(rèn)證者的成績(jī)發(fā)送給簽約企業(yè)和高校，企業(yè)和高校會(huì)根據(jù)需要與被認(rèn)證者聯(lián)系。認(rèn)證知識(shí)要求

程序設(shè)計(jì)基礎(chǔ)

邏輯與數(shù)學(xué)運(yùn)算，分支循環(huán)，過(guò)程調(diào)用(遞歸)，字符串操作，文件操作等數(shù)據(jù)結(jié)構(gòu)

線性表（數(shù)組、隊(duì)列、棧、鏈表）、樹（堆、排序二叉樹）、哈希表、集合與映射、圖算法與算法設(shè)計(jì)策略

排序與查找，枚舉，貪心策略，分治策略，遞推與遞歸，動(dòng)態(tài)規(guī)劃，搜索；圖論算法，計(jì)算幾何，字符串算法、線段樹；隨機(jī)算法，近似算法等CSP例題

注意事項(xiàng)成績(jī)期中，期末，作業(yè)；掌握：1.各章主要算法策略——5種策略

2.算法設(shè)計(jì)策略應(yīng)用于具體問(wèn)題

典型問(wèn)題算法

3.各章典型問(wèn)題/算法設(shè)計(jì)+分析作業(yè)：各章典型問(wèn)題/算法的編程實(shí)現(xiàn)（每章3個(gè)）答疑、作業(yè)：助教課堂紀(jì)律第1章算法概述學(xué)習(xí)要點(diǎn):理解算法的概念理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系算法設(shè)計(jì)：算法業(yè)務(wù)邏輯、解題流程算法分析：性能（速度、快慢）、資源占用掌握算法的計(jì)算復(fù)雜性概念掌握算法漸近復(fù)雜性的數(shù)學(xué)表述掌握用C++語(yǔ)言描述算法的方法算法(Algorithm)算法是指解決特定問(wèn)題的一種方法或一個(gè)過(guò)程。——從計(jì)算機(jī)角度，形式化、半形式化描述算法是若干指令、程序語(yǔ)句的有窮序列，滿足性質(zhì)：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。(3)確定性：組成算法的每條指令、語(yǔ)句是清晰，無(wú)歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。程序(Program)程序：算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。進(jìn)程（process，“操作系統(tǒng)”課程）：程序的一次執(zhí)行

e.g.Windows任務(wù)管理器程序=數(shù)據(jù)結(jié)構(gòu)+算法（1）處理對(duì)象，輸入、輸出、中間結(jié)果、….

（2）處理過(guò)程程序(Program)程序可以不滿足算法的性質(zhì)(4)——有限性。例如，操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，某些語(yǔ)句、模塊反復(fù)執(zhí)行，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。問(wèn)題求解(ProblemSolving)

e.g.旅行最短路徑問(wèn)題（TSP）證明正確性算法性能分析設(shè)計(jì)實(shí)現(xiàn)程序理解問(wèn)題—問(wèn)題抽象描述選擇數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法策略（回溯、分支限界、..）設(shè)計(jì)算法編譯-鏈接裝載執(zhí)行進(jìn)程結(jié)果操作系統(tǒng)編譯程序程序設(shè)計(jì)、軟件工程算法設(shè)計(jì)與分析算法策略分治算法動(dòng)態(tài)規(guī)劃貪心法回溯搜索分支限界法….，e.g.on-line算法，概率算法算法復(fù)雜性分析

算法分析對(duì)象：（1）性能：算法/程序執(zhí)行的快慢，對(duì)CPU資源的占用（2）資源占用：內(nèi)存資源、I/O資源占用；e.g.Windows任務(wù)管理器算法復(fù)雜性：?jiǎn)栴}規(guī)模n

，表示輸入大小，（1）時(shí)間復(fù)雜性T(n)，算法性能的定量描述（2）空間復(fù)雜性S(n)，算法所需計(jì)算機(jī)資源的定量描述更準(zhǔn)確地，時(shí)空復(fù)雜性依賴于問(wèn)題的規(guī)模n、算法的輸入I，有：

T=T(n,I)S=S(n,I)問(wèn)題規(guī)模n、問(wèn)題輸入I有可能是多維的，e.g.對(duì)圖上最短路徑問(wèn)題，問(wèn)題規(guī)模n：圖的頂點(diǎn)數(shù)目、邊數(shù)目，輸入I：起始點(diǎn)，目標(biāo)點(diǎn)圖中任意兩點(diǎn)最短路徑圖G(V,E)子圖G1(V1,E1)ab|V|=100,|E|=1000|V1|=40,|E|=400圖中任意兩點(diǎn)最短路徑對(duì)圖G(V,E)，其復(fù)雜性為T(C1002,|V|=100,|E|=1000)對(duì)子圖G1(V1,E1)，其復(fù)雜性為T(C402,|V1|=40,|E1|=400)對(duì)相同的輸入I=(a,b)，針對(duì)G和G1的計(jì)算結(jié)果、復(fù)雜性有可能不同·算法的時(shí)間復(fù)雜性（1）最壞情況下的時(shí)間復(fù)雜性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間復(fù)雜性

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時(shí)間復(fù)雜性

Tavg(n)=

，其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。算法漸近復(fù)雜性衡量算法復(fù)雜性的檔次/規(guī)?！A，

Rate/Orderofgrowth對(duì)時(shí)間復(fù)雜性函數(shù)T(n)，有可能，T(n)

,asn

;例如，

T(n)=2n2+4n+1，t(n)=2n2(T(n)-t(n))/T(n)0

，asn;,t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。漸近分析的記號(hào)在下面的討論中，對(duì)所有n，f(n)

0，g(n)

0，（即f(n)和g(n)是定義在正數(shù)集上的正函數(shù)），考察f(n)各種漸近界（1）漸近上界記號(hào)OO(g(n))={f(n)|存在正常數(shù)c和n0，使得對(duì)所有n

n0有：0

f(n)

cg(n)}或者稱為：函數(shù)f(n)當(dāng)n充分大時(shí)上有界，且g(n)是它的一個(gè)上界，記為f(n)=O(g(n))，即f(n)的階不高于g(n)的階——f上升規(guī)模/檔次不快于于g

。E.g.1f(n)=5n2+1,g(n)=2n2g(n)f(n)n0c=1平行E.g.2漸近分析的記號(hào)（2）漸近下界記號(hào)

(g(n))={f(n)|存在正常數(shù)c和n0，使得對(duì)所有n

n0有：0

cg(n)

f(n)}或者稱為：函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個(gè)下界，記為f(n)=

(g(n))，即f(n)的階不低于g(n)的階——f上升不慢于g。E.g.3f(n)=5n2+1，g(n)=10n1.5，取n0=4，c=1g(n)f(n)n0c=1平行E.g.4（3）非緊上界記號(hào)o

o(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)n0>0使得對(duì)所有n

n0有：0

f(n)<cg(n)}等價(jià)于

f(n)/g(n)0

，asn

。或者稱為：當(dāng)n充分大時(shí)，函數(shù)f(n)的階比g(n)低——上升更慢，記為f(n)=o(g(n))。例如，4nlogn+7=o(2n2+3nlogn+3),

，取n0=3，c=2g(n)f(n)n0c=1非平行（4）非緊下界記號(hào)

(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)n0>0使得對(duì)所有n

n0有：0

cg(n)

<

f(n)}等價(jià)于

f(n)/g(n)

，asn

?；蛘叻Q：當(dāng)n充分大時(shí)，函數(shù)f(n)的階比g(n)高，記為f(n)=

(g(n))。例如，3n2+4nlogn+7=

(4nlogn+12)。，取n0=3，c=1f(n)

(g(n))

g(n)

o(f(n))

（非緊上界與非緊下界互為對(duì)偶）g(n)f(n)n0c=1非平行（5）緊漸近界記號(hào)

(g(n))={f(n)|存在正常數(shù)c1,c2和n0，使得對(duì)所有n

n0有：c1g(n)

f(n)

c2g(n)}或者稱：f(n)與g(n)同階。例如,3n2+4nlogn+7=

(n2)

，取n0=3，c1=3，c2=6定理1：

(g(n))=O(g(n))

(g(n))g(n)f(n)n0c1g(n)c2g(n)漸近分析記號(hào)在等式和不等式中的意義f(n)=

(g(n))的確切意義是：f(n)

(g(n))。一般情況下，等式和不等式中的漸近記號(hào)

(g(n))表示

(g(n))中的某個(gè)函數(shù)。例如：2n2+3n+1=2n2+

(n)表示

2n2+3n+1=2n2+f(n)，其中f(n)是

(n)中某個(gè)函數(shù)。等式和不等式中漸近記號(hào)O,o,

和

的意義是類似的。漸近分析中函數(shù)比較f(n)=O(g(n))

ab;漸近上界f(n)=

(g(n))

ab;漸近下界

f(n)=

(g(n))

a=b;緊漸近界f(n)=o(g(n))

a<b;非緊上界f(n)=

(g(n))

a>b.非緊下界

漸近分析記號(hào)的若干性質(zhì)（1）傳遞性：f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=o(g(n))，g(n)=o(h(n))

f(n)=o(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；（2）反身性/自反性：f(n)=

(f(n))；f(n)=O(f(n))；f(n)=

(f(n)).（3）對(duì)稱性：f(n)=

(g(n))

g(n)=

(f(n)).（4）互對(duì)稱性：f(n)=O(g(n))

g(n)=

(f(n))；f(n)=o(g(n))

g(n)=

(f(n))；（5）算術(shù)運(yùn)算：O(f(n))+O(g(n))=

O(max{f(n),g(n)})

；證明見(jiàn)下頁(yè)O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；g(n)=O(f(n))

O(f(n))+O(g(n))=

O(f(n))。規(guī)則O(f(n))+O(g(n))=

O(max{f(n),g(n)})的證明：對(duì)于任意f1(n)

O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n

n1，有f1(n)

c1f(n)。類似地，對(duì)于任意g1(n)

O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n

n2，有g(shù)1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的n

n3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

c32*max{f(n),g(n)}=2c3*h(n)=O(max{f(n),g(n)}).算法漸近復(fù)雜性分析中常用函數(shù)（1）單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)

f(n);單調(diào)遞減：m

n

f(m)

f(n);嚴(yán)格單調(diào)遞增：m

<n

f(m)<f(n);嚴(yán)格單調(diào)遞減：m

<n

f(m)>f(n).（2）取整函數(shù)

x

：不大于x的最大整數(shù)；

x

：不小于x的最小整數(shù)。取整函數(shù)的若干性質(zhì)

x-1<x

x

x<x+1，e.g.x=7.5；

n/2

+n/2=n;e.g.n=5

對(duì)于n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;

f(x)=x,g(x)=x

為單調(diào)遞增函數(shù)。（3）多項(xiàng)式函數(shù)

p(n)=a0+a1n+a2n2+…+adnd；ad>0;

p(n)=

(nd);

f(n)=O(nk)

f(n)多項(xiàng)式有界；

f(n)=O(1)

f(n)

c;

k

d

p(n)=O(nk);k

d

p(n)=

(nk);k>

d

p(n)=o(nk);k<d

p(n)=

(nk).（4）指數(shù)函數(shù)對(duì)于正整數(shù)m,n和實(shí)數(shù)a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1

an為單調(diào)遞增函數(shù);a>1

nb=o(an)（枚舉、窮搜型算法）ex

1+x;|x|11+x

ex

1+x+x2;

ex

=1+x+(x2),asx0,e.g.(x2)=x2;（5）對(duì)數(shù)函數(shù)

logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)k;loglogn=log(logn);fora>0,b>0,c>0|x|1forx>-1,foranya>0,,logbn=o(na)（6）階層函數(shù)Stirling’sapproximation

算法分析中常見(jiàn)的復(fù)雜性函數(shù)算法分析中常見(jiàn)的復(fù)雜性函數(shù)小規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)問(wèn)題規(guī)模vs算法復(fù)雜性

數(shù)學(xué)模型階次vs輸入擾動(dòng)當(dāng)算法復(fù)雜度的階次比較大時(shí)，如T(n)=nk,k>4,問(wèn)題規(guī)模的微小增加，導(dǎo)致算法復(fù)雜性急劇增大數(shù)學(xué)建模時(shí)，如果對(duì)象的數(shù)學(xué)模型為高階模型，微小的輸入擾動(dòng)引起輸出的劇烈波動(dòng)實(shí)際應(yīng)用中，如果1個(gè)算法的時(shí)間復(fù)雜性T(n)不滿足T(n)=O(nk),k比較小，如k≤4，則該算法當(dāng)問(wèn)題規(guī)模n較大時(shí)，計(jì)算時(shí)間急劇增加、過(guò)大，很可能無(wú)法在合理的時(shí)間內(nèi)得到正確解好的算法要同時(shí)保證功能和性能?。?/p>

—功能：輸出結(jié)果是正確的

—性能：使用有限的計(jì)算資源，如cpu、內(nèi)存，在可接受的時(shí)間內(nèi)輸出結(jié)果例1.問(wèn)題規(guī)模vs算法復(fù)雜性

RunningTimesAssumeN=100,000andprocessorspeedis1,000,000,000operationspersecondFunctionRunningTime2N3.2x1030086yearsN43171yearsN311.6daysN210secondsNN0.032secondsNlogN0.0017secondsN0.0001secondsN3.2x10-7secondslogN1.2x10-8seconds

例2.漢諾(Hanoi)塔印度教有一個(gè)古老的傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言：當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

這個(gè)難題的主要目的在于把一個(gè)柱子上的碟子全部移到另外一個(gè)柱子上去，必須遵守以下規(guī)則:

1.每次只能移動(dòng)一個(gè)盤子；

2.每次只能把一個(gè)柱子上的最上面的一個(gè)盤子放到另外一個(gè)柱子上去，那個(gè)柱子上可能已經(jīng)放有盤子。

3.大盤在下，小盤在上。遞歸解法(Recursivesolution，見(jiàn)第2章)

hanoi(#disk,source,buffer,target):hanoi(n,left,middle,right);=>/*將位于左柱的n片，借助中柱，移植右柱hanoi(n-1,left,right,middle);/*將最高的n-1片，借助右柱，移至中柱move(1,left,_,right);/*最底層的第n片，直接移至右柱hanoi(n-1,middle,left,right);/*右柱的n-1片，借助左柱，移至右柱n-1這需要多少次移動(dòng)呢?

假設(shè)有n片，移動(dòng)次數(shù)是f(n).

顯然f(1)=1,f(2)=3,f(3)=7,

且f(k+1)=f(k)+1+f(k)=2*f(k)+1此后不難證明：

f(n)=2n-1n=64時(shí)，

f(64)=264-1=18446744073709551615

≈1.84×1019f(64)=264-1=18446744073709551615≈1.84×1019假如每秒鐘移動(dòng)一次，共需多長(zhǎng)時(shí)間呢？一個(gè)平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952(≈3.16×107)秒，搬動(dòng)64片所需時(shí)間：

18446744073709551615/31556952=584554049253.855年

≈

(1.84×1019)÷(3.16×107)

≈

5.8×1011

年

=5.8×103×108

年=5800億年這表明移完這些金片需要5845億年以上。宇宙大約已存在140億年。壽命據(jù)說(shuō)為2萬(wàn)億年；地球存在至今不過(guò)45億年，太陽(yáng)系的預(yù)期壽命據(jù)說(shuō)也就是數(shù)百億年。真的過(guò)了5845億年，不說(shuō)太陽(yáng)系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅

地老天荒！編寫計(jì)算機(jī)程序，模擬移動(dòng)64個(gè)盤片，程序所需時(shí)間？移動(dòng)的總次數(shù)

f(64)=264-1=18446744073709551615≈1.84×1019假設(shè)：移動(dòng)1次需要執(zhí)行m條機(jī)器指令，e.g.m=10以單核微機(jī)為計(jì)算平臺(tái)，主頻為F,e.g.F=3GHz=3×109次/每秒

1個(gè)機(jī)器指令周期時(shí)長(zhǎng)t

=1/F=(1/3)*10-9

秒假設(shè)1條指令平均需要s個(gè)周期,e.g.s=2,則1條指令的執(zhí)行時(shí)間為s*t,e.g.s*t=(2/3)*10-9

秒模擬程序執(zhí)行時(shí)間：

f(64)*m*(s*t)≈1.84×1019×10×(2/3)*10-9

秒

≈

1.2×1011

秒≈（1.2×1011

）/(3.16×107)年

≈3.8×103

年=3800年利用高性能并行計(jì)算機(jī)系統(tǒng)/超級(jí)計(jì)算機(jī)前提：如果能采用合適的并行算法，e.g.第2章遞歸-分治策略（——實(shí)際上不能?。?！)北郵曙光天潮4000L集群系統(tǒng)

40個(gè)計(jì)算節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)IntelXeon（EM64T）3.2G*2(雙核/CPU)，每個(gè)節(jié)點(diǎn)2個(gè)計(jì)算核；峰值運(yùn)算速度：5240億次/秒；

￥80萬(wàn)；

漢諾塔問(wèn)題計(jì)算時(shí)間：≈2.2年(?!)目前(截止2013年11月18日)，全世界最快的超級(jí)計(jì)算機(jī)“天河二號(hào)”

32,000顆XeonE5主處理器，48,000個(gè)XeonPhi協(xié)處理器，每個(gè)XeonPhi有61個(gè)核心，使用其中的57個(gè)核心。共312萬(wàn)個(gè)計(jì)算核心；

170個(gè)機(jī)柜組成;

峰值運(yùn)算速度：5.49億億次/秒；研發(fā)耗資1億美元，￥10多億？，入住廣州超級(jí)計(jì)算中心;

漢諾塔問(wèn)題計(jì)算時(shí)間：≈

12分鐘(?!)用c++描述算法（1）選擇語(yǔ)句：（1.1)if語(yǔ)句：（1.2)？語(yǔ)句：

if(expression)statement;elsestatement;exp1?exp2:exp3y=x>9?100:200;等價(jià)于：

if(x>9)y=100;elsey=200;（1.3)switch語(yǔ)句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}（2）迭代語(yǔ)句：（2.1)for循環(huán)：

for(init;condition;inc)statement;（2.2)while循環(huán)：

while(condition)statement;（2.3)do-while循環(huán)：

do{statement;}while(condition);（3）跳轉(zhuǎn)語(yǔ)句：（3.1)return語(yǔ)句：

returnexpression;（3.2)goto語(yǔ)句：

gotolabel;

label:（4）函數(shù)：例：

return-typefunctionname(para-list){bodyofthefunction}intmax(intx,inty){returnx>y?x:y;}（5）模板template

：template<classType>Typemax(Typex,Typey){returnx>y?x:y;}inti=max(1,2)；doublex=max(1.0,2.0)；（6）動(dòng)態(tài)存儲(chǔ)分配：（6.1）運(yùn)算符new：運(yùn)算符new用于動(dòng)態(tài)存儲(chǔ)分配。new返回一個(gè)指向所分配空間的指針。例：int

x；y=newint；

y=10；也可將上述各語(yǔ)句作適當(dāng)合并如下：int

y=newint；

y=10；或int

y=newint(10)；或int

y；y=newint(10)；（6.2）一維數(shù)組：為了在運(yùn)行時(shí)創(chuàng)建一個(gè)大小可動(dòng)態(tài)變化的一維浮點(diǎn)數(shù)組x，可先將x聲明為一個(gè)float類型的指針。然后用new為數(shù)組動(dòng)態(tài)地分配存儲(chǔ)空間。例：

float

x=newfloat[n]；創(chuàng)建一個(gè)大小為n的一維浮點(diǎn)數(shù)組。運(yùn)算符new分配n個(gè)浮點(diǎn)數(shù)所需的空間，并返回指向第一個(gè)浮點(diǎn)數(shù)的指針。然后可用x[0]，x[1]，…，x[n-1]來(lái)訪問(wèn)每個(gè)數(shù)組元素。（6.3）運(yùn)算符delete：當(dāng)動(dòng)態(tài)分配的存儲(chǔ)空間已不再需要時(shí)應(yīng)及時(shí)釋放所占用的空間。用運(yùn)算符delete來(lái)釋放由new分配的空間。例：deletey；delete[]x；分別釋放分配給

y的空間和分配給一維數(shù)組x的空間。（6.4）動(dòng)態(tài)二維數(shù)組：創(chuàng)建類型為Type的動(dòng)態(tài)工作數(shù)組，這個(gè)數(shù)組有rows行和cols列。template<classType>voidMake2DArray(Type**&x,introws,intcols){x=newType*[rows];for(inti=0;i<rows;i++)x[i]=newType[cols];}當(dāng)不再需要一個(gè)動(dòng)態(tài)分配的二維數(shù)組時(shí)，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所分配的空間。然后釋放為行指針?lè)峙涞目臻g。釋放空間后將x置為0，以防繼續(xù)訪問(wèn)已被釋放的空間。template<classType>void

Delete2DArray(Type**&x,introws){for(inti=0;i<rows;i++)delete[]x[i];delete[]x;x=0;}算法分析方法例：順序搜索算法template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-1;}14689357a:n=8,（1）Tmax(n)=max{T(I)|size(I)=n}=O(n),k=7（2）Tmin(n)=min{T(I)|size(I)=1

}=O(1),k=1（3）在平均情況下，假設(shè)：

(a)搜索成功（即k在數(shù)組內(nèi)）的概率為p(0

p

1)；

(b)在數(shù)組的每個(gè)位置i(0

i<n)搜索成功的概率相同，均為p/n。算法時(shí)間復(fù)雜性分析的基本法則非遞歸算法：（1）for/while循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)；（3）順序語(yǔ)句各語(yǔ)句計(jì)算時(shí)間相加；（4）if-else語(yǔ)句if語(yǔ)句計(jì)算時(shí)間和else語(yǔ)句計(jì)算時(shí)間的較大者。template<classType>voidinsertion_sort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumof(ti-1) }a[j+1]=key;//c7n-1

}}524613a:ijkey=2,a[j]=5在最好情況下（已經(jīng)排好序），ti=1,for1

i<n;在最壞情況下（完全未排好），ti

i+1,for1

i<n;對(duì)于輸入數(shù)據(jù)a[i]=n-i,i=0,1,…,n-1，算法insertion_sort達(dá)到其最壞情形。因此，????由此可見(jiàn)，Tmax(n)=

(n2)問(wèn)題書上說(shuō)排序算法復(fù)雜度的下界是nlogn,求最接近點(diǎn)對(duì)復(fù)雜度的下界是nlogn，這些下界是如何分析得到的呢？如何證明不可能找到比這些復(fù)雜度更小的算法呢？——復(fù)雜度下界是由問(wèn)題本身性質(zhì)決定的！?。∵f歸算法的空間復(fù)雜度一般是怎么求的呢？比如問(wèn)題規(guī)模為n的二分查找和求斐波那契數(shù)列的第n項(xiàng)這兩個(gè)問(wèn)題的空間復(fù)雜度是多少呢？分別是如何分析得到的？空間復(fù)雜性S(n)的含義S(n)

算法中的指令運(yùn)行時(shí)占用的存儲(chǔ)空間（一般指內(nèi)存空間），或：算法所對(duì)應(yīng)的程序運(yùn)行時(shí)占用的存儲(chǔ)空間算法/程序運(yùn)行時(shí)占用的存儲(chǔ)空間

1.算法/程序在外設(shè)磁盤上所占存儲(chǔ)空間——靜態(tài)、有限

a.目標(biāo)文件(.o文件，目標(biāo)代碼、機(jī)器指令)所占存儲(chǔ)空間每條指令所占空間總和

b.所處理的輸入/輸出數(shù)據(jù)所占存儲(chǔ)空間算法/程序運(yùn)行時(shí)占用的存儲(chǔ)空間（續(xù)）

2.算法/程序在內(nèi)存中運(yùn)行時(shí)，所占存儲(chǔ)空間——可以是動(dòng)態(tài)變化的

所占存儲(chǔ)空間包括（參見(jiàn)編譯原理、操作系統(tǒng)）：

a.load進(jìn)內(nèi)存的算法/程序的機(jī)器指令集合所占內(nèi)存空間

—固定有限

b.輸入/輸出數(shù)據(jù)所占內(nèi)存空間

—但對(duì)每種輸入，所占空間是固定的；對(duì)不同的輸入，所占空間有可能不同

c.算法/程序操作的各類數(shù)據(jù)對(duì)象——變量所占空間，如過(guò)程參數(shù)

—可能隨著算法業(yè)務(wù)邏輯、執(zhí)行軌跡的不同，占用的內(nèi)存空間可能會(huì)發(fā)生變化

d.描述算法/程序運(yùn)行狀態(tài)的信息，如程序計(jì)數(shù)器指針

e.g.intx、動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)內(nèi)存泄露Fig.3.1ProcessinMemoryOctober2012OperatingSystemConcepts-Chapter3Processes-83ProcessConcept(cont.)

參見(jiàn)“操作系統(tǒng)”Aprocessincludesprogramcode(ortextsection)datasection(containingglobalvariables)currentactivity,asrepresentedbythevalueofprogramcounterandthecontentsoftheprocessor’sregisters,calledprocesscontextstack(fortemporarydata,e.g.functionparameters,returnaddresses,localvariables)heapProcess=program+data

+PCB計(jì)算機(jī)操作系統(tǒng)如何為算法/程序分配外設(shè)磁盤存儲(chǔ)空間根據(jù)算法/程序的目標(biāo)文件、輸入/輸數(shù)據(jù)文件大小，以磁盤塊block大小為單位（e.g.4k），分配外設(shè)存儲(chǔ)空間示例——觀察Windows操作系統(tǒng)下的txt文件

1.創(chuàng)建空的txt文件，觀察文件屬性信息2.在空文件中加入8個(gè)字符“abcdefgh”，觀察文件屬性信息txt文件存儲(chǔ)格式：4k：txt文件大?。?5k=4k*3+3K4k：abcdefgh計(jì)算機(jī)操作系統(tǒng)如何為算法/程序分配內(nèi)存空間將算法/程序的地址空間（執(zhí)行時(shí)可訪問(wèn)的全部?jī)?nèi)存地址范圍）劃分