Analysis of AlgorithmsMathematical Analysis of AlgorithmsExamplesUseful ToolsAlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAlgorithm AnalysisSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Section 3.3 of [email protected] / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsIntroductionHow c an we say that one algorithm performs better thananother?Quantify the resources required to execute:TimeMemoryI/Ocircuits, power, etcTime is not merely CPU clock cycles, we want to studyalgorithms independent or implementations, platforms, andhardware. We need an objective point of reference. For that,we measure time by “the number of operations as a function ofan algorithm’s input size.”2 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsInput SizeFor a given problem, we characterize the input size, n,appropriately:Sorting – The number of items to be sortedGraphs – The number of vertices and/or edgesNumerical – The number of bits neede d to represent anumberThe choice of an input size greatly depends on the ele me ntaryoperation; the most relevant or important operation of analgorithm.ComparisonsAdditionsMultiplications3 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsOrders of GrowthSmall input sizes can usually be computed instantaneously,thus we are most interested in how an algorithm performs asn → ∞.Indeed, for small values of n, most s uch functions will be verysimilar in running time. Only for sufficiently large n dodifferences in running time become apparent. As n → ∞ thedifferences become more and more stark.4 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsIntractabilityProblems that we can solve (today) only with exponential orsuper-exponential time algorithms are said to be (likely)intractable. That is, though they may be solved in a reasonableamount of time for small n, for large n, there is (likely) no hopeof efficient execution. It may take millions or billions of years.Tractable problems are problems that have efficient (read:polynomial) algorithms to solve them. Polynomial order ofmagnitude usually means there exists a polynomial p(n ) = nkfor some c onstant k that always bounds the order of growth.More on asymptotics in the next slide set.Intractable problems may need to be solved usingapproximation or randomized algorithms.5 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsWorst, Best, and Average CaseSome algorithms perform differently on various inputs of similarsize. It is sometimes helpful to consider the Worst-Case,Best-Case, and Average-Case efficiencies of algorithms. Forexample, say we want to search an array A of size n for a givenvalue K.Worst-Case: K 6∈ A then we must search every item (ncomparisons)Best-Case: K is the first item that we check, so only onecomparison6 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAverage-CaseSince any worth-while algorithm will be used quite extensively,the average running-time is arguably the best measure of itsperformance (if the worst-case is not frequently encountered).For searching an array, and assuming that p is the probabilityof a successful search, we have:Cavg(n) =p + 2p + . . . + ip + . . . npn+ n(1 − p)=pn(1 + 2 + . . . + i + . . . + n) + n(1 − p)=pn(n(n + 1)2+ n(1 − p)If p = 1 (search succeeds), Cavg(n) =n+12≈ .5n.If p = 0 (search fails), Cavg(n) = n.A more intuitive interpretation is that the algorithm mustexamine, on average, half of all elements in A.7 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAverage-CaseAverage-Case analysis of algorithms is important in a practicalsense. Often, Cavgand Cworsthave the same order ofmagnitude and thus, from a theoretical point of view, are nodifferent from each other. Practical implementations, however,require a real-world examination.8 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsMathematical Analysis of AlgorithmsAfter developing pseudo-code for an algorithm, we wish toanalyze its efficiency as a function of the size of the input, n interms of how many times the elementary operation isperformed. Here is a general strategy:1Decide on a parameter(s) for the input, n.2Identify the basic operation.3Evaluate if the elementary operation depends only on n(otherwise evaluate best, worst, and average-caseseparately.4Set up a summation corresponding to the number ofelementary operations5Simplify the equation to get as simple of a function f(n)as possible.9 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAnalysis ExamplesExample IConsider the following code.Algorithm (UniqueElements)Input : Integer array A of size nOutput : true if all elements a ∈ A are distinctfor i = 1, . . . , n − 1 do1for j = i + 1, . . . , n do2if ai= ajthen3return false4end5end6end7return true810 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAnalysis ExampleExample I - AnalysisFor this algorithm, what isThe elementary operation?Input Size?Does the elementary operation depend only on n?The outer for-loop is run n − 1 times. More formally, itcontributesn−1Xi=111 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAnalysis ExampleExample I - AnalysisFor this algorithm, what isThe elementary operation?Input Size?Does the elementary operation depend only on n?The outer for-loop is run n − 1 times. More formally, itcontributesn−1Xi=111 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAnalysis ExampleExample I - AnalysisThe inner for-loop depends on the outer for-loop, so itcontributesnXj=i+1We obse rve t hat the ele mentary operation is exe cuted onc e ineach iteration, thus we haveCworst(n) =n−1Xi=1nXj=i+11 =n(n − 1)212 / 18AlgorithmAnalysisCSE235Analysis ofAlgorithmsMathematicalAnalysis ofAlgorithmsExamplesUseful ToolsAnalysis ExampleExample I - AnalysisThe inner for-loop depends on the outer for-loop, so itcontributesnXj=i+1We obse rve
View Full Document
Unlocking...