




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
Lecture1
IntroductionOverview1.Introduction (a)WhatareAlgorithms? (b)DesignofAlgorithms. (c)AnalysisofAlgorithms.2.Complexity (a)Asymptoticanalysis,OandΘ. (b)Orderofgrowth.Whatarealgorithms?Analgorithmisawell-definedfinitesetofrulesthatspecifiesasequentialseriesofelementaryoperationstobeappliedtosomedatacalledtheinput,producingafterafiniteamountoftimesomedatacalledtheoutput.Analgorithmsolvessomecomputationalproblem.Algorithms(alongwithdatastructures)arethefundamental“buildingblocks”fromwhichprogramsareconstructed.Onlybyfullyunderstandingthemisitpossibletowriteveryeffectiveprograms.CharacteristicsofalgorithmsAllalgorithmsmustsatisfythefollowingcriteria: (1)Input:Therearezeroormorequantitiesthatareexternallysupplied. (2)Output:Atleastonequantityisproduced. (3)Definiteness(確定性):Eachinstructionisclearandunambiguous. (4)Finiteness(有窮性):Ifwetraceouttheinstructionsofanalgorithm,thenforallcases,thealgorithmterminatesafterfinitenumberofsteps. (5)Effectiveness(有效性):Everyinstructionmustbebasicenoughtobecarriedout,inprinciple,byapersonusingonlypencilandpaper.AlgorithmdesignandanalysisAnalgorithmicsolutiontoacomputationalproblemwillusuallyinvolvedesigninganalgorithm,andthenanalysingitsperformance.DesignAgoodalgorithmdesignermusthaveathoroughbackgroundknowledgeofalgorithmictechniques,butespeciallysubstantialcreativityandimagination.AnalysisAgoodalgorithmanalystmustbeabletocarefullyestimateorcalculatetheresources(time,spaceorother)thatthealgorithmwillusewhenrunning.Thisrequireslogic,careandoftensomemathematicalability.Theaimofthiscourseistogiveyousufficientbackgroundtounderstandandappreciatetheissuesinvolvedinthedesignandanalysisofalgorithms.DesignandanalysisIndesigningandanalysinganalgorithmweshouldconsiderthefollowingquestions: 1.Whatistheproblemwehavetosolve? 2.Doesasolutionexist? 3.Canwefindasolution(algorithm),andistheremorethanonesolution? 4.Isthealgorithmcorrect? 5.Howefficientisthealgorithm?Algorithmdesignandanalysis--anexampleTheFibonaccisequenceisthesequenceofintegersstarting: 1,1,2,3,5,8,13,21,34,55,...Theformaldefinitionis: F1=F2=1andFn=Fn?1+Fn?2.PleasedeviseanalgorithmtocomputeFn.AnaiverecursivesolutionAnaivesolutionistosimplywritearecursivemethodthatdirectlymodelstheproblem.Isthisagoodalgorithm/programintermsofresourceusage?Timingitona(2005)iMacgivesthefollowingresults(thetimeisinsecondsandisforaloopcalculatingFn10000times).intfib(intn){
return
(n<
3
?
1
:fib(n-1)
+fib(n-2));}AnaiverecursivesolutionHowlongwillittaketocompute F30,F40orF50?Exercise:Showthenumberofmethodcallsmadetofib()is2Fn-1?1.AniterativealgorithmWfib(intn)
{
intf_2;
/*F(i+2)*/
intf_1=
1;
/*F(i+1)*/
intf_0=
1;
/*F(i)*/
for
(int
i
=
1;
i
<n;
i++)
{
/*F(i+2)=F(i+1)+F(i)*/f_2=f_1+f_0;
/*F(i)=F(i+1);F(i+1)=F(i+2)*/f_0=f_1;f_1=f_2;
}
returnf_0;}AmatrixalgorithmWehavethefollowingequation:UseMathematicalInduction: Basis:Forn=2, Inductivestep:Ifn=k,theequationholds,thenAmatrixalgorithm Bothsidesmultiplyby[1,1;1,0],weget Thus,theequationholdsforn=k+1.Usetheideaofdivide-and-conquerAlittlemore…GeneraltermformulaProveituseinduction.Hardtoimplement.EvaluatingalgorithmsCorrectness 1.Theoreticalcorrectness 2.NumericalstabilityEfficiency 1.Time 2.SpaceAnalgorithmisefficientifitusesasfewresourcesaspossible.Inmanysituationsthereisatrade-offbetweentimeandspace,inthatanalgorithmcanbemadefasterifitusesmorespaceorsmallerifittakeslonger.Althoughathoroughanalysisofanalgorithmshouldconsiderbothtimeandspace,timeisconsideredmoreimportant.NumericalstabilityYoucanbefairlycertainofexactresultsfromacomputerprogramprovidedallarithmeticisdonewiththeintegers
Z={...,?3,?2,?1,0,1,2,3,...}andyouguardcarefullyaboutanyoverflow.Howeverthesituationisentirelydifferentwhentheprobleminvolvesrealnumber,becausethereisnecessarilysomeround-offerrorwhenrealnumbersarestoredinacomputer.Afloatingpointrepresentationofanumberinbase"withprecisionpisarepresentationoftheform.Accumulationoferrors#include<stdio.h>intmain(){
doublet=
0.1;
for
(int
i
=
0;
i
<
20;
i++)
{
printf("%.16lf\n",t);t+=
0.1;
}
return
0;}MeasuringtimeHowshouldwemeasurethetimetakenbyanalgorithm?Wecandoitexperimentallybymeasuringthenumberofsecondsittakesforaprogramtorun—thisisoftencalledbenchmarkingandisoftenseeninpopularmagazines.Thiscanbeuseful,butdependsonmanyfactors:Themachineonwhichitisrunning.Thelanguageinwhichitiswritten.Theskilloftheprogrammer.Theinstanceonwhichtheprogramisbeingrun,bothintermsofsizeandwhichparticularinstanceitis.Soitisnotanindependentmeasureofthealgorithm,butratherameasureoftheimplementation,themachineandtheinstance.ComplexityThecomplexityofanalgorithmisa“device-independent”measureofhowmuchtimeitconsumes.Ratherthanexpressingthetimeconsumedinseconds,weattempttocounthowmany“elementaryoperations”thealgorithmperformswhenpresentedwithinstancesofdifferentsizes.Theresultisexpressedasafunction,givingthenumberofoperationsintermsofthesizeoftheinstance.Thismeasureisnotaspreciseasabenchmark,butmuchmoreusefulforansweringthekindofquestionsthatcommonlyarise:Iwanttosolveaproblemtwiceasbig.Howlongwillthattakeme?Wecanaffordtobuyamachinetwiceasfast?Whatsizeofproblemcanwesolveinthesametime?Theanswerstoquestionslikethisdependonthecomplexityofthealgorithm.DifferentinstancesofthesamesizeWehaveassumedthatthealgorithmtakesthesameamountoftimeoneveryinstanceofthesamesize.Butthisisalmostnevertrue,andsowemustdecidewhethertodobestcase,worstcaseoraveragecaseanalysis.Inbestcaseanalysisweconsiderthetimetakenbythealgorithmtobethetimeittakesonthebestinputofsizen.Inworstcaseanalysisweconsiderthetimetakenbythealgorithmtobethetimeittakesontheworstinputofsizen.Inaveragecaseanalysisweconsiderthetimetakenbythealgorithmtobetheaverageofthetimestakenoninputsofsizen.Anexample-InsertionsortLines2-7willbeexecutedntimes,lines4-5willbeexecuteduptojtimesforj=1ton.AsymptoticnotationsBig-Onotation:Itdefinesanasymptoticupperboundforafunctionf(n).
Definition:Afunctionf(n)issaidtobeO(g(n))ifthereareconstantscandn0suchthat
f(n)≤cg(n),?n≥n0.Big-Omeganotation():Itdefinesanasymptoticlowerboundforafunctionf(n).Big-Thetanotation:Itdefinesanasymptoticupperandlowerboundforafunctionf(n). Definition:Afunctionf(n)issaidtobe(g(n))ifthereareconstantsc1,c2andn0suchthat 0≤c1g(n)≤f(n)≤c2g(n),?n≥n0.Ifwesaythatf(n)=(n2)thenweareimplyingthatf(n)isapproximatelyproportionalton2forlargevaluesofn.Asymptoticnotationsf(n)=(
g(n))nn0c1g(n)c2g(n)f(n)Thereexistpositiveconstantsc1andc2suchthatthereisapositiveconstantn0suchthat…f(n)=O(
g(n))nn0f(n)cg(n)Thereexistpositiveconstantscsuchthatthereisapositiveconstantn0suchthat…f(n)=(
g(n))nn0cg(n)f(n)Thereexistpositiveconstantscsuchthatthereisapositiveconstantn0suchthat…OrderofgrowthAsymptoticnotations:,O,,o,.Theconstantcoefficient(s)areignored.Lowerorderitem(s)areignored,justkeepthehighestorderitem.Therateofgrowth,ortheorderofgrowth,possessesthehighestsignificance.Theinsertionsortrunsin(n2).f(n)=(g(n))actuallymeans:f(n)
(g(n))。Typicalorderofgrowth:O(1),O(logn),O(n),O(n),O(nlogn),O(n2),O(n3),O(2n),O(n!).What’sthecomplexityofeachFibalgorithm?ApproximationforfactorialsStirling’sapproximation
Arithmetic
operationO(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))。Orderofgrowth2nn2nlognnlognfnAnasymptoticallybettersortingalgorithm:Merge-sortAnalysisoftheMerge-sortalgorithmDescribedbyrecursiveequationSupposeT(n)istherunningtimeonaproblemofsizen.T(n)=(1)ifnnc
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東省泰安一中、寧陽一中2025年高三第一次模擬考試化學(xué)試卷含解析
- 護(hù)士臨床工作總結(jié)
- 五項管理主題班會
- 北京豐臺區(qū)北京第十二中學(xué)2025屆高三第六次模擬考試化學(xué)試卷含解析
- 學(xué)院年度工作總結(jié)報告
- 2023年廣東省廣州市第27屆WMO小學(xué)二年級上學(xué)期奧林匹克數(shù)學(xué)競賽復(fù)賽試卷
- 2025屆云南省臨滄市高三第六次模擬考試化學(xué)試卷含解析
- 廣西壯族自治區(qū)柳州市柳州高級中學(xué)2025年高三下學(xué)期第六次檢測化學(xué)試卷含解析
- 小班幼兒勞動教研工作總結(jié)
- 全肺切除術(shù)后護(hù)理診斷
- 湖北省部分名校2024-2025學(xué)年高二下學(xué)期3月聯(lián)考物理試卷(A)(原卷版+解析版)
- 第5課+光色交匯+課件-2024-2025學(xué)年浙人美版(2024)初中美術(shù)七年級下冊
- (2025)政工職稱考試題庫(附參考答案)
- 臨沂考科目一試題及答案
- 2025年初級等保測評試題及答案
- 真需求-打開商業(yè)世界的萬能鑰匙
- 執(zhí)行款收款賬戶確認(rèn)書模版
- 機組DEH、ETS、FSSS、MEH、METS系統(tǒng)邏輯
- 教練技術(shù)一階段講義
- 乙烯裂解爐焊接施工工藝及驗收規(guī)程
- 鋼格柵板安裝方案
評論
0/150
提交評論