Algorithmic Complexity Fawzi Emad Chau Wen Tseng Department of Computer Science University of Maryland College Park Where We Are OO software development So far Algorithms data structures Asymptotic analysis Data structures Linear Hierarchical Unstructured Advanced Java Collections Threads Coming up Algorithm Efficiency Efficiency Amount of resources used by algorithm Time space Measuring efficiency Benchmarking Asymptotic analysis Benchmarking Approach Pick some desired inputs Actually run implementation of algorithm Measure time space needed Industry benchmarks SPEC CPU performance MySQL Database applications WinStone Windows PC applications MediaBench Multimedia applications Linpack Numerical scientific applications Benchmarking Advantages Precise information for given configuration Implementation hardware inputs Disadvantages Affected by configuration Data sets usually too small Hardware Software Affected by special cases biased inputs Does not measure intrinsic efficiency Asymptotic Analysis Approach Mathematically analyze efficiency Calculate time as function of input size n T O f n T is on the order of f n Big O notation Advantages Measures intrinsic efficiency Dominates efficiency for large input sizes Search Example Number guessing game Pick a number between 1 n Guess a number Answer correct too high too low Repeat guesses until correct number guessed Linear Search Algorithm Algorithm 1 Guess number 1 2 If incorrect increment guess by 1 3 Repeat until correct Example Given number between 1 100 Pick 20 Guess sequence 1 2 3 4 20 Required 20 guesses Linear Search Algorithm Analysis of of guesses needed for 1 n If number 1 requires 1 guess If number n requires n guesses On average needs n 2 guesses Time O n Linear time Binary Search Algorithm Algorithm 1 Set to n 4 2 Guess number n 2 3 If too large guess number 4 If too small guess number 5 Reduce by 6 Repeat until correct Binary Search Algorithm Example Given number between 1 100 Pick 20 Guesses 50 25 Answer too large subtract 25 12 Answer too large subtract 13 6 Answer too small add 19 3 Answer too small add 22 1 Answer too large subtract 21 1 Answer too large subtract 20 Required 7 guesses Binary Search Algorithm Analysis of of guesses needed for 1 n If number n 2 requires 1 guess If number 1 requires log2 n guesses If number n requires log2 n guesses On average needs log2 n guesses Time O log2 n Log time Search Comparison For number between 1 100 Simple algorithm 50 steps Binary search algorithm log2 n 7 steps For number between 1 100 000 Simple algorithm 50 000 steps Binary search algorithm log2 n 77 steps Binary search is much more efficient Asymptotic Complexity Comparing two linear functions Size Running Time n 2 4n 3 64 32 259 128 64 515 256 128 1027 512 256 2051 Asymptotic Complexity Comparing two functions n 2 and 4n 3 behave similarly Run time roughly doubles as input size doubles Run time increases linearly with input size For large values of n Time 2n Time n approaches exactly 2 Both are O n programs Asymptotic Complexity Comparing two log functions Size Running Time log2 n 5 log2 n 3 64 6 33 128 7 38 256 8 43 512 9 48 Asymptotic Complexity Comparing two functions log2 n and 5 log2 n 3 behave similarly Run time roughly increases by constant as input size doubles Run time increases logarithmically with input size For large values of n Time 2n Time n approaches constant Base of logarithm does not matter Simply a multiplicative factor logaN logbN logba Both are O log n programs Asymptotic Complexity Comparing two quadratic functions Size Running Time n2 2 n2 8 2 4 16 4 16 40 8 64 132 16 256 520 Asymptotic Complexity Comparing two functions n2 and 2 n2 8 behave similarly Run time roughly increases by 4 as input size doubles Run time increases quadratically with input size For large values of n Time 2n Time n approaches 4 Both are O n2 programs Observations Big O categories O log n O n O n2 For large values of n Any O log n algorithm is faster than O n Any O n algorithm is faster than O n2 Asymptotic complexity is fundamental measure of efficiency Comparison of Complexity
View Full Document
Unlocking...