算法設計與分析-1-15

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

ACM程序設計競賽，bupt；研究生復試；大公司應聘筆試中國計算機學會(CCF)主辦的CCF計算機軟件能力認證(CCFCSP

)

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

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

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

認證內容：覆蓋大學計算機專業(yè)所學程序設計、數(shù)據(jù)結構、算法，以及相關數(shù)學基礎知識。編程語言：C/C++或Java。

認證方式：

1.采用上機編程方式，編制的程序在限定的時間、空間內通過給定的數(shù)據(jù)測試后獲得相應分數(shù)。

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

3.從第一題至第五題，難度依次遞進，考試時間為4小時成績效力

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

程序設計基礎

邏輯與數(shù)學運算，分支循環(huán)，過程調用(遞歸)，字符串操作，文件操作等數(shù)據(jù)結構

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

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

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

2.算法設計策略應用于具體問題

典型問題算法

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

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

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

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

算法分析對象：（1）性能：算法/程序執(zhí)行的快慢，對CPU資源的占用（2）資源占用：內存資源、I/O資源占用；e.g.Windows任務管理器算法復雜性：問題規(guī)模n

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

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

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

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

Tavg(n)=

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

Rate/Orderofgrowth對時間復雜性函數(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)，為算法的漸近復雜性。在數(shù)學上，t(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)簡單。漸近分析的記號在下面的討論中，對所有n，f(n)

0，g(n)

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

n0有：0

f(n)

cg(n)}或者稱為：函數(shù)f(n)當n充分大時上有界，且g(n)是它的一個上界，記為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漸近分析的記號（2）漸近下界記號

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

n0有：0

cg(n)

f(n)}或者稱為：函數(shù)f(n)當n充分大時下有界，且g(n)是它的一個下界，記為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）非緊上界記號o

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

n0有：0

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

f(n)/g(n)0

，asn

?；蛘叻Q為：當n充分大時，函數(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）非緊下界記號

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

n0有：0

cg(n)

<

f(n)}等價于

f(n)/g(n)

，asn

?；蛘叻Q：當n充分大時，函數(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))

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

(g(n))={f(n)|存在正常數(shù)c1,c2和n0，使得對所有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)漸近分析記號在等式和不等式中的意義f(n)=

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

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

(g(n))表示

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

(n)表示

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

(n)中某個函數(shù)。等式和不等式中漸近記號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.非緊下界

漸近分析記號的若干性質（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）對稱性：f(n)=

(g(n))

g(n)=

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

g(n)=

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

g(n)=

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

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

；證明見下頁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)})的證明：對于任意f1(n)

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

n1，有f1(n)

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

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

n2，有g1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對所有的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)}).算法漸近復雜性分析中常用函數(shù)（1）單調函數(shù)單調遞增：m

n

f(m)

f(n);單調遞減：m

n

f(m)

f(n);嚴格單調遞增：m

<n

f(m)<f(n);嚴格單調遞減：m

<n

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

x

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

x

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

x-1<x

x

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

n/2

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

對于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

為單調遞增函數(shù)。（3）多項式函數(shù)

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

p(n)=

(nd);

f(n)=O(nk)

f(n)多項式有界；

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ù)對于正整數(shù)m,n和實數(shù)a>0:a0=1;

a1=a;

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

(am)n=(an)m;

aman=

am+n;

a>1

an為單調遞增函數(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）對數(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

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

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

—功能：輸出結果是正確的

—性能：使用有限的計算資源，如cpu、內存，在可接受的時間內輸出結果例1.問題規(guī)模vs算法復雜性

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

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

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

1.每次只能移動一個盤子；

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

3.大盤在下，小盤在上。遞歸解法(Recursivesolution，見第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這需要多少次移動呢?

假設有n片，移動次數(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時，

f(64)=264-1=18446744073709551615

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

18446744073709551615/31556952=584554049253.855年

≈

(1.84×1019)÷(3.16×107)

≈

5.8×1011

年

=5.8×103×108

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

地老天荒！編寫計算機程序，模擬移動64個盤片，程序所需時間？移動的總次數(shù)

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

1個機器指令周期時長t

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

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

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

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

40個計算節(jié)點，每個節(jié)點IntelXeon（EM64T）3.2G*2(雙核/CPU)，每個節(jié)點2個計算核；峰值運算速度：5240億次/秒；

￥80萬；

漢諾塔問題計算時間：≈2.2年(?!)目前(截止2013年11月18日)，全世界最快的超級計算機“天河二號”

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

170個機柜組成;

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

漢諾塔問題計算時間：≈

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

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

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

default:statementsequence;}（2）迭代語句：（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）跳轉語句：（3.1)return語句：

returnexpression;（3.2)goto語句：

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）動態(tài)存儲分配：（6.1）運算符new：運算符new用于動態(tài)存儲分配。new返回一個指向所分配空間的指針。例：int

x；y=newint；

y=10；也可將上述各語句作適當合并如下：int

y=newint；

y=10；或int

y=newint(10)；或int

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

float

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

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

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

p

1)；

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

i<n)搜索成功的概率相同，均為p/n。算法時間復雜性分析的基本法則非遞歸算法：（1）for/while循環(huán)循環(huán)體內計算時間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內計算時間*所有循環(huán)次數(shù)；（3）順序語句各語句計算時間相加；（4）if-else語句if語句計算時間和else語句計算時間的較大者。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在最好情況下（已經排好序），ti=1,for1

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

i+1,for1

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

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

算法中的指令運行時占用的存儲空間（一般指內存空間），或：算法所對應的程序運行時占用的存儲空間算法/程序運行時占用的存儲空間

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

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

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

2.算法/程序在內存中運行時，所占存儲空間——可以是動態(tài)變化的

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

a.load進內存的算法/程序的機器指令集合所占內存空間

—固定有限

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

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

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

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

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

e.g.intx、動態(tài)數(shù)據(jù)結構內存泄露Fig.3.1ProcessinMemoryOctober2012OperatingSystemConcepts-Chapter3Processes-83ProcessConcept(cont.)

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

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

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