《第01章算法分析Analysis.ppt》由会员分享，可在线阅读，更多相关《第01章算法分析Analysis.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第01章算法分析Analysis Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望Running Time(1.1)wMost algorithms transform input objects into output objects.wThe running time of an algorithm typically grows with the input size.wAverage case time is often difficult to deter
2、mine.wWe focus on the worst case running time.nEasier to analyzenCrucial to applications such as games,finance and robotics2Analysis of AlgorithmsExperimental Studies(1.6)wWrite a program implementing the algorithmwRun the program with inputs of varying size and compositionwUse a method like System.
3、currentTimeMillis()to get an accurate measure of the actual running timewPlot the results3Analysis of AlgorithmsLimitations of ExperimentsIt is necessary to implement the algorithm,which may be difficultResults may not be indicative of the running time on other inputs not included in the experiment.
4、In order to compare two algorithms,the same hardware and software environments must be used4Analysis of AlgorithmsTheoretical AnalysisUses a high-level description of the algorithm instead of an implementationCharacterizes running time as a function of the input size,n.Takes into account all possibl
5、e inputsAllows us to evaluate the speed of an algorithm independent of the hardware/software environment5Analysis of AlgorithmsPseudocode(1.1)High-level description of an algorithmMore structured than English proseLess detailed than a programPreferred notation for describing algorithmsHides program
6、design issues Algorithm arrayMax(A,n)Input array A of n integersOutput maximum element of AcurrentMax A0for i 1 to n 1 doif Ai currentMax thencurrentMax Aireturn currentMax Example:find max element of an array6Analysis of AlgorithmsPseudocode DetailsControl flownif then else nwhile do nrepeat until
7、nfor do nIndentation replaces braces Method declarationAlgorithm method(arg,arg)Input Output Method callvar.method(arg,arg)Return valuereturn expressionExpressionsAssignment(like in Java)Equality testing(like in Java)n2Superscripts and other mathematical formatting allowed7Analysis of AlgorithmsThe
8、Random Access Machine(RAM)ModelwA CPUwAn potentially unbounded bank of memory cells,each of which can hold an arbitrary number or character012wMemory cells are numbered and accessing any cell in memory takes unit time.8Analysis of AlgorithmsPrimitive OperationswBasic computations performed by an alg
9、orithmwIdentifiable in pseudocodewLargely independent from the programming languagewExact definition not important(we will see why later)wAssumed to take a constant amount of time in the RAM modelwExamples:nEvaluating an expressionnAssigning a value to a variablenIndexing into an arraynCalling a met
10、hodnReturning from a method9Analysis of AlgorithmsCounting Primitive Operations(1.1)wBy inspecting the pseudocode,we can determine the maximum number of primitive operations executed by an algorithm,as a function of the input sizeAlgorithm arrayMax(A,n)#operationscurrentMax A0 2for i 1 to n 1 do 2+n
11、if Ai currentMax then2(n 1)currentMax Ai2(n 1)increment counter i 2(n 1)return currentMax 1Total 7n 110Analysis of AlgorithmsEstimating Running TimewAlgorithm arrayMax executes 7n 1 primitive operations in the worst case.Define:a=Time taken by the fastest primitive operationb=Time taken by the slowe
12、st primitive operationwLet T(n)be worst-case time of arrayMax.Thena(7n 1)T(n)b(7n 1)wHence,the running time T(n)is bounded by two linear functions11Analysis of AlgorithmsGrowth Rate of Running TimeChanging the hardware/software environment nAffects T(n)by a constant factor,butnDoes not alter the gro
13、wth rate of T(n)The linear growth rate of the running time T(n)is an intrinsic property of algorithm arrayMax12Analysis of AlgorithmsGrowth RateswGrowth rates of functions:nLinear nnQuadratic n2nCubic n3wIn a log-log chart,the slope of the line corresponds to the growth rate of the function13Analysi
14、s of AlgorithmsConstant FactorsThe growth rate is not affected bynconstant factors or nlower-order termsExamplesn102n+105 is a linear functionn105n2+108n is a quadratic function14Analysis of AlgorithmsBig-Oh Notation(1.2)Given functions f(n)and g(n),we say that f(n)is O(g(n)if there are positive con
15、stantsc and n0 such thatf(n)cg(n)for n n0Example:2n+10 is O(n)n2n+10 cnn(c 2)n 10nn 10/(c 2)nPick c 3 and n0 1015Analysis of AlgorithmsBig-Oh ExampleExample:the function n2 is not O(n)nn2 cnnn cnThe above inequality cannot be satisfied since c must be a constant 16Analysis of AlgorithmsMore Big-Oh E
16、xamplesn7n-27n-2 is O(n)need c 0 and n0 1 such that 7n-2 cn for n n0this is true for c=7 and n0=1n3n3+20n2+53n3+20n2+5 is O(n3)need c 0 and n0 1 such that 3n3+20n2+5 cn3 for n n0this is true for c=4 and n0=21n3 log n+log log n3 log n+log log n is O(log n)need c 0 and n0 1 such that 3 log n+log log n
17、 clog n for n n0this is true for c=4 and n0=217Analysis of AlgorithmsBig-Oh and Growth RateThe big-Oh notation gives an upper bound on the growth rate of a functionThe statement“f(n)is O(g(n)”means that the growth rate of f(n)is no more than the growth rate of g(n)We can use the big-Oh notation to r
18、ank functions according to their growth ratef(n)is O(g(n)g(n)is O(f(n)g(n)grows moreYesNof(n)grows moreNoYesSame growthYesYes18Analysis of AlgorithmsBig-Oh RulesIf is f(n)a polynomial of degree d,then f(n)is O(nd),i.e.,1.Drop lower-order terms2.Drop constant factorsUse the smallest possible class of
19、 functionsnSay“2n is O(n)”instead of“2n is O(n2)”Use the simplest expression of the classnSay“3n+5 is O(n)”instead of“3n+5 is O(3n)”19Analysis of AlgorithmsAsymptotic Algorithm AnalysisThe asymptotic analysis of an algorithm determines the running time in big-Oh notationTo perform the asymptotic ana
20、lysisnWe find the worst-case number of primitive operations executed as a function of the input sizenWe express this function with big-Oh notationExample:nWe determine that algorithm arrayMax executes at most 7n 1 primitive operationsnWe say that algorithm arrayMax“runs in O(n)time”Since constant fa
21、ctors and lower-order terms are eventually dropped anyhow,we can disregard them when counting primitive operations20Analysis of AlgorithmsComputing Prefix AveragesWe further illustrate asymptotic analysis with two algorithms for prefix averagesThe i-th prefix average of an array X is average of the
22、first(i+1)elements of X:Ai (X0+X1+Xi)/(i+1)Computing the array A of prefix averages of another array X has applications to financial analysis21Analysis of AlgorithmsPrefix Averages(Quadratic)The following algorithm computes prefix averages in quadratic time by applying the definitionAlgorithm prefix
23、Averages1(X,n)Input array X of n integersOutput array A of prefix averages of X#operations A new array of n integers nfor i 0 to n 1 do ns X0 nfor j 1 to i do 1+2+(n 1)s s+Xj 1+2+(n 1)Ai s/(i+1)nreturn A 122Analysis of AlgorithmsArithmetic ProgressionThe running time of prefixAverages1 isO(1+2+n)The
24、 sum of the first n integers is n(n+1)/2nThere is a simple visual proof of this factThus,algorithm prefixAverages1 runs in O(n2)time 23Analysis of AlgorithmsPrefix Averages(Linear)The following algorithm computes prefix averages in linear time by keeping a running sumAlgorithm prefixAverages2(X,n)In
25、put array X of n integersOutput array A of prefix averages of X#operationsA new array of n integersns 0 1for i 0 to n 1 dons s+XinAi s/(i+1)nreturn A 1Algorithm prefixAverages2 runs in O(n)time 24Analysis of Algorithmswproperties of logarithms:logb(xy)=logbx+logbylogb(x/y)=logbx-logbylogbxa=alogbxlo
26、gba=logxa/logxbwproperties of exponentials:a(b+c)=aba cabc=(ab)cab/ac=a(b-c)b=a logabbc=a c*logabSummations (Sec.1.3.1)Logarithms and Exponents(Sec.1.3.2)Proof techniques(Sec.1.3.3)Basic probability(Sec.1.3.4)Math you need to Review25Analysis of AlgorithmsRelatives of Big-Ohbig-Omeganf(n)is(g(n)if t
27、here is a constant c 0 and an integer constant n0 1 such that f(n)cg(n)for n n0big-Thetanf(n)is(g(n)if there are constants c 0 and c 0 and an integer constant n0 1 such that cg(n)f(n)cg(n)for n n0little-ohnf(n)is o(g(n)if,for any constant c 0,there is an integer constant n0 0 such that f(n)cg(n)for
28、n n0little-omeganf(n)is(g(n)if,for any constant c 0,there is an integer constant n0 0 such that f(n)cg(n)for n n026Analysis of AlgorithmsIntuition for Asymptotic NotationBig-Ohnf(n)is O(g(n)if f(n)is asymptotically less than or equal to g(n)big-Omeganf(n)is(g(n)if f(n)is asymptotically greater than
29、or equal to g(n)big-Thetanf(n)is(g(n)if f(n)is asymptotically equal to g(n)little-ohnf(n)is o(g(n)if f(n)is asymptotically strictly less than g(n)little-omeganf(n)is(g(n)if is asymptotically strictly greater than g(n)27Analysis of AlgorithmsExample Uses of the Relatives of Big-Ohf(n)is(g(n)if,for an
30、y constant c 0,there is an integer constant n0 0 such that f(n)cg(n)for n n0need 5n02 cn0 given c,the n0 that satifies this is n0 c/5 0n5n2 is (n)f(n)is(g(n)if there is a constant c 0 and an integer constant n0 1 such that f(n)cg(n)for n n0let c=1 and n0=1n5n2 is (n)f(n)is(g(n)if there is a constant c 0 and an integer constant n0 1 such that f(n)cg(n)for n n0let c=5 and n0=1n5n2 is (n2)28Analysis of Algorithms