Report

Algorithm Analysis 2P03 © Dave Bockus Acknowledgments to Mark Allen Weiss 2014 Data Structures & Algorithm Analysis in Java Strategies for Analyzing Code Rule 1-- FOR LOOPS: The running time of a FOR loop is at most the running time of the statements inside the FOR loop (including tests) times the number of iterations. Rule 2-- Nested Loops: The total running time of a statement inside a group of nested loops is the running time of the statements multiplied by the product of the sizes of all the loops. for (i=0; i < n; i++) Running time for (j=0; j < n; j++) nxn sum++; Strategies for Analyzing Code Cont... Rule 3-- Consecutive Statements: Statements simply add up, where the largest statement takes precedence. for (int i = 0; i < n; i++) Statements A sum++; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) Statements B sum++; • Total running time is determined by statement set B Strategies for Analyzing Code Cont... Rule 4-- If/Else: Running time of an IF/ELSE is never more than the running time of the test plus the larger of the running times of S1 and S2. If (condition) S1 Else S2 If (condition) for (int i = 0; i < n; i++) sum++; Else for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sum++; Worst case is condition + S2 = O(n2) Strategies for Analyzing Code Cont... • Loops where the problem N size is divided by some factor k is a logkN loop. for (int i = 0; i < n; i++){ n = n/3; sum++; } – Running time is log3N • or – Just O(log N) Strategies for Analyzing Code Cont... Analyze loops from the inside out. Recursion: Tail recursion is nothing more then a LOOP. PrintList (node ptr){ if (ptr != null) { print(ptr.data); PrintList(ptr.next); } } PrintList (node ptr){ while (ptr != null){ print(ptr.data); ptr = ptr.next; } } Other types of recursion may require recurrence relations to be defined. Partitioning a List Given a List: [3 7 2 4 6 1 5] Take first # or choose a pivot element Put everything less than this in a left sublist Put everything greater than this in a right sublist Keep doing this for each sublist E.g. The above partitions into: [2 1] 3 [ 4 6 7 5] Partitioning a List Cont… [3 7 2 4 6 1 i 1). While jth element > ith element, reduce j [3 7 2 4 6 1 i j 2). Swap the ith and jth elements [1 7 2 4 6 3 i j 5] j 5] 5] 3). While ith element <= jth element, increase i [1 7 2 4 6 3 5] i j 4). Swap the ith and jth elements [1 3 2 4 i 5). Repeat 1 to 4 until j=i 6 7 j 5] Partitioning a List Cont… Step 3 [3 i [3 i [1 i [1 Step 4 [1 Step 1 [1 Step 1 [1 Step 1 [1 Step 1 Step 2 Step 2 Step 3 Finished [1 [1 7 2 4 6 1 7 2 4 6 7 2 4 6 7 i 3 i 3 i 3 i 3 i 2 i 2 4 6 2 4 6 2 4 2 4 j 4 6 j 6 1 j 3 j 3 j 7 j 7 2] 3 i=j 2 j 3 j 5] j 5] 5] 5] 5] 5] 7 5] 6 7 5] 4 6 7 5] [4 6 7 5] Best Case for Quick Sort • Alternately we can use a recurrence relation LHS: with i elements – T(N) = T(i) + T(N – i – 1) + cN • So RHS: with N-i elements Number of comparison for pivot – constant time. – T(N) = 2T(N/2) + cN – T(N)/N = T(N/2)/(N/2) + c Multiply both sides by 1/N Best Case QS Continued ... • Cut list in ½ for each iteration until 1 element in partition – – – – T(N)/N = T(N/2)/(N/2) + c T(N/2)/(N/2)= T(N/4)/(N/4) + c T(N/4)/(N/4)= T(N/8)/(N/8) + c T(N/8)/(N/8)= T(N/16)/(N/16) + c • at some point – T(2)/(2)= T(1)/(1) + c Best Case QS Continued ... • If we add up all equations: – T(N) + T(N/2) … T(2) = T(N/2) … T(2) +T(1) + clgN N + N/2 + N/4 … 2 N/2 + N/4 …2+ 1 • Cancel out terms: – T(N) = T(1) + clgN N 1 – T(N) = NT(1) + cNlgN • T(1) is 1 so: – T(N) = N + cNlgN • so order NlgN Worst Case for QS Pivot – T(N) = T(N-1) +cN N>1 • Reducing the list by choosing the smallest – T(N-1) = T(N-2) + c(N-1) – T(N-2) = T(N-3) + c(N-2) • until – T(2) = T(1) +c(2) Worst Case for QS • Now add up all equations – T(N) + T(N-1) - T(1) = T(N-1) + c N – T(N) = T(1) + cN – T(N) = 1 + cN(N+1)/2 • or – T(N) = O(N2) Exercise: Bubble Sort • Determine the run time equation and complexity of bubble sort? for (i=1; i<=n; i++) for (j=1; j<n; j++) { {compare & swap} if (x[j] > x[j+1]) swap } The basic BS compares every element with every other element. Each time through the loop n elements are compared. Since we do this n times there are n x n or n2 comparisons. Runtime equation is f(n) = n2 with On2 complexity Exercise: Nexted Loops • Determine the run time equation and complexity of the following code? What is the value of sum if n = 20. for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) sum++; Exercise: Nexted Loops Cont…. • We must note that the inner loop will increase sum i times each time it executes. – So after 6 iterations of the inner loop, sum is 1 + 2 + 3 + 4 + 5 + 6, this happens to be the sum of n numbers: n = [n(n+1)]/2 if n = 20 then = 20(21)/2 = 210 Running the code n = 1 -- sum is n = 2 -- sum is n = 3 -- sum is n = 4 -- sum is n = 5 -- sum is n = 6 -- sum is n = 7 -- sum is n = 8 -- sum is n = 9 -- sum is n = 10 -- sum is 1 3 6 10 15 21 28 36 45 55 n = 11 -- sum is n = 12 -- sum is n = 13 -- sum is n = 14 -- sum is n = 15 -- sum is n = 16 -- sum is n = 17 -- sum is n = 18 -- sum is n = 19 -- sum is n = 20 -- sum is 66 78 91 105 120 136 153 171 190 210