CMSC 132 Object Oriented Programming II Algorithmic Complexity II Department of Computer Science University of Maryland College Park 1 Overview Critical sections Comparing complexity Types of complexity analysis 2 Analyzing Algorithms Goal Find asymptotic complexity of algorithm Approach Ignore less frequently executed parts of algorithm Find critical section of algorithm Determine how many times critical section is executed as function of problem size 3 Critical Section of Algorithm Heart of algorithm Dominates overall execution time Characteristics Operation central to functioning of program Contained inside deeply nested loops Executed as often as any other part of algorithm Sources Loops Recursion 4 Critical Section Example 1 Code for input size n 1 A 2 for int i 0 i n i B 3 4 C critical section Code execution A once B n times C once Time 1 n 1 O n 5 Critical Section Example 2 Code for input size n 1 A 2 for int i 0 i n i B for int j 0 j n j C 3 4 5 critical section 6 D Code execution A once B n times C n2 times D once Time 1 n n2 1 O n2 6 Critical Section Example 3 Code for input size n 1 A 2 for int i 0 i n i 3 4 for int j i 1 j n j B Code execution critical section A once B n n 1 times Time 1 n2 O n2 7 Critical Section Example 4 Code for input size n 1 A 2 for int i 0 i n i 3 4 for int j 0 j 10000 j B Code execution critical section A once B 10000 n times Time 1 10000 n O n 8 Critical Section Example 5 Code for input size n 1 for int i 0 i n i 2 3 4 5 6 for int j 0 j n j A for int i 0 i n i for int j 0 j n j B critical sections Code execution A n2 times B n2 times Time n2 n2 O n2 9 Critical Section Example 6 Code for input size n 1 i 1 2 while i n A i 2 i 3 4 critical section 5 B Code execution A log n times B 1 times Time log n 1 O log n 10 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 2 times Time 1 1 Time n 2 Time n 2 1 11 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 12 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 13 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 14 Comparing Complexity Compare two algorithms f n g n Determine which increases at faster rate As problem size n increases Can compare ratio f n lim If f is larger n g n If 0 g is larger If constant then same complexity 15 Complexity Comparison Examples log n vs n f n lim n g n log n lim n n 0 1 001n vs n1000 f n lim n g n n 1 001 lim n n1000 Not clear use L Hopital s Rule 16 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 17 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 18 Additional Complexity Categories Name Description P NP PSPACE EXPSPACE Decidable Undecidable Deterministic polynomial time Nondeterministic polynomial time Polynomial space Exponential space Can be solved by finite algorithm Not solvable by finite algorithm If a problem has a algorithm that solves it in time X then the problem is said to be in X e g matrix multiplication is in P 19 Why do we care If a problem can t be solved with in P time then no algorithm can solve all cases exactly in a reasonable amount of time But there might be an algorithm that always quickly gives close approximations Or an algorithm that gives quick exact answers for the cases we care about Issues such as PSPACE vs EXPSPACE are interesting theoretical issues and sometime provide practice insight 20 NP Time Algorithms Two ways of thinking about it First way Given a problem and a potential answer can we verify that the answer is correct in polynomial time Second way Whenever the algorithm wants it can clone itself in two If either clone finds an answer the entire system produces an answer 21 Graph 3 coloring Given a graph vertices and undirected edges Can you find a way to color each vertex either blue red or green Such that no two vertices connected by an edge have the same color 22 Some graphs are hard 23 3 coloring a graph is in NP There exist NP algorithms to 3 color a graph Guess a 3 coloring Verify that the coloring is valid Easy to do in O n time No one knows if there exists a polynomial time algorithm to find a 3 coloring for an arbitrary graph If you come up with one even one that runs in time O n100 you win one million dollars Seriously 24 NP Time Algorithm Many interesting problems are solvable with an NP algorithm but not known to be solvable with a P algorithm 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 25 NP Complete problems Some problems are NP complete They are in NP And if a polynomial time algorithm existed for the program Then every single last problem in NP could be solved in polynomial time Almost all problems that are in NP but are not known to be in P are NP complete But not all 26 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 for some problem in NP The expected answer The most important open problem in CS 1 …
View Full Document
Unlocking...