




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
2023/4/241ReviewoflastclassHowtosolveaproblembycomputerThenotionofalgorithmActualproblemMathematicsmodelAlgorithmdesignandanalysisProgrammingResultanalysisInputoutputfinitenesseffectivenessdefinitenessAlgorithmdesignpattern2023/4/242Howtodescribeanalgorithm?NaturallanguageStep1Inputmandn.Step2Dividembynandassignthevalueoftheremaindertor.Step3Ifr=0,returnthevalueofnastheanswerandstop;otherwise,proceedtoStep4.Step4Assignthevalueofntomandthevalueofrton.Step5GotoStep2.Advantages:easyunderstandDisadvantages:existinherentambiguity2023/4/243Howtodescribeanalgorithm?(II)FlowchartStartr=0Inputmandnr=m%nm=nn=routputnStopAflowchartisamethodofexpressinganalgorithmbyacollectionofconnectedgeometricshapescontainingdescriptionsofthealgorithm’ssteps.Advantages:intuitiveDisadvantages:lackflexibility2023/4/244Howtodescribeanalgorithm?(III)ProgramminglanguageAdvantages:canrunoncomputerdirectlyDisadvantages:lackabstraction#include<iostream.h>intGCD(intm,intn){
intr=m%n;
while(r!=0) { m=n; n=r; r=m%n; }
returnn;}voidmain(void){ cout<<GCD(60,24)<<endl;}2023/4/245Howtodescribeanalgorithm?(IV)Pseudocode1r=m%n;2Whiler≠02.1m=n;2.2n=r;2.3r=m%n;3returnn;Advantages:moreprecisethannaturallanguageApseudocodeisamixtureofanaturallanguageandprogramminglanguage.Itusesthebasicgrammarofprogramminglanguage,buttheoperationinstructionscandesignedwithnaturallanguage.Disadvantages:notexistasingleformofpseudocode2023/4/246FundamentalsoftheAnalysisofAlgorithmEfficiency(I)Chapter21、Theframeworktoanalyzealgorithms
2、Best,worst,average-caseanalysis
3、Threeasymptoticnotations2023/4/247GoalsofthislectureAttheendofthislecture,youshouldbeabletoDescribehowtoanalyzeanalgorithmUnderstandwhatisabest-case,worse-caseandaverage-caseanalysisMasterthethreeasymptoticnotations,,O,rateofgrowth2023/4/248AnalysisofalgorithmsDefinition:
Algorithmanalysismeanstoevaluatethetwocomputerresources,timeandspace,whichneededbyanalgorithm.Lessresourcesanalgorithmneeds,moreefficiencyitis.
Issues:timeefficiencyDeterminestheamountoftimethatalgorithmneedstobeexecuted.spaceefficiencyDeterminestheamountofspacethatalgorithmneedstobeexecuted.Approaches:
theoreticalanalysisempiricalanalysis2023/4/249Goal:DeterminestheamountoftimethatanalgorithmneedstobeexecutedMethods:DeterminestheexactamountoftimethatanalgorithmneedstobeexecutedDeterminesthenumberofrepetitionsofalltheoperationsasafunctionofinputsizeandinputinstanceWhereNistheinputsize,Iistheinputinstance.Theoreticalanalysisoftimeefficiency2023/4/2410OperationsComparisonsEqual,greater,notequal,…LogicaloperationsAnd,or,xor,not,…ArithmeticoperationsAdditions:add,subtract,increment,decrementMultiplications:multiply,divide,modAssignmentoperationX=1Forconvenience,eachelementaryoperationisconsideredtouse1timeunit.2023/4/2411SizeofInputSortingandFindingproblems:numberofelementinthearrayortableGraphalgorithms:numberofverticesoredges,orsumofbothComputationalGeometry:usuallynumberofpoints,vertices,edges,linesegments,orpolygons.MatrixOperation:dimensionofmatrixNumbertheoryandcryptography:numberofbitsofinputnumber2023/4/2412Examplesxx+1for
j1to
n
doxx+1repeatT(N,I)=3nnadditions,2nassignmentsT(N,I)=21addition,1assignmentfor
i1to
n
do
for
j1to
n
do
xx+1
repeatrepeatT(n)=3n2+nn2additions,2n2+nassignments2023/4/2413TheoreticalanalysisoftimeefficiencyDeterminingthenumberofrepetitionsofthebasicoperationasafunctionofinputsizeandinputinstanceBasicoperation:theoperationthatcontributesmosttowardstherunningtimeofthealgorithm
T(N,I)≈copC(N,I)runningtimeexecutiontimeforbasicoperationNumberoftimesbasicoperationisexecutedinputsize,inputinstance2023/4/2414InputsizeandbasicoperationexamplesBasicoperationInputsizemeasureProblemVisitingavertexortraversinganedge#verticesand/oredgesTheshortestpathproblemMultiplicationoftwonumbersMatrixdimensionsortotalnumberofelementsMultiplicationoftwomatricesKeycomparisonNumberoflist’sitems,i.e.nSearchingforkeyinalistofnitems2023/4/2415BestCaseAnalysisLeastamountofworktobedoneoverallofthepossibleinputwiththesamesizeWorstCaseAnalysis(mostimportant!)MostamountofworktobedoneoverallofthepossibleinputwiththesamesizeBest-case,average-case,worst-case2023/4/2416AverageCaseAnalysisTheamountofworkaveragedoverallofthepossibleinputsetswiththesamesizeNOTtheaverageofworstandbestcaseBest-case,average-case,worst-case(II)2023/4/2417Example:SequentialsearchWorstcaseBestcaseAveragecase2023/4/2418RateofGrowth(Important)Therateofgrowthofafunctiondetermineshowfastthefunctionvalueincreaseswhentheinputincrease2023/4/2419RateofGrowthThefunctionx3growsfasterthanthefunctionx2IfalgorithmAdoesx3operationsonaninputofsizexandalgorithmBdoesx2operations,algorithmBismoreefficientBecauseoftherelativeratesofgrowthoffunctions,wewillconsiderthefunctions
x3+x2+xequivalenttox3(thereasonisthatwhenxislarge,thedifferencebetweenthemislittle,soweonlykeeptheitemthatgrowsfastestwhileomitothers)2023/4/2420ClassificationofGrowthBigOmega?(f):Theclassoffunctionsthatgrowatleastasfastasthefunctionf,andmaybefasterBigOhO(f):Theclassoffunctionsthatgrownofasterthanf,andmaybeslowerBigTheta(f)Theclassoffunctionsthatgrowatthesamerateasthefunctionf2023/4/2421AsymptoticNotation:O(mostimportant!)O-notation:asymptoticupperboundCallf(n)=O(g(n))ifthereexistpositiveconstantscandn0suchthat0f(n)cg(n)forallnn0.Or,if,thenf(n)=O(g(n))f(n)=2n3+3n-5
=O(n3)f(n)=2n3+3n-5
=
O(n4)Intheanalysisliterature,f(n)=
O(g(n))meansf(n)O
(g(n))Thinking:2n=O(2n+1)?2n+1=O(2n)?(logn)2=O(n)? (n+1)!=O(n!)2023/4/2422AsymptoticNotation:Onf(n)cg(n)n0f(n)=O(g(n))2023/4/2423AsymptoticNotation:-notation:asymptoticlowerboundCallf(n)=(g(n))ifthereexistpositiveconstantscandn0suchthat0cg(n)f(n)
forallnn0.or,if,thenf(n)=(g(n))f(n)=2n3+3n-5
=
(n3)f(n)=2n3+3n-5
=
(n2)Intheanalysisliterature,f(n)=
(g(n))meansf(n)
(g(n))2023/4/2424AsymptoticNotation:ncg(n)f(n)n0f(n)=(g(n))2023/4/2425Somepropertiesofasymptoticorderofgrowthf(n)O(f(n))
f(n)O(g(n))iffg(n)(f(n))
Iff
(n)O(g
(n))andg(n)O(h(n)),thenf(n)O(h(n))
Iff1(n)O(g1(n))andf2(n)O(g2(n)),thenf1(n)+
f2(n)O(max{g1(n),g2(n)})2023/4/2426AsymptoticNotation:-notation:
Callf(n)=(g(n))ifthereexistpositiveconstantsc1,c2,andn0suchthat0c1g(n)f(n)c2g(n)forallnn0.or,if,cisaconstantandc
>0,thenf(n)=(g(n))f(n)=2n3+3n-5
=(n3)f(n)=2n4+1=(n3)???2023/4/2427AsymptoticNotation:f(n)=(g(n))nf(n)c2g(n)n0c1g(n)2023/4/2428OrdersofgrowthofsomeimportantfunctionsAlllogarithmicfunctionslogan
belongtothesameclass
(logn)nomatterwhatthelogarithm’sbasea>1is
Allpolynomialsofthesamedegreekbelongtothesameclass:
aknk+ak-1nk-1+…+a0(nk)
Exponentialfunctionsanhavediffe
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年硅系鐵合金項目合作計劃書
- 藤床架企業(yè)縣域市場拓展與下沉戰(zhàn)略研究報告
- 旅客進出站服務企業(yè)數(shù)字化轉型與智慧升級戰(zhàn)略研究報告
- 機器人汽車零部件瑕疵剔除行業(yè)深度調研及發(fā)展戰(zhàn)略咨詢報告
- 農產(chǎn)品倉儲企業(yè)縣域市場拓展與下沉戰(zhàn)略研究報告
- 果脯蜜餞食品企業(yè)數(shù)字化轉型與智慧升級戰(zhàn)略研究報告
- 木糖企業(yè)縣域市場拓展與下沉戰(zhàn)略研究報告
- 扒胎機企業(yè)數(shù)字化轉型與智慧升級戰(zhàn)略研究報告
- 乳食品企業(yè)縣域市場拓展與下沉戰(zhàn)略研究報告
- 小型貨車道路運輸企業(yè)數(shù)字化轉型與智慧升級戰(zhàn)略研究報告
- 甘肅四年級信息技術下冊教學設計(簡版)(含核心素養(yǎng))
- 作文復習:破繭成蝶逆天改命-《哪吒2》現(xiàn)象級成功的高考寫作啟示 課件
- 2025年錫林郭勒職業(yè)學院單招職業(yè)技能測試題庫標準卷
- 2025中建三局(中原)社會招聘高頻重點模擬試卷提升(共500題附帶答案詳解)
- 【生 物】光合作用課件-2024-2025學年人教版生物七年級下冊
- 人教版 七年級英語下冊 UNIT 2 單元綜合測試卷(2025年春)
- 2024年湖北省武漢市中考數(shù)學試題(解析版)
- 2024年“新能源汽車裝調工”技能及理論知識考試題與答案
- 【地理】非洲-位置與范圍 高原為主的地形課件-2024-2025學年湘教版(2024)七下
- 搶救車的管理
- GB/T 17350-2024專用汽車和專用掛車分類、名稱及型號編制方法
評論
0/150
提交評論