




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 公共衛(wèi)生執(zhí)業(yè)醫(yī)師考試新思維方法試題及答案
- 深度探討助理廣告師考試廣告活動(dòng)的評(píng)估標(biāo)準(zhǔn)試題及答案
- 食品配送承包合同范例
- 二零二五版租房意向金協(xié)議書(shū)范例
- 應(yīng)屆畢業(yè)生頂崗實(shí)習(xí)協(xié)議書(shū)
- 女方出軌離婚財(cái)產(chǎn)分割協(xié)議
- 債權(quán)轉(zhuǎn)讓三方協(xié)議
- 生物炭結(jié)構(gòu)對(duì)剩余污泥厭氧產(chǎn)甲烷效能的影響機(jī)制研究
- 明確考試方向2025年計(jì)算機(jī)二級(jí)考試試題及答案
- 初二政治學(xué)科教學(xué)工作總結(jié)(4篇)
- 期中測(cè)試卷(1-5單元)(試題)(含答案)-2024-2025學(xué)年二年級(jí)下冊(cè)數(shù)學(xué)青島版
- 2025屆北京市順義區(qū)高三下學(xué)期一模英語(yǔ)試題(原卷版+解析版)
- 人工智能技術(shù)與知識(shí)產(chǎn)權(quán)保護(hù)
- 2025-2030便利店行業(yè)市場(chǎng)發(fā)展現(xiàn)狀及發(fā)展前景與投資研究報(bào)告
- 2025屆高三湖北省十一校第二次聯(lián)考英語(yǔ)試卷(含答案詳解)
- 信息技術(shù)與小學(xué)教育教學(xué)融合
- 產(chǎn)品設(shè)計(jì)研發(fā)費(fèi)用統(tǒng)計(jì)表
- 提高教學(xué)管理質(zhì)量校長(zhǎng)講話:“2574”工作實(shí)施思路!即兩大抓手五項(xiàng)重點(diǎn)任務(wù)七個(gè)落實(shí)環(huán)節(jié)四個(gè)質(zhì)量目標(biāo)
- 2025屆廣東省深圳市高三年級(jí)第一次調(diào)研考試歷史試題
- 清理報(bào)廢漁船合同范本
- 《基于西門(mén)子S7-1200PLC的四層電梯控制系統(tǒng)設(shè)計(jì)》8900字
評(píng)論
0/150
提交評(píng)論