Data-Structure-(资料结构)课件

C.–C.YaoDataStructure(資料結構）AssistantProf.Chih-ChiaYao（姚志佳）E-mail:ccyao@.tw

C.–C.YaoDataStructure(資料結構C.–C.YaoText&Referencebooks教科書(Textbook)：EllisHorowitz,SartajSahni,andDineshP.Mehta,“FundamentalsofDataStructuresinC++”,2ndEd.,SiliconPress,2007.(開發圖書代理)中文版—基礎資料結構-使用C++,第二版,戴顯權譯,開發圖書參考書目(ReferenceBooks):EllisHorowitz,SartajSahni,andSusanAnderson-Freed,“FundamentalsofDataStructuresinC”,2ndEd.,SiliconPress,2008.(開發圖書代理)廖榮貴工作室，“資料結構與演算法”，文魁資訊股份有限公司.林貞嫻，“資料結構－使用C語言”，碁峰出版社.C.–C.YaoText&ReferencebooC.–C.YaoGrading1. 作業:20%2. 3次期中考(MidtermExams):90%3. 課程參與(Participation):10%C.–C.YaoGrading1. 作業:20%C.–C.YaoChap1BasicConcepts(基本概念)C.–C.YaoChap1BasicConceptsC.–C.YaoAlgorithmDefinition:Analgorithmisafinitesetofinstructionsthat,iffollowed,accomplishesaparticulartask.Inaddition,allalgorithmsmustsatisfythefollowingcriteria:Input.Zeromorequantitiesareexternallysupplied.Output.Atleastonequantityisproduced.Definiteness.Eachinstructionisclearandunambiguous.Finiteness.Ifwetraceouttheinstructionsofanalgorithm,thenforallcases,thealgorithmterminatesafterafinitenumberofsteps.Effectiveness.Everyinstructionmustbebasicenoughtobecarriedout,inprinciple,byapersonusingonlypencilandpaper.Itisnotenoughthateachoperationbedefiniteasin3)italsomustbefeasible.C.–C.YaoAlgorithmDefinition:C.–C.YaoExample:SelectionSortSupposewemustdeviseaprogramthatsortsacollectionofn≥1integers.

Fromthoseintegersthatarecurrentlyunsorted,findthesmallestandplaceitnextinthesortedlist.ProblemintheabovestatementDoesnotdescribewhereandhowtheintegersareinitiallysorted.Doesnotindicatewheretoplacetheresult.C.–C.YaoExample:SelectionSC.–C.YaoC++ProgramforSelectionSortvoid

sort(int*a,constint

n)//sortthenintegersa[0]toa[n-1]intonon-decreasingorder

for(int

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

int

j=i; //findsmallestintegerina[i]toa[n-1]

for(int

k=i+1;k<n;k++)

if(a[k]<a[j])j=k; //interchange

int

temp=a[i];a[i]=a[j];a[j]=temp; }}C.–C.YaoC++ProgramforSeleC.–C.YaoSelectionSort(Cont.)Theorem1.1:sort(a,n)correctlysortsasetofn≥1integers;theresultremainsina[0]…a[n-1]suchthata[0]≤a[1]≤…≤a[n–1].C.–C.YaoSelectionSort(ContC.–C.YaoExample:BinarySearchAssumethatwehaven≥1distinctintegersthatarealreadysortedandstoredinthearraya[0]…a[n-1].Ourtaskistodetermineiftheintegerxispresentandifsotoreturnjsuchthatx=a[j];otherwisereturn-1.Bymakinguseofthefactthatthesetissorted,weconceivethefollowingefficientmethod: Letleftandright,respectively,denotetheleftandrightendsofthelisttobesearched.Initially,left=0andright=n–1.Letmiddle=(left+right)/2bethemiddlepositioninthelist.Ifwecomparea[middle]withx,weobtainoneofthethreeresults: (1)x<a[middle].Inthiscase,ifxispresent,itmustbeinthepositionsbetween0andmiddle–1.Therefore,wesetright

tomiddle–1. (2)x==a[middle].Inthiscase,wereturnmiddle. (3)x>a[middle].Inthiscase,ifxispresent,itmustbeinthepositionsbetweenmiddle+1andn-1.So,wesetlefttomiddle+1.C.–C.YaoExample:BinarySearcC.–C.YaoAlgorithmforBinarySearchint

BinarySearch(int*a,constint

x,constint

n)//Searchthesortedarraya[0],…,a[n-1]forx{

for(initializeleftandright;whiletherearemoreelements;) { letmiddlebethemiddleelement;

switch(compare(x,a[middle])){

case‘>’:setlefttomiddle+1;break;

case‘<‘:setrighttomiddle-1;break;

case‘=‘:foundx; }//endofswitch }//endoffor notfound;}//endofBinarySearchC.–C.YaoAlgorithmforBinaryC.–C.YaoC++ProgramforBinarySearchcharcompare(intx,inty){

if(x>y)return‘>’;

elseif(x<y)return‘<‘;

elsereturn‘=‘;}//endofcompareC.–C.YaoC++ProgramforBinaC.–C.YaoAlgorithmforBinarySearch(Cont.)int

BinarySearch(int*a,constint

x,constint

n)//Searchthesortedarraya[0],…,a[n-1]forx{

for(int

left=0,right=n-1;left<=right;) {

int

middle=(left+right)/2;

switch(compare(x,a[middle])){

case‘>’:left=middle+1;break;//x>a[middle]

case‘<‘:right=middle-1;break;//x<a[middle]

case‘=‘:return

middle;//x==a[middle] }//endofswitch }//endoffor

return-1;}//endofBinarySearchC.–C.YaoAlgorithmforBinaryC.–C.YaoRecursiveAlgorithmsint

BinarySearch(int*a,constint

x,constint

left,constint

right){

if(left<=right) {

int

middle=(left+right)/2;

if(x<a[middle])returnBinarySearch(a,x,left,middle-1);

elseif(x<a[middle])returnBinarySearch(a,x,left,middle-1);

return

middle; }//endif

return-1;}//endofBinarySearchC.–C.YaoRecursiveAlgorithmsC.–C.YaoRecursiveAlgorithms(cont.)Recursiveprogram:

intmain() { intn=10; printf(“%d”,rfib(n)); } intrfib(intn) { if(n==1||n==2)return1; returnrfib(n1)+rfib(n2); }

C.–C.YaoRecursiveAlgorithmsC.–C.YaoPerformanceAnalysisSpaceComplexity:Thespacecomplexityofaprogramistheamountofmemoryitneedstoruntocompletion.TimeComplexity:Thetimecomplexityofaprogramistheamountofcomputertimeitneedstoruntocompletion.C.–C.YaoPerformanceAnalysisC.–C.YaoSpaceComplexityAfixedpartthatisindependentofthecharacteristicsoftheinputsandoutputs.Thisparttypicallyincludestheinstructionspace,spaceforsimplevarialbesandfixed-sizecomponentvariables,spaceforconstants,etc.Avariablepartthatconsistsofthespaceneededbycomponentvariableswhosesizeisdependentontheparticularprobleminstancebeingsolved,thespaceneededbyreferencedvariables,andtherecursionstackspace.ThespacerequirementS(P)ofanyprogramPiswrittenasS(P)=c+SpwherecisaconstantC.–C.YaoSpaceComplexityAfiC.–C.YaoTimeComplexityThetime,T(P),takenbyaprogramPisthesumofthecompiletimeandtherun(orexecution)time.Thecompiletimedoesnotdependontheinstancecharacteristics.Wefocusontheruntimeofaprogram,denotedbytp(instancecharacteristics).C.–C.YaoTimeComplexityThetC.–C.YaoTimeComplexityinC++GeneralstatementsinaC++program StepcountComments 0Declarativestatements 0Expressionsandassignmentstatements 1Iterationstatements NSwitchstatement NIf-elsestatement NFunctioninvocation 1orNMemorymanagementstatements 1orNFunctionstatements 0Jumpstatements 1orNC.–C.YaoTimeComplexityinCC.–C.YaoTimeComplexity(Cont.)Notethatastepcountdoesnotnecessarilyreflectthecomplexityofthestatement.Stepperexecution(s/e):Thes/eofastatementistheamountbywhichcountchangesasaresultoftheexecutionofthatstatement.C.–C.YaoTimeComplexity(ConC.–C.YaoTimeComplexityIterativeExamplefloat

sum(float*a,constintn){

floats=0;

for(inti=0;i<n;i++) s+=a[i];

return;}C.–C.YaoTimeComplexityIterC.–C.YaoStepCountofIterativeExamplefloat

sum(float*a,constintn){

floats=0; count++; //countisglobal

for(inti=0;i<n;i++) { count++; //forfor s+=a[i]; count++; //forassignment } count++; //forlasttimeoffor

count++; //forreturn

return;}C.–C.YaoStepCountofIteratC.–C.YaoStepCountofIterativeExample(Simplified)voidsum(float*a,constintn){

for(inti=0;i<n;i++) count+=2; count+=3;}Ifinitiallycount=0,thenthetotalofstepsis2n+3.C.–C.YaoStepCountofIteratC.–C.YaoTimeComplexityofRecursiveExamplefloatrsum(float*a,constintn){

if(n<=0)return0;

elsereturn(rsum(a,n–1)+a[n-1]);}C.–C.YaoTimeComplexityofRC.–C.YaoStepCountofRecursiveExamplefloatrsum(float*a,constintn){ count++; //forifconditional

if(n<=0){ count++; //forreturn

return0; }

else{

count++; //forreturn return(rsum(a,n–1)+a[n-1]); }}Assumetrsum(0)=2trsum(n) =2+trsum(n-1) =2+2+trsum(n-2) =2*2+trsum(n-2) =2n+trsum(0) =2n+2 C.–C.YaoStepCountofRecursC.–C.YaoMatrixAdditionExamplelinevoid

add(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}C.–C.YaoMatrixAdditionExamC.–C.YaoStepCountofMatrixAdditionExamplevoid

add(matrixa,matrixb,matrixc,intm,intn){

for(inti=0;i<m;i++) { count++; //forfori

for(intj=0;j<n;j++) { count++; //forforj c[i][j]=a[i][j]+b[i][j]; count++; //forassigment } count++; //forlasttimeofforj } count++; //forlasttimeoffori}C.–C.YaoStepCountofMatrixC.–C.YaoStepCountofMatrixAdditionExample(Simplified)linevoid

add(matrixa,matrixb,matrixc,intm,intn){

for(inti=0;i<m;i++){

for(intj=0;j<n;j++) count+=2; count+2; }count++;}C.–C.YaoStepCountofMatrixC.–C.YaoStepTableofMatrixAdditionExampleLines/eFrequencyTotalsteps101021m+1m+131m(n+1)mn+m41mnmn5010Totalnumberofsteps2mn+2m+1C.–C.YaoStepTableofMatrixC.–C.YaoFibonacciNumbersTheFibonaccisequenceofnumbersstartsas0,1,1,2,3,5,8,13,21,34,55,… Eachnewtermisobtainedbytakingthesumofthetwopreviousterms.IfwecallthefirsttermofthesequenceF0thenF0=0,F1=1,andingeneral

Fn=Fn-1+Fn-2,n≥2.C.–C.YaoFibonacciNumbersTheC.–C.YaoC++ProgramofFibonacciNumbers1 void

fibonacci(intn)2//computetheFibonaccinumberFn

3{4 if(n<=1)cout<<n<<endl; //F0=0,andF1=15 else{ //computeFn6 intfn;intfnm2=0;intfnm1=1;7 for(inti=2;i<=n;i++)8 {9 fn=fnm1+fnm2;10 fnm2=fnm1;11 fnm1=fn;12 }//endoffor13 cout<<fn<<endl;14 }//endofelse15 }//endoffibonacciC.–C.YaoC++ProgramofFibonC.–C.YaoStepCountofFibonacciProgramTwocases:n=0orn=1Line4regardedastwolines:4(a)and4(b),totalstepcountinthiscaseis2n>1Line4(a),6,and13areeachexecutedonceLine7getsexecutedntimes.Lines8–12getexecutedn-1timeseach.Line6hass/eof2andtheremaininglineshaveans/eof1.Totalstepsforthecasen>1is4n+1C.–C.YaoStepCountofFibonaC.–C.YaoAsymptoticNotationDeterminingstepcountshelpustocomparethetimecomplexitiesoftwoprogramsandtopredictthegrowthinruntimeastheinstancecharacteristicschange.Butdeterminingexactstepcountscouldbeverydifficult.Sincethenotionofastepcountisitselfinexact,itmaybeworththeefforttocomputetheexactstepcounts.Definition[Big“oh”]:f(n)=O(g(n))iffthereexistpositiveconstantscandn0suchthatf(n)≤cg(n)foralln,n≥n0C.–C.YaoAsymptoticNotationDC.–C.YaoExamplesofAsymptoticNotation3n+2=O(n) 3n+2≤4n foralln≥3100n+6=O(n) 100n+6≤101n foralln≥1010n2+4n+2=O(n2) 10n2+4n+2≤11n2 foralln≥5C.–C.YaoExamplesofAsymptotC.–C.YaoAsymptoticNotation(Cont.)Theorem1.2:Iff(n)=amnm+…+a1n+

a0,thenf(n)=O(nm).

Proof:

forn≥1

So,f(n)=O(nm)

C.–C.YaoAsymptoticNotationC.–C.YaoAsymptoticNotation(Cont.)Definition:[Omega]f(n)=Ω(g(n))iffthereexistpositiveconstantscandn0suchthatf(n)≥cg(n)foralln,n≥n0.Example:3n+2=Ω(n)100n+6=Ω(n)10n2+4n+2=Ω(n2)C.–C.YaoAsymptoticNotationC.–C.YaoAsymptoticNotation(Cont.)Definition:f(n)=Θ(g(n))iffthereexistpositiveconstantsc1,c2,andn0suchthatc1g(n)≤f(n)≤c2g(n)foralln,n≥n0.C.–C.YaoAsymptoticNotationC.–C.YaoAsymptoticNotation(Cont.)Theorem1.3:Iff(n)=amnm+…+a1n+

a0andam>0,thenf(n)=Ω(nm).

Theorem1.4:Iff(n)=amnm+…+a1n+

a0andam>0,thenf(n)=Θ(nm).

C.–C.YaoAsymptoticNotationC.–C.YaoPracticalComplexitiesIfaprogramPhascomplexitiesΘ(n)andprogramQhascomplexitiesΘ(n2),then,ingeneral,wecanassumeprogramPisfasterthanQforasufficientlargen.However,cautionneedstobeusedontheassertionof“sufficientlylarge”.C.–C.YaoPracticalComplexitiC.–C.YaoFunctionValueslognnnlognn2n32n010112122484248166416382464512256416642564096655365321601024327684294967296C.–C.YaoFunctionValueslognC.–C.YaoDataStructure(資料結構）AssistantProf.Chih-ChiaYao（姚志佳）E-mail:ccyao@.tw

C.–C.YaoDataStructure(資料結構C.–C.YaoText&Referencebooks教科書(Textbook)：EllisHorowitz,SartajSahni,andDineshP.Mehta,“FundamentalsofDataStructuresinC++”,2ndEd.,SiliconPress,2007.(開發圖書代理)中文版—基礎資料結構-使用C++,第二版,戴顯權譯,開發圖書參考書目(ReferenceBooks):EllisHorowitz,SartajSahni,andSusanAnderson-Freed,“FundamentalsofDataStructuresinC”,2ndEd.,SiliconPress,2008.(開發圖書代理)廖榮貴工作室，“資料結構與演算法”，文魁資訊股份有限公司.林貞嫻，“資料結構－使用C語言”，碁峰出版社.C.–C.YaoText&ReferencebooC.–C.YaoGrading1. 作業:20%2. 3次期中考(MidtermExams):90%3. 課程參與(Participation):10%C.–C.YaoGrading1. 作業:20%C.–C.YaoChap1BasicConcepts(基本概念)C.–C.YaoChap1BasicConceptsC.–C.YaoAlgorithmDefinition:Analgorithmisafinitesetofinstructionsthat,iffollowed,accomplishesaparticulartask.Inaddition,allalgorithmsmustsatisfythefollowingcriteria:Input.Zeromorequantitiesareexternallysupplied.Output.Atleastonequantityisproduced.Definiteness.Eachinstructionisclearandunambiguous.Finiteness.Ifwetraceouttheinstructionsofanalgorithm,thenforallcases,thealgorithmterminatesafterafinitenumberofsteps.Effectiveness.Everyinstructionmustbebasicenoughtobecarriedout,inprinciple,byapersonusingonlypencilandpaper.Itisnotenoughthateachoperationbedefiniteasin3)italsomustbefeasible.C.–C.YaoAlgorithmDefinition:C.–C.YaoExample:SelectionSortSupposewemustdeviseaprogramthatsortsacollectionofn≥1integers.

Fromthoseintegersthatarecurrentlyunsorted,findthesmallestandplaceitnextinthesortedlist.ProblemintheabovestatementDoesnotdescribewhereandhowtheintegersareinitiallysorted.Doesnotindicatewheretoplacetheresult.C.–C.YaoExample:SelectionSC.–C.YaoC++ProgramforSelectionSortvoid

sort(int*a,constint

n)//sortthenintegersa[0]toa[n-1]intonon-decreasingorder

for(int

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

int

j=i; //findsmallestintegerina[i]toa[n-1]

for(int

k=i+1;k<n;k++)

if(a[k]<a[j])j=k; //interchange

int

temp=a[i];a[i]=a[j];a[j]=temp; }}C.–C.YaoC++ProgramforSeleC.–C.YaoSelectionSort(Cont.)Theorem1.1:sort(a,n)correctlysortsasetofn≥1integers;theresultremainsina[0]…a[n-1]suchthata[0]≤a[1]≤…≤a[n–1].C.–C.YaoSelectionSort(ContC.–C.YaoExample:BinarySearchAssumethatwehaven≥1distinctintegersthatarealreadysortedandstoredinthearraya[0]…a[n-1].Ourtaskistodetermineiftheintegerxispresentandifsotoreturnjsuchthatx=a[j];otherwisereturn-1.Bymakinguseofthefactthatthesetissorted,weconceivethefollowingefficientmethod: Letleftandright,respectively,denotetheleftandrightendsofthelisttobesearched.Initially,left=0andright=n–1.Letmiddle=(left+right)/2bethemiddlepositioninthelist.Ifwecomparea[middle]withx,weobtainoneofthethreeresults: (1)x<a[middle].Inthiscase,ifxispresent,itmustbeinthepositionsbetween0andmiddle–1.Therefore,wesetright

tomiddle–1. (2)x==a[middle].Inthiscase,wereturnmiddle. (3)x>a[middle].Inthiscase,ifxispresent,itmustbeinthepositionsbetweenmiddle+1andn-1.So,wesetlefttomiddle+1.C.–C.YaoExample:BinarySearcC.–C.YaoAlgorithmforBinarySearchint

BinarySearch(int*a,constint

x,constint

n)//Searchthesortedarraya[0],…,a[n-1]forx{

for(initializeleftandright;whiletherearemoreelements;) { letmiddlebethemiddleelement;

switch(compare(x,a[middle])){

case‘>’:setlefttomiddle+1;break;

case‘<‘:setrighttomiddle-1;break;

case‘=‘:foundx; }//endofswitch }//endoffor notfound;}//endofBinarySearchC.–C.YaoAlgorithmforBinaryC.–C.YaoC++ProgramforBinarySearchcharcompare(intx,inty){

if(x>y)return‘>’;

elseif(x<y)return‘<‘;

elsereturn‘=‘;}//endofcompareC.–C.YaoC++ProgramforBinaC.–C.YaoAlgorithmforBinarySearch(Cont.)int

BinarySearch(int*a,constint

x,constint

n)//Searchthesortedarraya[0],…,a[n-1]forx{

for(int

left=0,right=n-1;left<=right;) {

int

middle=(left+right)/2;

switch(compare(x,a[middle])){

case‘>’:left=middle+1;break;//x>a[middle]

case‘<‘:right=middle-1;break;//x<a[middle]

case‘=‘:return

middle;//x==a[middle] }//endofswitch }//endoffor

return-1;}//endofBinarySearchC.–C.YaoAlgorithmforBinaryC.–C.YaoRecursiveAlgorithmsint

BinarySearch(int*a,constint

x,constint

left,constint

right){

if(left<=right) {

int

middle=(left+right)/2;

if(x<a[middle])returnBinarySearch(a,x,left,middle-1);

elseif(x<a[middle])returnBinarySearch(a,x,left,middle-1);

return

middle; }//endif

return-1;}//endofBinarySearchC.–C.YaoRecursiveAlgorithmsC.–C.YaoRecursiveAlgorithms(cont.)Recursiveprogram:

intmain() { intn=10; printf(“%d”,rfib(n)); } intrfib(intn) { if(n==1||n==2)return1; returnrfib(n1)+rfib(n2); }

C.–C.YaoRecursiveAlgorithmsC.–C.YaoPerformanceAnalysisSpaceComplexity:Thespacecomplexityofaprogramistheamountofmemoryitneedstoruntocompletion.TimeComplexity:Thetimecomplexityofaprogramistheamountofcomputertimeitneedstoruntocompletion.C.–C.YaoPerformanceAnalysisC.–C.YaoSpaceComplexityAfixedpartthatisindependentofthecharacteristicsoftheinputsandoutputs.Thisparttypicallyincludestheinstructionspace,spaceforsimplevarialbesandfixed-sizecomponentvariables,spaceforconstants,etc.Avariablepartthatconsistsofthespaceneededbycomponentvariableswhosesizeisdependentontheparticularprobleminstancebeingsolved,thespaceneededbyreferencedvariables,andtherecursionstackspace.ThespacerequirementS(P)ofanyprogramPiswrittenasS(P)=c+SpwherecisaconstantC.–C.YaoSpaceComplexityAfiC.–C.YaoTimeComplexityThetime,T(P),takenbyaprogramPisthesumofthecompiletimeandtherun(orexecution)time.Thecompiletimedoesnotdependontheinstancecharacteristics.Wefocusontheruntimeofaprogram,denotedbytp(instancecharacteristics).C.–C.YaoTimeComplexityThetC.–C.YaoTimeComplexityinC++GeneralstatementsinaC++program StepcountComments 0Declarativestatements 0Expressionsandassignmentstatements 1Iterationstatements NSwitchstatement NIf-elsestatement NFunctioninvocation 1orNMemorymanagementstatements 1orNFunctionstatements 0Jumpstatements 1orNC.–C.YaoTimeComplexityinCC.–C.YaoTimeComplexity(Cont.)Notethatastepcountdoesnotnecessarilyreflectthecomplexityofthestatement.Stepperexecution(s/e):Thes/eofastatementistheamountbywhichcountchangesasaresultoftheexecutionofthatstatement.C.–C.YaoTimeComplexity(ConC.–C.YaoTimeComplexityIterativeExamplefloat

sum(float*a,constintn){

floats=0;

for(inti=0;i<n;i++) s+=a[i];

return;}C.–C.YaoTimeComplexityIterC.–C.YaoStepCountofIterativeExamplefloat

sum(float*a,constintn){

floats=0; count++; //countisglobal

for(inti=0;i<n;i++) { count++; //forfor s+=a[i]; count++; //forassignment } count++; //forlasttimeoffor

count++; //forreturn

return;}C.–C.YaoStepCountofIteratC.–C.YaoStepCountofIterativeExample(Simplified)voidsum(float*a,constintn){

for(inti=0;i<n;i++) count+=2; count+=3;}Ifinitiallycount=0,thenthetotalofstepsis2n+3.C.–C.YaoStepCountofIteratC.–C.YaoTimeComplexityofRecursiveExamplefloatrsum(float*a,constintn){

if(n<=0)return0;

elsereturn(rsum(a,n–1)+a[n-1]);}C.–C.YaoTimeComplexityofRC.–C.YaoStepCountofRecursiveExamplefloatrsum(float*a,constintn){ count++; //forifconditional

if(n<=0){ count++; //forreturn

return0; }

else{

count++; //forreturn return(rsum(a,n–1)+a[n-1]); }}Assumetrsum(0)=2trsum(n) =2+trsum(n-1) =2+2+trsum(n-2) =2*2+trsum(n-2) =2n+trsum(0) =2n+2 C.–C.YaoStepCountofRecursC.–C.YaoMatrixAdditionExamplelinevoid

add(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}C.–C.YaoMatrixAdditionExamC.–C.YaoStepCountofMatrixAdditionExamplevoid

add(matrixa,matrixb,matrixc,intm,intn){

for(inti=0;i<m;i++) { count++; //forfori

for(intj=0;j<n;j++) { count++; //forforj c[i][j]=a[i][j]+b[i][j]; count++; //forassigment } count++; //forlasttimeofforj } count++; //forlasttimeoffori}C.–C.YaoStepCountofMatrixC.–C.YaoStepCountofMatrixAdditionExample(Simplified)linevoid

add(matrixa,matrixb,matrixc,intm,intn){

for(inti=0;i<m;i++){

for(intj=0;j<n;j++) count+=2; count+2; }count++;}C.–C.YaoStepCountofMatrixC.–C.YaoStepTableofMatrixAdditionExampleLines/eFrequencyTotalsteps101021m+1m+131m(n+1)mn+m41mnmn5010Totalnumberofsteps2mn+2m+1C.–C.YaoStepTableofMatrixC.–C.YaoFibonacciNumbersTheFibonaccisequenceofnumbersstartsas0,1,1,2,3,5,8,13,21,34,55,… Eachnewtermisobtainedbytakingthesumofthetwopreviousterms.IfwecallthefirsttermofthesequenceF0thenF0=0,F1=1,andingeneral

Fn=Fn-1+Fn-2,n≥2.C.–C.YaoFibonacciNumbersTheC.–C.YaoC++ProgramofFibonacciNumbers1 void

fibonacci(intn)2//computetheFibonaccinumberFn

3{4 if(n<=1)cout<<n<<endl; //F0=0,andF1=15 else{ //computeFn6 intfn;intfnm2=0;intfnm1=1;7 for(inti=2;i<=n;i++)8 {9 fn=fnm1+fnm2;10 fnm2=fnm1;11 fnm1=fn;12 }//endoffor13 cout<<fn<<endl;