Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 11
Текст из файла (страница 11)
This abuse of equality to denoteset membership may at first appear confusing, but we shall see later in this section that it hasadvantages.Figure 3.1(a) gives an intuitive picture of functions f(n) and g(n), where we have that f(n) =Θ(g(n)). For all values of n to the right of n0, the value of f(n) lies at or above c1g(n) and at orbelow c2g(n). In other words, for all n ≥ n0, the function f(n) is equal to g(n) to within aconstant factor.
We say that g(n) is an asymptotically tight bound for f(n).Figure 3.1: Graphic examples of the Θ, O, and Ω notations. In each part, the value of n0shown is the minimum possible value; any greater value would also work. (a) Θ-notationbounds a function to within constant factors. We write f(n) = Θ(g(n)) if there exist positiveconstants n0, c1, and c2 such that to the right of n0, the value of f(n) always lies between c1g(n)and c2g(n) inclusive.
(b) O-notation gives an upper bound for a function to within a constantfactor. We write f(n) = O(g(n)) if there are positive constants n0 and c such that to the right ofn0, the value of f(n) always lies on or below cg(n). (c) Ω-notation gives a lower bound for afunction to within a constant factor. We write f(n) = Ω(g(n)) if there are positive constants n0and c such that to the right of n0, the value of f(n) always lies on or above cg(n).The definition of Θ(g(n)) requires that every member f(n) Θ(g(n)) be asymptoticallynonnegative, that is, that f(n) be nonnegative whenever n is sufficiently large.
(Anasymptotically positive function is one that is positive for all sufficiently large n.)Consequently, the function g(n) itself must be asymptotically nonnegative, or else the setΘ(g(n)) is empty. We shall therefore assume that every function used within Θ-notation isasymptotically nonnegative. This assumption holds for the other asymptotic notations definedin this chapter as well.In Chapter 2, we introduced an informal notion of Θ-notation that amounted to throwing awaylower-order terms and ignoring the leading coefficient of the highest-order term. Let usbriefly justify this intuition by using the formal definition to show that 1/2n2 - 3n = Θ(n2).
Todo so, we must determine positive constants c1, c2, and n0 such thatc1n2 ≤ 1/2n2 - 3n ≤ c2n2for all n ≥ n0. Dividing by n2 yieldsc1 ≤ 1/2 - 3/n ≤ c2.The right-hand inequality can be made to hold for any value of n ≥ 1 by choosing c2 ≥ 1/2.Likewise, the left-hand inequality can be made to hold for any value of n ≥ 7 by choosing c1 ≤1/14. Thus, by choosing c1 = 1/14, c2 = 1/2, and n0 = 7, we can verify that 1/2n2 - 3n = Θ(n2).Certainly, other choices for the constants exist, but the important thing is that some choiceexists. Note that these constants depend on the function 1/2n2 - 3n; a different functionbelonging to Θ(n2) would usually require different constants.We can also use the formal definition to verify that 6n3 ≠ Θ(n2). Suppose for the purpose ofcontradiction that c2 and n0 exist such that 6n3 ≤ c2n2 for all n ≥ n0.
But then n ≤ c2/6, whichcannot possibly hold for arbitrarily large n, since c2 is constant.Intuitively, the lower-order terms of an asymptotically positive function can be ignored indetermining asymptotically tight bounds because they are insignificant for large n. A tinyfraction of the highest-order term is enough to dominate the lower-order terms. Thus, settingc1 to a value that is slightly smaller than the coefficient of the highest-order term and settingc2 to a value that is slightly larger permits the inequalities in the definition of Θ-notation to besatisfied.
The coefficient of the highest-order term can likewise be ignored, since it onlychanges c1 and c2 by a constant factor equal to the coefficient.As an example, consider any quadratic function f(n) = an2 + bn + c, where a, b, and c areconstants and a > 0. Throwing away the lower-order terms and ignoring the constant yieldsf(n) = Θ(n2). Formally, to show the same thing, we take the constants c1 = a/4, c2 = 7a/4, and.
The reader may verify that 0 ≤ c1n2 ≤ an2 + bn + c ≤ c2n2 for all n ≥ n0.In general, for any polynomial, where the ai are constants and ad > 0, we havedp(n) = Θ(n ) (see Problem 3-1).Since any constant is a degree-0 polynomial, we can express any constant function as Θ(n0),or Θ(1). This latter notation is a minor abuse, however, because it is not clear what variable istending to infinity.[2] We shall often use the notation Θ(1) to mean either a constant or aconstant function with respect to some variable.O-notationThe Θ-notation asymptotically bounds a function from above and below.
When we have onlyan asymptotic upper bound, we use O-notation. For a given function g(n), we denote byO(g(n)) (pronounced "big-oh of g of n" or sometimes just "oh of g of n") the set of functionsO(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥n0}.We use O-notation to give an upper bound on a function, to within a constant factor. Figure3.1(b) shows the intuition behind O-notation. For all values n to the right of n0, the value ofthe function f(n) is on or below g(n).We write f(n) = O(g(n)) to indicate that a function f(n) is a member of the set O(g(n)).
Notethat f(n) = Θ(g(n)) implies f(n) = O(g(n)), since Θ-notation is a stronger notion than Onotation. Written set-theoretically, we have Θ(g(n)) O(g(n)). Thus, our proof that anyquadratic function an2 + bn + c, where a > 0, is in Θ(n2) also shows that any quadraticfunction is in O(n2). What may be more surprising is that any linear function an + b is inO(n2), which is easily verified by taking c = a + |b| and n0 = 1.Some readers who have seen O-notation before may find it strange that we should write, forexample, n = O(n2).
In the literature, O-notation is sometimes used informally to describeasymptotically tight bounds, that is, what we have defined using Θ-notation. In this book,however, when we write f(n) = O(g(n)), we are merely claiming that some constant multipleof g(n) is an asymptotic upper bound on f(n), with no claim about how tight an upper bound itis. Distinguishing asymptotic upper bounds from asymptotically tight bounds has nowbecome standard in the algorithms literature.Using O-notation, we can often describe the running time of an algorithm merely byinspecting the algorithm's overall structure.
For example, the doubly nested loop structure ofthe insertion sort algorithm from Chapter 2 immediately yields an O(n2) upper bound on theworst-case running time: the cost of each iteration of the inner loop is bounded from above byO(1) (constant), the indices i and j are both at most n, and the inner loop is executed at mostonce for each of the n2 pairs of values for i and j.Since O-notation describes an upper bound, when we use it to bound the worst-case runningtime of an algorithm, we have a bound on the running time of the algorithm on every input.Thus, the O(n2) bound on worst-case running time of insertion sort also applies to its runningtime on every input.
The Θ(n2) bound on the worst-case running time of insertion sort,however, does not imply a Θ(n2) bound on the running time of insertion sort on every input.For example, we saw in Chapter 2 that when the input is already sorted, insertion sort runs inΘ(n) time.Technically, it is an abuse to say that the running time of insertion sort is O(n2), since for agiven n, the actual running time varies, depending on the particular input of size n. When wesay "the running time is O(n2)," we mean that there is a function f(n) that is O(n2) such that forany value of n, no matter what particular input of size n is chosen, the running time on thatinput is bounded from above by the value f(n). Equivalently, we mean that the worst-caserunning time is O(n2).Ω-notationJust as O-notation provides an asymptotic upper bound on a function, Ω-notation provides anasymptotic lower bound.
For a given function g(n), we denote by Ω(g(n)) (pronounced "bigomega of g of n" or sometimes just "omega of g of n") the set of functionsΩ(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥n0}.The intuition behind Ω-notation is shown in Figure 3.1(c). For all values n to the right of n0,the value of f(n) is on or above cg(n).From the definitions of the asymptotic notations we have seen thus far, it is easy to prove thefollowing important theorem (see Exercise 3.1-5).Theorem 3.1For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) andf(n) = Ω(g(n)).As an example of the application of this theorem, our proof that an2 + bn + c = Θ(n2) for anyconstants a, b, and c, where a > 0, immediately implies that an2 + bn + c = Ω(n2) and an2 + bn+ c = O(n2).
In practice, rather than using Theorem 3.1 to obtain asymptotic upper and lowerbounds from asymptotically tight bounds, as we did for this example, we usually use it toprove asymptotically tight bounds from asymptotic upper and lower bounds.Since Ω-notation describes a lower bound, when we use it to bound the best-case runningtime of an algorithm, by implication we also bound the running time of the algorithm onarbitrary inputs as well. For example, the best-case running time of insertion sort is Ω(n),which implies that the running time of insertion sort is Ω(n).The running time of insertion sort therefore falls between Ω(n) and O(n2), since it fallsanywhere between a linear function of n and a quadratic function of n. Moreover, thesebounds are asymptotically as tight as possible: for instance, the running time of insertion sortis not Ω(n2), since there exists an input for which insertion sort runs in Θ(n) time (e.g., whenthe input is already sorted).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
