Question? Leave a message!




ALGORITHM ANALYSIS

ALGORITHM ANALYSIS
2. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ Lecture slides by Kevin Wayne Copyright © 2005 PearsonAddison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Sep 8, 2013 6:19 AM2. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ SECTION 2.1A strikingly modern thought “ As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time ” — Charles Babbage (1864) how many times do you have to turn the crank Analytic Engine 3Brute force Brute force. For many nontrivial problems, there is a natural bruteforce search algorithm that checks every possible solution. n Typically takes 2 time or worse for inputs of size n. Unacceptable in practice. 4Polynomial running time Desirable scaling property. When the input size doubles, the algorithm should only slow down by some constant factor C. Def. An algorithm is polytime if the above scaling property holds. There exists constants c 0 and d 0 such that d choose C = 2 on every input of size n, its running time is bounded d by c n primitive computational steps. Cobham von Neumann Nash Gödel Edmonds Rabin (1964) (1953) (1955) (1956) (1965) (1966) 5Polynomial running time We say that an algorithm is efficient if has a polynomial running time. Justification. It really works in practice In practice, the polytime algorithms that people develop have low constants and low exponents. Breaking through the exponential barrier of brute force typically exposes some crucial structure of the problem. Exceptions. Some polytime algorithms do have high constants and/or exponents, and/or are useless in practice. Mapgraphs inpolynomialtime Mapgraphs inpolynomialtime MikkelThorup Department ofComputer Science,University ofCopenhagen MikkelThorup Universitetsparken1,DK2100Copenhagen East,Denmark 100 1 + 0.02 ln n Department ofComputer Science,University ofCopenhagen Q. Which would you prefer 20 n vs. n mthorupdiku.dk Universitetsparken1,DK2100Copenhagen East,Denmark mthorupdiku.dk Abstract Abstract Chen,Grigni,andPapadimitriou(WADS’97andSTOC’98) have introduced a modified notion of planarity, where two Chen,Grigni,andPapadimitriou(WADS’97andSTOC’98) faces areconsideredadjacent if they shareat least one point. have introduced a modified notion of planarity, where two The corresponding abstract graphs are called map graphs. faces areconsideredadjacent if they shareat least one point. Chenet.al. raisedthe questionofwhethermapgraphs canbe The corresponding abstract graphs are called map graphs. recognizedin polynomialtime. Theyshowedthat thedecision Figure 1. Large cliques inmaps Chenet.al. raisedthe questionofwhethermapgraphs canbe problem is in NP and presenteda polynomial time algorithm recognizedin polynomialtime. Theyshowedthat thedecision Figure 1. Large cliques inmaps forthespecialcasewhereweallowatmost4facestointersect problem is in NP and presenteda polynomial time algorithm addition, the hamantach may have at most two triangle faces inany point—if only3 areallowedtointersectin apoint, we forthespecialcasewhereweallowatmost4facestointersect touching all three corners. In 5 there is a classification of getthe usualplanar graphs. addition, the hamantach may have at most two triangle faces inany point—if only3 areallowedtointersectin apoint, we allthedifferenttypesoflargecliquesinmaps. Chenet.al.5 Chenet.al.conjecturedthatmapgraphscanberecognized touching all three corners. In 5 there is a classification of getthe usualplanar graphs. showed that recognizing map graphs is in NP, hence that the inpolynomialtime,andinthispaper,theirconjectureissettled allthedifferenttypesoflargecliquesinmaps. Chenet.al.5 Chenet.al.conjecturedthatmapgraphscanberecognized recognitioncanbe doneinsinglyexponentialtime. However, affirmatively. showed that recognizing map graphs is in NP, hence that the inpolynomialtime,andinthispaper,theirconjectureissettled theyconjecturedthat,infact,mapgraphscanberecognizedin recognitioncanbe doneinsinglyexponentialtime. However, affirmatively. polynomialtime. Theysupportedtheirconjecturebyshowing theyconjecturedthat,infact,mapgraphscanberecognizedin thatifweallowatmost4facestomeetinanysinglepoint,the 1.Introduction polynomialtime. Theysupportedtheirconjecturebyshowing resultingmapgraph6 scanberecognizedinpolynomialtime. In thatifweallowatmost4facestomeetinanysinglepoint,the 1.Introduction thispaper,wesettlethegeneralconjecture,showingthatgiven RecentlyChen,Grigni,andPapadimitriou4,5suggested resultingmapgraphscanberecognizedinpolynomialtime. In agraph,wecandecideinpolynomialtimeifitisamapgraph. the study of a modified notion of planarity. The basic frame thispaper,wesettlethegeneralconjecture,showingthatgiven Thealgorithmcaneasilybemodifiedtodrawacorresponding RecentlyChen,Grigni,andPapadimitriou4,5suggested workisthesameasthatofplanargraphs. Wearegivenasetof agraph,wecandecideinpolynomialtimeifitisamapgraph. mapifitexists. the study of a modified notion of planarity. The basic frame nonoverlapping faces in theplane,Th each ealgbei orintghm a di casncehom asilyeo bemodifiedtodrawacorresponding workisthesameasthatofplanargraphs. Wearegivenasetof morphism. By nonoverlapping,wma empeiafnitthexatisttw s.ofacesmay nonoverlapping faces in theplane, eachbeinga dischomeo Mapcoloring Itshouldbenotedthatcoloringofmapgraphs only intersectin their boundaries. The plane may or may not morphism. By nonoverlapping,wemeanthattwofacesmay datesbacktoOreandPlummerin19698,thatis,theywanted becompletelycoveredbythefaces. Atraditionalplanargraph Mapcoloring Itshouldbenotedthatcoloringofmapgraphs only intersectin their boundaries. The plane may or may not tocolorthefacessothatanytwointersectingfacesgotdifferent is obtained as follows. The vertices are the faces, and two datesbacktoOreandPlummerin19698,thatis,theywanted becompletelycoveredbythefaces. Atraditionalplanargraph colors. Foranaccountofcolorfulhistory,thereaderisreferred faces are neighbors if their intersection contains a nontrivial tocolorthefacessothatanytwointersectingfacesgotdifferent is obtained as follows. The vertices are the faces, and two to 7, 2.5. In particular, the history provides ananswer to a curve. Chen et.al.4, 5 suggestedsimplifying the definition, colors. Foranaccountofcolorfulhistory,thereaderisreferred faces are neighbors if their intersection contains a nontrivial problemofChenet.al. 5: ifatmost4facesmeetinanysingle by saying that two faces are neighbors if and only if they in to 7, 2.5. In particular, the history provides ananswer to a curve. Chen et.al.4, 5 suggestedsimplifying the definition, point,canwecolorthemapwith6colors Itisstraightforward tersect in at least one point. They called the resulting graphs problemofChenet.al. 5: ifatmost4facesmeetinanysingle by saying that two faces are neighbors if and only if they in toseethattheresultinggraphsare1planar,meaningthatthey “planarmapgraphs”. Herewewilljustcallthemmapgraphs. point,canwecolorthemapwith6colors Itisstraightforward tersect in at least one point. They called the resulting graphs canbedrawnintheplanesuchthateachedgeiscrossedbyat Note that there are nonplanar map graphs, for as illustrated toseethattheresultinggraphsare1planar,meaningthatthey “planarmapgraphs”. Herewewilljustcallthemmapgraphs. mostoneotheredge. Alreadyin1965,Ringel9conjectured in Figure 1, map graphs can contain arbitrarily large cliques. canbedrawnintheplanesuchthateachedgeiscrossedbyat Note that there are nonplanar map graphs, for as illustrated that all1planar graphs canbe coloredwith 6 colors,and this We shall refer to the first type of clique as a flower with the mostoneotheredge. Alreadyin1965,Ringel9conjectured in Figure 1, map graphs can contain arbitrarily large cliques. conjecture wassettled in 1984 by Borodin 2, so the answer petals intersecting in a center.Thesecondisa hamantash that all1planar graphs canbe coloredwith 6 colors,and this We shall refer to the first type of clique as a flower with the toChenet.al.’s problemis: yes. basedon three distinct corner points.Eachofthethreepairs conjecture wassettled in 1984 by Borodin 2, so the answer petals intersecting in a center.Thesecondisa hamantash of corner points is connected by a side of parallel faces.In toChenet.al.’s problemis: yes. basedon three distinct corner points.Eachofthethreepairs Map metrics The shortest path metrics of map graphs are Most ofthis workwasdonewhiletheauthor visitedMIT. of corner points is connected by a side of parallel faces.In Chen et.al.calledflowersforpizzas, but“flower”seems morenatural. commonly used in prizing systems,where you pay for cross Map metrics The shortest path metrics of map graphs are Most ofthis workwasdonewhiletheauthor visitedMIT. Chen et.al.calledflowersforpizzas, but“flower”seems morenatural. commonly used in prizing systems,where you pay for crossWorstcase analysis Worst case. Running time guarantee for any input of size n. Generally captures efficiency in practice. Draconian view, but hard to find effective alternative. Exceptions. Some exponentialtime algorithms are used widely in practice because the worstcase instances seem to be rare. simplex algorithm Linux grep kmeans algorithm 7Types of analyses Worst case. Running time guarantee for any input of size n. Ex. Heapsort requires at most 2 n log n compares to sort n elements. 2 Probabilistic. Expected running time of a randomized algorithm. Ex. The expected number of compares to quicksort n elements is 2n ln n. Amortized. Worstcase running time for any sequence of n operations. Ex. Starting from an empty stack, any sequence of n push and pop operations takes O(n) operations using a resizing array. Averagecase. Expected running time for a random input of size n. Ex. The expected number of character compares performed by 3way radix quicksort on n uniformly random strings is 2n ln n. Also. Smoothed analysis, competitive analysis, ... 8Why it matters 92. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ SECTION 2.2BigOh notation Upper bounds. T(n) is O( f (n)) if there exist constants c 0 and n ≥ 0 0 such that T(n) ≤ c · f (n) for all n ≥ n . 0 c · f (n) 2 Ex. T(n) = 32n + 17n + 1. T(n) 2 choose c = 50, n = 1 0 T(n) is O(n ). 3 T(n) is also O(n ). T(n) is neither O(n) nor O(n log n). n n 0 2 Typical usage. Insertion makes O(n ) compares to sort n elements. T(n) limsup . Alternate definition. T(n) is O( f (n)) if f(n) n 11Notational abuses Equals sign. O( f (n)) is a set of functions, but computer scientists often write T(n) = O( f (n)) instead of T(n) ∈ O( f (n)). 3 2 Ex. Consider f (n) = 5n and g (n) = 3n . 3 We have f (n) = O(n ) = g(n). Thus, f (n) = g(n). Domain. The domain of f (n) is typically the natural numbers 0, 1, 2, … . Sometimes we restrict to a subset of the natural numbers. Other times we extend to the reals. Nonnegative functions. When using bigOh notation, we assume that the functions involved are (asymptotically) nonnegative. Bottom line. OK to abuse notation; not OK to misuse it. 12BigOmega notation Lower bounds. T(n) is Ω( f (n)) if there exist constants c 0 and n ≥ 0 0 such that T(n) ≥ c · f (n) for all n ≥ n . 0 T(n) 2 Ex. T(n) = 32n + 17n + 1. c · f (n) 2 choose c = 32, n = 1 0 T(n) is both Ω(n ) and Ω(n). 3 3 T(n) is neither Ω(n ) nor Ω(n log n). n n 0 Typical usage. Any comparebased sorting algorithm requires Ω(n log n) compares in the worst case. Meaningless statement. Any comparebased sorting algorithm requires at least O(n log n) compares in the worst case. 13BigTheta notation Tight bounds. T(n) is Θ( f (n)) if there exist constants c 0, c 0, and n ≥ 0 1 2 0 such that c · f (n) ≤ T(n) ≤ c · f (n) for all n ≥ n . 1 2 0 c · f (n) 2 T(n) 2 Ex. T(n) = 32n + 17n + 1. c · f (n) 1 2 choose c = 32, c = 50, n = 1 1 2 0 T(n) is Θ(n ). 3 T(n) is neither Θ(n) nor Θ(n ). n n 0 Typical usage. Mergesort makes Θ(n log n) compares to sort n elements. 14Useful facts f(n) lim = c 0 Proposition. If , then f (n) is Θ(g(n)). n g(n) Pf. By definition of the limit, there exists n such such that for all n ≥ n 0 0 1 f(n) c 2c 2 g(n) Thus, f (n) ≤ 2 c g(n) for all n ≥ n , which implies f (n) is O(g(n)). 0 Similarly, f (n) ≥ ½ c g(n) for all n ≥ n , which implies f (n) is Ω(g(n)). 0 f(n) Proposition. If , then f (n) is O(g(n)). lim =0 n g(n) 15Asymptotic bounds for some common functions d d Polynomials. Let T(n) = a + a n + … + a n with a 0. Then, T(n) is Θ(n ). 0 1 d d d a +a n+...+a n 0 1 d lim = a 0 d Pf. d n n no need to specify base Logarithms. Θ(log n) is Θ(log n) for any constants a, b 0. a b (assuming it is a constant) d Logarithms and polynomials. For every d 0, log n is O(n ). d n Exponentials and polynomials. For every r 1 and every d 0, n is O(r ). d n lim =0 Pf. n n r 16BigOh notation with multiple variables Upper bounds. T(m, n) is O( f (m, n)) if there exist constants c 0, m ≥ 0, 0 and n ≥ 0 such that T(m, n) ≤ c · f (m, n) for all n ≥ n and m ≥ m . 0 0 0 2 3 Ex. T(m, n) = 32mn + 17mn + 32n . 2 3 3 T(m, n) is both O(mn + n ) and O(mn ). 3 2 T(m, n) is neither O(n ) nor O(mn ). Typical usage. Breadthfirst search takes O(m + n) time to find the shortest path from s to t in a digraph. 172. ALGORITHM ANALYSIS computational tractability ‣ asymptotic order of growth ‣ survey of common running times ‣ SECTION 2.4Linear time: O(n) Linear time. Running time is proportional to input size. Computing the maximum. Compute maximum of n numbers a , …, a . 1 n max ← a 1 for i = 2 to n if (a max) i max ← a i 19Linear time: O(n) Merge. Combine two sorted lists A = a , a , …, a with B = b , b , …, b into sorted 1 2 n 1 2 n whole. i = 1, j = 1 while (both lists are nonempty) if (a ≤ b ) append a to output list and increment i i j i else(a ≤ b )append b to output list and increment j i j j append remainder of nonempty list to output list Claim. Merging two lists of size n takes O(n) time. Pf. After each compare, the length of output list increases by 1. 20Linearithmic time: O(n log n) O(n log n) time. Arises in divideandconquer algorithms. Sorting. Mergesort and heapsort are sorting algorithms that perform O(n log n) compares. Largest empty interval. Given n timestamps x , …, x on which copies of a 1 n file arrive at a server, what is largest interval when no copies of file arrive O(n log n) solution. Sort the timestamps. Scan the sorted list in order, identifying the maximum gap between successive timestamps. 212 Quadratic time: O(n ) Ex. Enumerate all pairs of elements. Closest pair of points. Given a list of n points in the plane (x , y ), …, (x , y ), 1 1 n n find the pair that is closest. 2 O(n ) solution. Try all pairs of points. 2 2 min ← (x x ) + (y y ) 1 2 1 2 for i = 1 to n for j = i+1 to n 2 2 d ← (x x ) + (y y ) i j i j if (d min) min ← d 2 Remark. Ω(n ) seems inevitable, but this is just an illusion. see Chapter 5 223 Cubic time: O(n ) Cubic time. Enumerate all triples of elements. Set disjointness. Given n sets S , …, S each of which is a subset of 1 n 1, 2, …, n, is there some pair of these which are disjoint 3 O(n ) solution. For each pair of sets, determine if they are disjoint. foreach set S i foreach other set S j foreach element p of S i determine whether p also belongs to S j if (no element of S belongs to S ) i j report that S and S are disjoint i j 23k Polynomial time: O(n ) Independent set of size k. Given a graph, are there k nodes such that no two are joined by an edge k is a constant k O(n ) solution. Enumerate all subsets of k nodes. foreach subset S of k nodes check whether S in an independent set if (S is an independent set) report S is an independent set 2 Check whether S is an independent set takes O(k ) time. k n n(n 1)(n 2) ··· (n k+1) n Number of k element subsets = = k k(k 1)(k 2) ··· 1 k 2 k k O(k n / k) = O(n ). polytime for k=17, but not practical 24Exponential time Independent set. Given a graph, what is maximum cardinality of an independent set 2 n O(n 2 ) solution. Enumerate all subsets. S ← φ foreach subset S of nodes check whether S in an independent set if (S is largest independent set seen so far) update S ← S 25Sublinear time Search in a sorted array. Given a sorted array A of n numbers, is a given number x in the array O(log n) solution. Binary search. lo ← 1, hi ← n while (lo ≤ hi) mid ← (lo + hi) / 2 if (x Amid) hi ← mid 1 else if (x Amid) lo ← mid + 1 else return yes return no 26
Website URL
Comment