Algorithmic Complexity 2OverviewBig-O NotationFormal Definition of Big-OBig-O ExamplesSlide 6Types of Case AnalysisSlide 8Slide 9Slide 10Approaches to Average CaseQuicksort ExampleSlide 13Amortization ExampleSlide 15Slide 16Analyzing AlgorithmsCritical Section of AlgorithmCritical Section Example 1Slide 20Critical Section Example 2Slide 22Critical Section Example 3Slide 24Critical Section Example 4Slide 26Critical Section Example 5Slide 28Critical Section Example 6Slide 30Critical Section Example 7Slide 32Algorithmic Complexity 2Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewBig-O notationAnalysis casesCritical sectionBig-O NotationRepresentsUpper bound on number of steps in algorithmIntrinsic efficiency of algorithm for large inputsf(n)O(…)input size# stepsFormal Definition of Big-O Function f(n) is ( g(n) ) ifFor some positive constants M, N0M g(N0) f(n), for all n N0IntuitivelyFor some coefficient M & all data sizes N0M g(n) is always greater than f(n)Big-O Examples5n + 1000 O(n)Select M = 6, N0 = 1000For n 10006n 5n+1000 is always trueExample for n = 10006000 5000 +1000Big-O Examples2n2 + 10n + 1000 O(n2)Select M = 4, N0 = 100For n 1004n2 2n2 + 10n + 1000 is always trueExample for n = 10040000 20000 + 1000 + 1000Types of Case AnalysisCan analyze different types (cases) of algorithm behaviorTypes of analysisBest caseWorst caseAverage caseTypes of Case AnalysisBest caseSmallest number of steps requiredNot very useful Example Find item in first place checkedTypes of Case AnalysisWorst caseLargest number of steps requiredUseful for upper bound on worst performanceReal-time applications (e.g., multimedia)Quality of service guaranteeExample Find item in last place checkedTypes of Case AnalysisAverage caseNumber of steps required for “typical” caseMost useful metric in practiceDifferent approaches1. Average case2. Expected case3. AmortizedApproaches to Average Case1. Average caseAverage over all possible inputsAssumes uniform probability distribution2. Expected caseWeighted average over all inputsWeighted by likelihood of input3. AmortizedExamine common sequence of operationsAverage number of steps over sequenceQuicksort ExampleQuicksortOne of the fastest comparison sortsFrequently used in practiceQuicksort algorithmPick pivot value from listPartition list into values smaller & bigger than pivotRecursively sort both listsQuicksort ExampleQuicksort propertiesAverage case = O(nlog(n))Worst case = O(n2)Pivot smallest / largest value in listPicking from front of nearly sorted listCan avoid worst-case behaviorAttempt to select random pivot valueAmortization ExampleAdding numbers to end of array of size kIf array is full, allocate new arrayAllocation cost is O(size of new array)Copy over contents of existing arrayTwo approachesNon-amortizedIf array is full, allocate new array of size k+1AmortizedIf array is full, allocate new array of size 2kCompare their allocation costAmortization ExampleNon-amortized approachAllocation cost as table grows from 1..nTotal cost ½ (n+1)2Case analysisBest case allocation cost = kWorse case allocation cost = kAverage case allocation cost = k = n/2Size (k) 1 2 3 4 5 6 7 8Cost 1 2 3 4 5 6 7 8Amortization ExampleAmortized approachAllocation cost as table grows from 1..nTotal cost 2 (n – 1)Case analysis Best case allocation cost = 0Worse case allocation cost = 2(k – 1)Average case allocation cost = 2Worse case takes more steps, but faster overallSize (k) 1 2 3 4 5 6 7 8Cost 2 0 4 0 8 0 0 0Analyzing AlgorithmsGoalFind asymptotic complexity of algorithmApproachIgnore less frequently executed parts of algorithmFind critical section of algorithmDetermine how many times critical section is executed as function of problem sizeCritical Section of AlgorithmHeart of algorithmDominates overall execution timeCharacteristicsOperation central to functioning of programContained inside deeply nested loopsExecuted as often as any other part of algorithmSourcesLoopsRecursionCritical Section Example 1Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. B4. CCode executionA B C Time Critical Section Example 1Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. B4. CCode executionA onceB n timesC onceTime 1 + n + 1 = O(n)critical sectionCritical Section Example 2Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. B4. for (int j = 0; j < n; j++)5. C6. DCode executionA B Time C D Critical Section Example 2Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. B4. for (int j = 0; j < n; j++)5. C6. DCode executionA onceB n timesTime 1 + n + n2 + 1 = O(n2)critical sectionC n2 timesD onceCritical Section Example 3Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. for (int j = i+1; j < n; j++)4. BCode executionA B Time Critical Section Example 3Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. for (int j = i+1; j < n; j++)4. BCode executionA onceB ½ n (n-1) timesTime 1 + ½ n2 = O(n2)critical sectionCritical Section Example 4Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. for (int j = 0; j < 10000; j++)4. BCode executionA B Time Critical Section Example 4Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. for (int j = 0; j < 10000; j++)4. BCode executionA onceB 10000 n timesTime 1 + 10000 n = O(n)critical sectionCritical Section Example 5Code (for input size n)1. for (int i = 0; i < n; i++)2. for (int j = 0; j < n; j++)3. A4. for (int i = 0; i < n; i++)5. for (int j = 0; j < n; j++)6. BCode executionA B Time Critical Section Example 5Code (for input size n)1. for (int i = 0; i < n; i++)2. for (int j = 0; j < n; j++)3. A4. for (int i = 0; i < n; i++)5. for (int j = 0; j < n; j++)6. BCode executionA n2 timesB n2 timesTime n2 + n2 = O(n2)critical sectionsCritical Section Example 6Code (for input size n)1. i = 12. while (i < n)3. A4. i = 2 i5. BCode executionA B Time Critical Section Example 6Code (for input size n)1. i = 12. while (i < n)3. A4. i = 2 i5. BCode executionA log(n) timesB 1 timesTime log(n) + 1 = O( log(n) )critical sectionCritical Section Example 7Code (for input size n)1. DoWork (int n)2. if (n == 1)3. A4. else5.
View Full Document
Unlocking...