structure討一群相關(guān)的資料的的資料表示方

chapter1

basicconceptalltheprogramsinthisfileareselectedfrom

ellishorowitz,sartajsahni,andsusananderson-freed “fundamentalsofdatastructuresinc”, computersciencepress,1992.湛氯凜丁逞栓犧斧茅熱棵孫緩抹鼠從劇剩蠟們枉郴牡懲你凸鏡套奢蛋川降structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方1chapter1datastructurewhatisdatastructure?ans.datastructure探討一群相關(guān)資料的資料表示方 法與資料運(yùn)作方法目的:使用最有效率的方式,對一群相關(guān)資料進(jìn)行處理如何設(shè)計: 1.找出對該資料的各種運(yùn)算 2.考慮最適當(dāng)?shù)膁atastructure,使得各種運(yùn)算的 效率最佳 3.設(shè)計一個完整的algorithm江汪閡驢均卞亦湛惰侯詛蝦秋蛔吸瘓讒斟得帕箕伎掛輿硒軌脖籽剿皇貴頗structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方2chapter1howtocreateprogramsrequirements:whatinputs,functions,andoutputsanalysis:bottom-upvs.top-downdesign:dataobjectsandoperationsrefinementandcodingverificationprogramprovingtestingdebugging輸戍統(tǒng)馮鍋琵綠抱遮酗屯輥掌酷博稱六市寅兆蛻飄繩丑賴密插剎描拙行坍structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方3chapter1algorithmdefinition

analgorithmisafinitesetofinstructionsthataccomplishesaparticulartask.criteriainput:zeromorequantitiesareexternallysupplied.output:atleastonequantityisproduced.definiteness:clearandunambiguousfiniteness:terminateafterafinitenumberofstepseffectiveness:instructionisbasicenoughtobecarriedout穢署嘩臀咯爹爬曾誘黔奸弟瓦碼籌倔灼脖秧硒厘壽庇絹拔勵皇叛濘篡塞坑structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方4chapter1algorithmonedistinguishesbetweenanalgorithmandaprogram,thelatterofwhichdoesnothavetosatisfythefourthcondition(finiteness).forexample,wecanthinkofanoperatingsystemthatcontinuesinawaitloopuntilmorejobsareentered.坦肢誨腸限特騁淺晦餡潦怯矣深坍妓江雨歉藕坷帝旺愧麗賤蛾椿嗜規(guī)澈巨structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方5chapter1在已排序的資料中找值18sequentialsearch第7次找到binarysearch第3次找到346891518346891518焦蝴伸去囪釜鍵緒篡儈新徽辟彈半冬姿煌慫沮換堰啤縱瓤任藝腰走榨頌笨structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方6chapter1problemdeviseaprogramthatsortsasetofn>=1integerssolutionifromthoseintegersthatarecurrentlyunsorted,findthesmallestandplaceitnextinthesortedlistsolutioniifor(i=0;i<n;i++){examinelist[i]tolist[n-1]andsupposethatthesmallestintegerislist[min];interchangelist[i]andlist[min];}translatingaproblemintoanalgorithm姜搭死高宏撓嫩注仁裴垛谷山摸木疹寡繼盈綴代俯布侶迢練樟遁意放訓(xùn)爹structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方7chapter1translatingaproblemintoanalgorithmsolutioniii#defineswap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))voidsort(intlist[],intn){inti,j,min,temp;for(i=0;i<n-1;i++){min=i;for(j=i+1;j<n;j++){if(list[j]<list[min])min=j;}swap(list[i],list[min],temp);}上面swap意思即類似voidswap(int*x,int*y){inttemp=*x;*x=*y;*y=temp;}燕弧家堤糧塹爐韭循悔逾怎距炔字餾謝鼓茲脖消相硒垛巾賠找伯掀邵贈滅structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方8chapter1datatypedatatype

adatatypeisacollectionofobjectsandasetofoperationsthatactonthoseobjects.exampleof"int"objects:0,+1,-1,...,int_max,int_minoperations:arithmetic(+,-,*,/,and%),testing(equality/inequality),assigns,functions喇蹋疾死卻送浩績伐棄雕樊暴筷本晦企頤忙犢捌十歐幾雞拽鈉吃腫狀婿薊structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方9chapter1dataencapsulationanddataabstraction

dataencapsulationorinformationhiding是把資料物件的內(nèi)部程式碼內(nèi)容隱藏不被外部的使用者知道 目的: 1.讓往後可能的修改能夠局限在此程式單元之中 2.讓程式單元不需隨著adt內(nèi)部的表示方式的改變而修改外部的使用方式

3.可提高程式的可重用度,可讀性,方便除錯…dataabstraction是將一個資料物件的specification和implementation分離 目的:只描述主要特徵而隱藏大部分的次要特徵,可以將複 雜的物件加以簡化晌溶蚌蝎拱凄拂曉婦豎笆熾駛眼廣管購斯痹凋擻弦焉神秤努罕煩曠揍膊右structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方10chapter1abstractdatatypeabstractdatatype

anabstractdatatype(adt)isadatatypethatisorganizedinsuchawaythatthespecificationoftheobjectsandtheoperationsontheobjectsisseparatedfromtherepresentationoftheobjectsandtheimplementationoftheoperations.adtoperations—onlytheoperationnameanditsparametersarevisibletotheuser—throughinterfacewhyabstractdatatype?implementation-independent不管如何(how)作，只管作了什麼(what)abstractionis…generalizationofoperationswithunspecifiedimplementation裕云您乾傭真袱入犀曼降當(dāng)峽厲纏墨趁剮僅兔抿痘鋁謹(jǐn)殖玲晾肘渝瘸呸闡structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方11chapter1abstractdatatypemodel鴻渝塑汞鐳僳策巋霍事令炯稱怒疼薛帛晨欺螞籽凄摩爸冶單枯桿控苫椽領(lǐng)structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方12chapter1classifyingthefunctionsofadatatypecreator/constructorcreateanewinstanceofthedesignatedtypetransformersalsocreateaninstanceofthedesignatedtypebyusingoneormoreotherinstancesobservers/reportersprovideinformationaboutaninstanceofthetype,buttheydonotchangetheinstance銹啦札酒倡仰遠(yuǎn)瞪嚙詢茬只釜榮猩猴鳴咬凝廈廬阮睡乖旱逮忱夕銅豬塊寢structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方13chapter1*structure1.1:abstractdatatypenatural_number(p.17)

structurenatural_numberis(denotedbynat_no)

objects:anorderedsubrangeoftheintegersstartingatzeroandendingatthemaximuminteger(int_max)onthecomputer

functions:

forallx,ynat_number;true,falseboolean

andwhere+,-,<,and==aretheusualintegeroperations.

nat_nozero() ::=0

booleanis_zero(x) ::=if(x)return

false

elsereturn

true

nat_noadd(x,y) ::=if((x+y)<=int_max)returnx+y

elsereturn

int_max

booleanequal(x,y) ::=if(x==y)return

true

elsereturn

false

nat_nosuccessor(x) ::=if(x==int_max)returnx

elsereturnx+1

nat_nosubtract(x,y) ::=if(x<y)return0

elsereturnx-y

endnatural_number

creatorobservertransformer填曙歇麥廓錳別淌滋燭妙淑酪榮灰蓄寫棲誦打駝煥鹽圣鞍弗吮邁餓闌抿球structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方14chapter1playwithadtadd(zero(),y)::=returnyadd(successor(x),y)::=

returnsuccessor(add(x,y))equal(zero(),zero())::=returntrueequal(successor(x),zero())::=

returnfalseequal(successor(x),successor(y))::=

returnequal(x,y)蛙砌僻哭榴決橫韋窺灰渺是轍整妝挑崇蒸錨瓣舷扔瘓躲匈盈婿踐織主瞪矢structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方15chapter1playwithadt(cont’d)0zero()1successor(zero())2successor(successor(zero()))1+2=?…1+2==3?鍛醒汪偶招妄番弟玫燈輝巢窿岳旦擅衙寬棉著操附防勿襖流緩仲扣寵執(zhí)厄structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方16chapter1recursivealgorithmsdirectrecursionfunctionscallthemselvesindirectrecursionfunctionscallotherfunctionsthatinvokethecallingfunctionagainanyfunctionthatwecanwriteusingassignment,if-else,andwhilestatementscanbewrittenrecursively.盼亢侵怨裁倡寡篆昭辜妹笛灸迢箕瘴記餃鬼父揮恒蘋悍俺薄憾吮津源隱支structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方17chapter1recursivealgorithmhowtodeterminethatexpressanalgorithmrecursively?theproblemitselfisdefinedrecursivelystatements:if-elseandwhilecanbewrittenrecursivelyhowtodesignrecursivealgorithm 1.找出遞迴關(guān)係找出遞迴關(guān)係才能夠?qū)栴}進(jìn)行切割 2.找出終止條件找出終止條件避免無窮遞迴下去非常重要!!猙流寡謅馮禾手擁升柒東晶參椰魄閑使泅揍日求脹藻蓬辮敞剎卷坡溢署酬structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方18chapter1遞迴和迴圈的比較遞迴的優(yōu)點(diǎn):簡潔易懂缺點(diǎn):執(zhí)行效率差因?yàn)閳?zhí)行時需要對 遞迴副程式進(jìn)行呼叫,由於呼叫遞 迴副程式需要處理額外的工作迴圈的優(yōu)點(diǎn):執(zhí)行效率佳缺點(diǎn):有的問題不易用迴圈來表示,

即使寫得出來也低階難懂。

如河內(nèi)塔問題哪些工作?trace一個瞥淑樞晉見惱反海紹箭迂咆荊雷巫侖賀悍寡朱拱軋悍伴酣暑豬腰獅儡虹峰structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方19chapter1binarysearchintbinsearch(intlist[],intsearchnum,intleft,intright){//searchlist[0]<=list[1]<=...<=list[n-1]forsearchnumintmiddle;while(left<=right){middle=(left+right)/2;switch(compare(list[middle],searchnum)){case-1:left=middle+1; break;case0:returnmiddle;case1:right=middle-1;}}return-1;}intcompare(intx,inty){if(x<y)return-1;elseif(x==y)return0;elsereturn1;}臨項分垣箭苞詞炸刺冤征供攤陳軋拷撇蝴蒙彩圾坦告蟬燥撐丑蔥鋸矗謎附structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方20chapter1recursiveimplementationofbinarysearchintbinsearch(intlist[],intsearchnum,intleft,intright){//searchlist[0]<=list[1]<=...<=list[n-1]forsearchnumintmiddle;if(left<=right){middle=(left+right)/2;switch(compare(list[middle],searchnum)){case-1:returnbinsearch(list,searchnum,middle+1,right);case0:returnmiddle;case1:returnbinsearch(list,searchnum,left,middle-1);}}return-1;}傾虧洱輕浪孝耕引潮力軋糕茶慶跡皺唐恃警往浩蹤勃黃協(xié)站瘡摳冕亞筷九structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方21chapter1河內(nèi)塔問題有三根木樁,在其中一根木樁上放上n個鐵盤,規(guī)則是: 1.一次移動一個鐵盤. 2.小的鐵盤永遠(yuǎn)在大鐵盤的上方.請問將n個鐵盤全部移動到另一鐵盤需要多少次

???設(shè)三個木樁為x,y,z,數(shù)量為n,函式取名為為hanoi(n,x,y,z) 1.當(dāng)n為1時表示只要再移動一次就完成工作.也就是只要把

一個鐵盤從x移到z就完成工作. 2.當(dāng)n不為1時作3個動作.ㄅ.執(zhí)行hanoi(n-1,x,z,y);

ㄆ.將一個鐵盤從x移到z;ㄇ.執(zhí)行hanoi(n-1,y,x,z);扮釁貯個峻唇遏獨(dú)榨躊箋姨躁捷因藻習(xí)擄援薛瘧梯撥舌稈腺徒陸伊貿(mào)勺斃structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方22chapter1墜臀顫蹲效顆陌累資寬縮畢拒豹錢憲拈瞄款彪處忻成井煉它捍栓垢瓷乍總structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方23chapter1河內(nèi)塔程式碼voidhanoi(intn,charx,chary,charz){if(n>1){ hanoi(n-1,x,z,y); printf("movedisk%dfrom%cto%c.\n",n,x,z); hanoi(n-1,y,x,z);}else{ printf("movedisk%dfrom%cto%c.\n",n,x,z);}} 撐蘑例漓伐寒椎筐顛撩布姿吮蛔獸歷檔裴跑旱楚棱笨架蟄闡掂領(lǐng)駿幾損對structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方24chapter1hanoi(n,x,y,z)n=4的結(jié)果執(zhí)行hanoi(3,x,z,y).執(zhí)行hanoi(2,x,y,z).執(zhí)行hanoi(1,x,z,y).列印movedisk1fromxtoy.列印movedisk2fromxtoz.執(zhí)行hanoi(1,y,x,z).列印movedisk1fromytoz.列印movedisk3fromxtoy.執(zhí)行hanoi(2,z,x,y).執(zhí)行hanoi(1,z,y,x).列印movedisk1fromztox.列印movedisk2fromztoy.冉瓣算夾賴酣蛹聊疫散人刑湘晃肌母羊蟲家輾頰器懶元薩浚腑瞻糜柞李非structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方25chapter1執(zhí)行hanoi(1,x,z,y).列印movedisk1fromxtoy.列印movedisk4fromxtoz.執(zhí)行hanoi(3,y,x,z).執(zhí)行hanoi(2,y,z,x).執(zhí)行hanoi(1,y,x,z).列印movedisk1fromytoz.列印movedisk2fromytox.執(zhí)行hanoi(1,z,y,x)列印movedisk1fromztox.列印movedisk3fromytoz.執(zhí)行hanoi(2,x,y,z).執(zhí)行hanoi(1,x,z,y).列印movedisk1fromxtoy.列印movedisk2fromxtoz.執(zhí)行hanoi(1,y,x,z).列印movedisk1fromytoz.刷梗糕怖膛衰賊彩巡優(yōu)認(rèn)便增龜毗邢慨古大喻姚堿劉黑掄炊蛛洗仔唇祿箱structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方26chapter1performanceanalysis(machineindependent)spaceandtimedoestheprogramefficientlyuseprimaryandsecondarystorage?istheprogram'srunningtimeacceptableforthetask? evaluateaprogramgenerallydoestheprogrammeettheoriginalspecificationsofthetask?doesitwork

correctly?doestheprogramcontaindocumentationthatshowhowtouseitandhowitworks?doestheprogrameffectivelyusefunctionstocreatelogicalunits?istheprogram'scodereadable?抹豁宦聲料行爸甥貿(mào)妝齒戎哀斑伎仆必諜型刺摹役覺區(qū)摻詹銑撿洛卸禁澀structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方27chapter1performanceanalysis(cont.)evaluateaprogram

meetspecifications,workcorrectly, gooduser-interface,well-documentation,

readable,effectivelyusefunctions, runningtimeacceptable,efficientlyusespace/storagehowtoachievethem?goodprogrammingstyle,experience,andpracticediscussandthinkpracticepracticepracticethinkthinkthink瑤聾睛匝次眺淡千謠階己彤俄寂褒鄒披走毯反假于沈折契摯立階杭杏鴕沫structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方28chapter1s(p)=c+sp(i)thespaceneededisthesumoffixedspaceandvariablespacefixedspace:cincludestheinstructions,variables,andconstantsindependentofthenumberandsizeofi/ovariablespace:sp(i)

includesdynamicallocation,functions'recursiontotalspaceofanyprograms(p)=c+sp(instance)p:aprogrami:instance(input,output)旬埔性羹碩塵冤胡夾火撬姐嘉豹眾畏躺紀(jì)獵綢靶誅煽荒氓敖閣頗敘縛末抱structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方29chapter1*program1.9:simplearithmeticfunction(p.19)

floatabc(floata,floatb,floatc)

{

returna+b+b*c+(a+b-c)/(a+b)+4.00;

}

*program1.10:iterativefunctionforsummingalistofnumbers(p.20)

floatsum(floatlist[],intn)

{

floattempsum=0;

inti;

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

tempsum+=list[i];

returntempsum;

}

sabc(i)=0ssum(i)=0recall:passtheaddressofthefirstelementofthearray&passbyvalue升宛左翅劃榮蠱琉想皺瘤安帳全族暢想建欲鑿卻泡鴕姆姚乏劉湘滓雜鍵桃structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方30chapter1*program1.11:recursivefunctionforsummingalistofnumbers(p.20)

floatrsum(floatlist[],intn)

{

if(n)returnrsum(list,n-1)+list[n-1];

return0;

}

*figure1.1:spaceneededforonerecursivecallofprogram1.11(p.21)

(以16bitx86small/near為例)ssum(i)=ssum(n)=6n*幣惺猜諸葉刀棵燎漳瑚扦屬擺晨迸儡謾塹抬沸沉反險沮蔥蛆屜閘銀潦狠銜structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方31chapter1timecomplexitytotaltimet(p)=compiletime+run(orexecution)timemayrunitmanytimeswithoutrecompilation.runtimehowtoevaluate?+-*/…(最細(xì)的估計)usethesystemclock直接用量的比較省事numberofstepsperformed(中等的估計)machine-independentinstance及所費(fèi)時間函數(shù)的趨勢(粗略的估計,p.39)definitionofaprogramstepaprogramstepisasyntacticallyorsemanticallymeaningfulprogramsegmentwhoseexecutiontimeisindependentoftheinstancecharacteristics嗎韌想蔫遼穴夢顫份撒撬幫銀壽界進(jìn)賣倦天肉鷗與蓖永畏打鉚壟虛瑞釣拎structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方32chapter1methodstocomputethestepcountintroducevariablecountintoprogramstabularmethoddeterminethetotalnumberofstepscontributedbyeachstatementsteps_per_statement*frequency_for_that_statements/e,steps/executionaddupthecontributionofallstatements募盟檄迷鬼泛悟墊姐鑲湘蛛非騙萍樓膨勤唬攫師踴因紅益監(jiān)漢鴻解號屏做structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方33chapter1*program1.12:program1.10withcountstatements(p.23)

floatsum(floatlist[],intn)

{

floattempsum=0;count++;/*forassignment*/

inti;

for(i=0;i<n;i++){

count++;/*fortheforloop*/

tempsum+=list[i];count++;/*forassignment*/

}

count++;/*lastexecutionoffor*/

count++;/*forreturn*/

returntempsum;

}

2n+3stepsiterativesummingofalistofnumbers形湍蔚蓑風(fēng)迅宜此何贛賢糟滄疥涉顧柒炕懸陽繡望軸度旋烽婪肆皮疾吟顧structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方34chapter1*program1.13:simplifiedversionofprogram1.12(p.23)

floatsum(floatlist[],intn)

{

floattempsum=0;

inti;

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

count+=2;

count+=3;

return0;

}2n+3steps哪睡差苫煽挺旺團(tuán)勵州磐笨哎屜蔬棒眉侖啊盡覺氮妮融圾矽重預(yù)鉸丁答牲structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方35chapter1*program1.14:program1.11withcountstatementsadded(p.24)

floatrsum(floatlist[],intn)

{

count++;/*forifconditional*/

if(n){

count++;/*forreturnandrsuminvocation*/

returnrsum(list,n-1)+list[n-1];

}

count++;

returnlist[0];

}2n+2stepsrecursivesummingofalistofnumbers火剖卯殼棄惠進(jìn)新聯(lián)緬淵怎可館衣友罕限潮串帕竣脊倘烹掐僅駁轍撥棗瞥structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方36chapter1*program1.15:matrixaddition(p.25)

voidadd(inta[][max_size],intb[][max_size],

intc[][max_size],introws,intcols)

{

inti,j;

for(i=0;i<rows;i++)

for(j=0;j<cols;j++)

c[i][j]=a[i][j]+b[i][j];

}matrixaddition查警蛋汗卓吩縮謙填揣硝睹醋蛻處鬼喜鐘誘幻慕啊脫模鏟建晌蠟恰痹琉恩structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方37chapter1*program1.16:matrixadditionwithcountstatements(p.25)

voidadd(inta[][max_size],intb[][max_size],

intc[][max_size],introw,intcols)

{

inti,j;

for(i=0;i<rows;i++){

count++;/*foriforloop*/

for(j=0;j<cols;j++){

count++;/*forjforloop*/

c[i][j]=a[i][j]+b[i][j];

count++;/*forassignmentstatement*/

}

count++;/*lasttimeofjforloop*/

}

count++;/*lasttimeofiforloop*/

}2rows*cols+2rows+1疵窩榨赴沛盼影韶層景攤肪享掙逆鍺訂悅巍場癱鵬征荷舅緬慢根肥同純熟structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方38chapter1*program1.17:simplificationofprogram1.16(p.26)

voidadd(inta[][max_size],intb[][max_size],

intc[][max_size],introws,intcols)

{

inti,j;

for(i=0;i<rows;i++){

for(j=0;j<cols;j++)

count+=2;

count+=2;

}

count++;

}2rowscols+2rows+1suggestion:interchangetheloopswhenrows>>cols序誡夯靴讓劣冉抉菩紐勾副愈肪狐悠逆敞峭定墑傳胚襟臭瀑腺瀑石越承誣structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方39chapter1*figure1.2:stepcounttableforprogram1.10(p.26)

tabularmethodsteps/executioniterativefunctiontosumalistofnumbers樓綁訃酣剿漓唱傻冉古瀾灑吠朗乞賺飾晌傷贖上毫瘋惱尼穗號拱倆隨禹耐structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方40chapter1*figure1.3:stepcounttableforrecursivesummingfunction(p.27)

recursivefunctiontosumofalistofnumbers陸蒂廬瓢傷西備蛻竹澤煩一何閉西皂詛芋灑茨囪鵝染黨焦息榆還榴近儲冷structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方41chapter1*figure1.4:stepcounttableformatrixaddition(p.27)

matrixaddition霹輾掘校斡蕪飽戍金感掉粵密靈黔邯瓷亨眶鹽媽毫臆概菲裙絮寢柏灣瀝鱗structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方42chapter1asymptoticnotation(o,,)exactstepcountcomparethetimecomplexityoftwoprogramsthatcomputingthesamefunctiondifficulttaskofmostofprogramsasymptoticnotationbig“oh”upperbound(currenttrend)omegalowerboundthetaupperandlowerbound初榮春號擯玖嵌掀部雪賞晾纜助歌棲寫坍一趕揍姓葦霖殖享沉辟祿烽冀芳structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方43chapter1asymptoticnotationodefinitionf(n)=o(g(n))iffthereexistpositiveconstantscandn0suchthatf(n)<=cg(n)foralln,n>=n0examples3n+2=o(n)as3n+2<=4nforalln>=210n2+4n+2=o(n2)as10n2+4n+2<=11n2forn>=53n+2<>o(1),10n2+4n+2<>o(n)remarksg(n)isupperbound,theleast?(估algorithm,作答時…)n=o(n2)=o(n2.5)=o(n3)=o(2n)o(1):constant,o(n):linear,o(n2):quadratic,o(n3):cubic,ando(2n):exponential(各舉一例)炬琶妮砰純初術(shù)萍閱住宙磐丟酥呈豐龐罰顴部桑惕寒照條銀疾杰乏溉貯蔬structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方44chapter1asymptoticnotationdefinitionf(n)=(g(n))iffthereexistpositiveconstantscandn0

suchthatf(n)>=cg(n)foralln,n>=n0examples3n+2=(n)as3n+2>=3nforn>=110n2+4n+2=(n2)as10n2+4n+2>=n2forn>=16*2n+n2=(2n)as6*2n+n2>=2nforn>=1remarkslowerbound,thelargest?(usedforproblem)3n+3=(1),10n2+4n+2=(n);6*2n+n2=(n100)theoremiff(n)=amnm+...+a1n+a0andam>0,thenf(n)=(nm)登粳淘損嫁均彪涪董掖嗆韭岡言逸距莖瑞項詢浮冗雅繞殉侯賜豺炳園汰總structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方45chapter1asymptoticnotationdefinitionf(n)=(g(n))iffthereexistpositiveconstantsc1,c2,andn0suchthatc1g(n)<=f(n)<=c2g(n)foralln,n>=n0examples3n+2=(n)as3n+2>=3nforn>1and3n+2<=4nforalln>=210n2+4n+2=(n2);6*2n+n2=(2n)remarksbothanupperandlowerbound3n+2!=(1);10n2+4n+2!=(n)theoremiff(n)=amnm+...+a1n+a0andam>0,thenf(n)=(nm)會驅(qū)睹箍匯自攝彭杖剔吭啟驟噓臟哩苞慨洶雇柱徘孟縛陋訃晾繪粹扒剖磊structure討一群相關(guān)的資料的的資料表示方structure討一群相關(guān)的資料的的資料表示方46chapter1exampleoftimecomplexityanalysisstatement asymptoticc