Algorithmic Complexity 3 Fawzi Emad Chau Wen Tseng Department of Computer Science University of Maryland College Park Overview Recurrence relations Complexity categories Comparing complexity Types of complexity analysis 1 Critical Section Example 7 Code for input size n 1 DoWork int n 2 3 4 5 6 if n 1 A else DoWork n 2 DoWork n 2 critical sections Code execution A 1 times DoWork n 2 Time 1 1 2 times Time n 2 Time n 2 1 Recursive Algorithms Definition An algorithm that calls itself Components of a recursive algorithm 1 Base cases Computation with no recursion 2 Recursive cases Recursive calls Combining recursive results 2 Recursive Algorithm Example Code for input size n 1 DoWork int n 2 3 4 5 6 if n 1 A else DoWork n 2 DoWork n 2 base case recursive cases Recurrence Relations Definition Value of a function at a point is given in terms of its value at other points Examples T n T n 1 k T n T n 1 n T n T n 1 T n 2 T n T n 2 k T n 2 T n 2 k 3 Recurrence Relations Base case Value of function at some specified points Also called boundary values boundary conditions Base case example T 1 0 T 1 1 T 2 1 T 2 k Solving Recurrence Equations Back substitution iteration method Iteratively substitute recurrence into formula Example T 1 5 T n T n 1 1 T n 2 1 1 T n 3 1 1 1 T n 4 1 1 1 1 T 1 1 1 5 1 1 n 4 4 Example Recurrence Solutions Examples T n T n 1 k T n T n 1 n T n T n 1 T n 2 T n T n 2 k T n 2 T n 2 k T n 2 T n 1 k O n O n O n O log n O n O 2 2 n Many additional issues solution methods Take CMSC 351 Introduction to Algorithms Asymptotic Complexity Categories Complexity O 1 O log n O n O n log n O n2 O n3 O nk O kn Name Example Constant Logarithmic Linear N log N Quadratic Cubic Polynomial Exponential Array access Binary search Largest element Optimal sort 2D Matrix addition 2D Matrix multiply Linear programming Integer programming From smallest to largest For size n constant k 1 5 Complexity Category Example 300 of Solution Steps 250 2 n n 2 nlog n n log n 200 150 100 50 0 1 2 3 4 5 6 7 Problem Size Complexity Category Example of Solution Steps 1000 2 n n 2 nlog n n log n 100 10 1 1 2 3 4 5 6 7 Problem Size 6 Calculating Asymptotic Complexity As n increases Highest complexity term dominates Can ignore lower complexity terms Examples O n O nlog n O n2 O n3 O 2n 2 n 100 n log n 10 n n2 100 n n3 100 n2 1 100 2n 100 n4 Complexity Examples 2n 100 O n n nlog n 2 n 100 800000 700000 600000 500000 400000 300000 200000 100000 31602 16111 8208 4175 2118 1068 533 260 120 49 13 0 7 Complexity Examples n log n 10 n O nlog n n nlog n 1 2 n log n 10 n 800000 700000 600000 500000 400000 300000 200000 100000 44252 22565 11501 5855 2975 1506 756 373 178 79 28 2 0 Complexity Examples n2 100 n O n2 nlog n n 2 1 2 n 2 100 n 800000 700000 600000 500000 400000 300000 200000 100000 44252 22565 11501 5855 2975 1506 756 373 178 79 28 2 0 8 Complexity Examples 1 100 2n 100 n4 n 2 O 2n n 4 2 n 1 100 2 n 100 n 4 79 120 178 260 373 533 756 1E 150 1E 135 1E 120 1E 105 1E 90 1E 75 1E 60 1E 45 1E 30 1E 15 1 2 13 28 49 Comparing Complexity Compare two algorithms f n g n Determine which increases at faster rate As problem size n increases Can compare ratio If f is larger f n lim n g n If 0 g is larger If constant then same complexity 9 Complexity Comparison Examples log n vs n f n log n lim n g n lim n n 0 1 001n vs n1000 n lim 1 001 n 1000 f n lim n g n n Not clear use L Hopital s Rule L Hopital s Rule If ratio is indeterminate 0 0 or Ratio of derivatives computes same value f n lim n g n f n lim n g n Can simplify ratio by repeatedly taking derivatives of numerator denominator 10 Using L Hopital s Rule 1 001n vs n1000 n lim 1 001 n 1000 f n lim n g n n n 1 001n 1 lim n 1000 n999 n 2 lim n n 1 1 001 n 1000 999 n998 Additional Complexity Measures Upper bound Big O Represents upper bound on steps Lower bound Big Omega Represents lower bound on steps Combined bound Big Theta Represents combined upper lower bound on steps Best possible asymptotic solution 11 2D Matrix Multiplication Example Problem C A B Lower bound n2 Required to examine 2D matrix Upper bounds O n3 O n2 807 O n2 376 Basic algorithm Strassen s algorithm 1969 Coppersmith Winograd 1987 Improvements still possible open problem Since upper lower bounds do not match Additional Complexity Categories Name Description NP PSPACE EXPSPACE Decidable Undecidable Nondeterministic polynomial time NP Polynomial space Exponential space Can be solved by finite algorithm Not solvable by finite algorithm Mostly of academic interest only Quadratic algorithms usually too slow for large data Use fast heuristics to provide non optimal solutions 12 NP Time Algorithm Polynomial solution possible If make correct guesses on how to proceed Required for many fundamental problems Boolean satisfiability Traveling salesman problem TLP Bin packing Key to solving many optimization problems Most efficient trip routes Most efficient schedule for employees Most efficient usage of resources NP Time Algorithm Properties of NP Can be solved with exponential time Not proven to require exponential time Currently solve using heuristics NP complete problems Representative of all NP problems Solution can be used to solve any NP problem Examples Boolean satisfiability Traveling salesman 13 P NP Are NP problems solvable in polynomial time Prove P NP Show polynomial time solution exists for any NP complete problem Prove P NP Show no polynomial time solution possible The expected answer Important open problem in computer science 1 million prize offered by Clay Math Institute Algorithmic Complexity Summary Asymptotic complexity Fundamental measure of efficiency Independent of implementation computer platform Learned how to Examine program Find critical sections Calculate complexity of algorithm Compare complexity 14
View Full Document
Unlocking...