Algorithm Design 2-2 Asymptotic Order of Growth
TL; DL
Asymptotic...グラフ同士の時間、記憶領域水準の評価基準（Order) multiple f(n)の差を表す。 T is asymptotically upper-bounded by f . Tはasymptotically upper-bounded。T (n) ≤ c · f (n)
T(n)= pn^2+qn+r is O(n^2). T(n) is the worst-case running time of a certain algorithm. = upper bound
lower-bound..T(n) = pn2 + qn + r ≥ pn^2, which meets what is required by the definition of Ω(·) with ε = p > 0.
tight-bound: T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). f(n) is an asymptotically tight bound for T(n). An upper bound is said to be a tight upper bound, a least upper bound, or a supremum, if no smaller value is an upper bound. ; upper boundとlower-boundのvalueが同じ時。T(n) = Θ(n^2). Θ(f(n))= O(f(n)) + Ω(f(n))
Upper-bound proof: f(n) ≤ 2cg(n) for all n ≥ n0, which implies that f(n) = O(g(n)); Lower-bound proof: f(n) ≥ 1/2cg(n) for all n ≥ n0, which implies that f (n) = Ω(g(n)).
a polynomial-time algorithm is one whose running time T(n) is O(n^d) for some constant d, where d is independent of the input size.
Logarithms 2^3 = 8 ⇔ 3 = log28 base 2, exponent 3. For example, n (log n) のnはこの場合8である。baseである2は省略される。
Logarithms grow more slowly than polynomials, and polynomials grow more slowly than exponentials.
We will mainly express algorithms in the pseudo-code style that we used for the Gale-Shapley algorithm.
one step will consist of assigning a value to a variable, looking up an entry in an array, following a pointer, or performing an arithmetic operation on a fixed-size integer.
“On any input of size n, the algorithm runs for at most 1.62n^2 +3.5n + 8 steps.”
First, getting such a precise bound may be an exhausting activity, and more detail than we wanted anyway.
Second, because our ultimate goal is to identify broad classes of algorithms that have similar behavior, we’d actually like to classify running times at a coarser level of granularity so that similarities among different algorithms, and among different problems, show up more clearly.
And finally, extremely detailed statements about the number of steps an algorithm executes are often—in a strong sense—meaningless.
As just discussed, we will generally be counting steps in a pseudo-code specification of an algorithm that resembles a high- level programming language.
our algorithm that took at most 1.62n^2 + 3.5n + 8 steps can also be viewed as taking 40.5n^2 + 87.5n + 200 steps when we analyze it at a level that is closer to the actual hardware.
O, Ω, and Θ
• 「O」はオーダー(Order)という単語に由来し、ランダウの記号などとも呼ばれ、実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するかを評価するも基準として用いられる
- Ω は ω^3 = 1
Asymptotic Upper Bounds
Let T(n) be a function—say, the worst-case running time of a certain algorithm on an input of size n.
Given another function f(n), we say that T(n) is O(f(n)) (read as “T(n) is order f(n)”) if, for sufficiently large n, the function T(n) is bounded above by a constant multiple of f (n).
multiple of function = f(n)
We will also sometimes write this as T (n) = O(f (n)). T(n) is O(f(n)) if there exist constants c > 0 and n0 ≥ 0 so that for all n ≥ n0, we have T (n) ≤ c · f (n). In this case, we will say that T is asymptotically upper-bounded by f . It is important to note that this definition requires a constant c to exist that works for all n; in particular, c cannot depend on n.
As an example of how this definition lets us express upper bounds on running times, consider an algorithm whose running time (as in the earlier discussion) has the form **T(n) = pn^2 + qn + r for positive constants p, q, and r. We’d like to claim that any such function is O(*n^*2).
To see why, we notice that for all n≥1, we have qn ≤ *qn^*2, and r ≤ *rn^*2. So we can write
**T(n)= *pn^*2 +qn+r ≤ *pn^*2 +*qn^*2 +*rn^*2 = (p+q+r)n^2
for all n ≥ 1. This inequality is exactly what the definition of O(·) requires:
**T(n) ≤ cn^2, where c = p + q + r.
Note that O(·) expresses only an upper bound, not the exact growth rate of the function. T(n)= pn^2+qn+r is O(n^2).
Indeed, we just argued that T(n)≤(p+q+r)*n^*2, and since we also have *n^*2 ≤ *n^*3, we can conclude that T(n) ≤ (p + q + r)*n^*3 as the definition of O(*n^*3) requires.
There are cases where an algorithm has been proved to have running time O(*n^*3).
some years pass, people analyze the same algorithm more carefully, and they show that in fact its running time is O(*n^*2).
There was nothing wrong with the first result; it was a correct upper bound. It’s simply that it wasn’t the “tightest” possible running time.
Asymptotic Lower Bounds
we want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some specific function f (n). (In this example, f (n) happens to be *n^*2.)
Thus, we say that T(n) is Ω(f(n)) (also written T(n) = Ω(f(n))) if there exist constants ε > 0 and n0 ≥ 0 so that for all n ≥ n0, we have T (n) ≥ ε · f (n).
By analogy with O(·) notation, we will refer to T in this case as being asymptotically lower- bounded by f.
Again, note that the constant ε must be fixed, independent of n.an infinitesimally small positive quantity is commonly denoted ε; see (ε, δ)-definition of limit.
- epsilon(ε)…an infinitesimally small positive quantity is commonly denoted ε; see (ε, δ)-definition of limit.
This definition works just like O(·), except that we are bounding the function T(n) from below, rather than from above. For example, returning to the function T(n) = *pn^*2 + qn + r, where p, q, and r are positive constants, let’s claim that T(n) = Ω(*n^*2).
upper boundは O(n^2), lower boundはΩ(n^2)で表す。 Order（Big O notation)は実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するか。 Omegaはω^3 = 1。
Whereas establishing the upper bound involved “inflating” the terms in T(n) until it looked like a constant times *n^*2, now we need to do the opposite: we need to reduce the size of T(n) until it looks like a constant times *n^*2. It is not hard to do this; for all n ≥ 0, we have
**T(n) = pn2 + qn + r ≥ pn^2,
which meets what is required by the definition of Ω(·) with ε = p > 0.
Just as we discussed the notion of “tighter” and “weaker” upper bounds, the same issue arises for lower bounds.
For example, it is correct to say that our function **T(n)=pn^2+qn+r is Ω(n),sinceT(n)≥pn^2≥pn.
逆にいうとupper-boundはlower-boundでもあるというproof **T(n)=pn^2+qn+r is Ω(n),sinceT(n)≥pn^2≥pn.
Asymptotically Tight Bounds If we can show that a running time T(n) is both O(f (n)) and also Ω(f (n)), then in a natural sense we’ve found the “right” bound: T(n) grows exactly like f(n) to within a constant factor. This, for example, is the conclusion we can draw from the fact that T(n) = pn2 + qn + r is both O(*n^*2) and Ω(*n^*2).
There is a notation to express this: if a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In this case, we say that f(n) is an asymptotically tight bound for T(n). So, for example, our analysis above shows that **T(n)=*pn^*2 +qn+r is Θ(n^2).
T(n) = Θ(n^2). Θ(f(n))= O(f(n)) + Ω(f(n))
The supremum (abbreviated sup; plural suprema) of a subset of a partially ordered set is the least element in that is greater than or equal to each element of if such an element exists. In other words, it is the least element of that is greater than or equal to the greatest element of. .
https://www.math.ucdavis.edu/~hunter/m125b/ch2.pdf
supremum(least upper bound)
The supremum of a set is its least upper bound and the infimum is its greatest upper bound. Definition 2.2. Suppose that A ⊂ R is a set of real numbers. If M ∈ R is an upper bound of A such that M ≤ M′ for every upper bound M′ of A, then M is called the supremum of A, denoted M = sup A.
Asymptotically tight bounds on worst-case running times are nice things to find, since they characterize the worst-case performance of an algorithm precisely up to constant factors.
And as the definition of Θ(·) shows, one can obtain such bounds by closing the gap between an upper bound and a lower bound.
For example, sometimes you will read a (slightly informally phrased) sentence such as “An upper bound of O(*n^*3) has been shown on the worst-case running time of the algorithm, but there is no example known on which the algorithm runs for more than Ω(*n^*2) steps.” This is implicitly an invitation to search for an asymptotically tight bound on the algorithm’s worst-case running time.
Sometimes one can also obtain an asymptotically tight bound directly by computing a limit as n goes to infinity.
Essentially, if the ratio of functions f(n) and g(n) converges to a positive constant as n goes to infinity, then f (n) = Θ(g(n)).
(2.1) Let f and g be two functions that lim f (n)
n→∞ g(n) exists and is equal to some number c > 0*. Then f* (n) = Θ(g(n)).
Proof. We will use the fact that the limit exists and is positive to show that f (n) = O(g(n)) and f (n) = Ω(g(n)), as required by the definition of Θ(·).
Since
lim f(n)=c>0, n→∞ g(n)
it follows from the definition of a limit that there is some n0 beyond which the ratio is always between 1/2c and 2c.
Thus, f(n) ≤ 2cg(n) for all n ≥ n0, which implies that f(n) = O(g(n)); and f(n) ≥ 1/2cg(n) for all n ≥ n0, which implies that f (n) = Ω(g(n)).
Properties of Asymptotic Growth Rates
Transitivity
(2.2) (a) If f =O(g) and g =O(h), then f =O(h). (b) If f =Ω(g) and g =Ω(h), then f =Ω(h).
Proof:
For (a), we’re given that for some constants c and n0, we have f (n) ≤ cg(n) for all n ≥ n0. Also, for some (potentially different) constants c′ and n0′ , we have g(n) ≤ c′h(n) for all n ≥ n0′ . So consider any number n that is at least as large as both n0 and n0′.
We have f (n) ≤ cg(n) ≤ cc′h(n), and so f (n) ≤ cc′h(n) for all n ≥ max(n0, n0′ ).
This latter inequality is exactly what is required for showing that f = O(h).
Combining parts (a) and (b) of (2.2), we can obtain a similar result for asymptotically tight bounds. Suppose we know that f = Θ(g) and that g = Θ(h). Then since f = O(g) and g = O(h), we know from part (a) that f =O(h); since f =Ω(g) and g =Ω(h), we know from part (b) that f =Ω(h). It follows that f = Θ(h). Thus we have shown
(2.3) If f =Θ(g) and g =Θ(h), then f =Θ(h).
Sums of Functions It is also useful to have results that quantify the effect of adding two functions. First, if we have an asymptotic upper bound that applies to each of two functions f and g, then it applies to their sum.
(2.4) Suppose that f and g are two functions such that for some other function h, we have f =O(h) and g =O(h). Then f +g =O(h).
Proof. We’re given that for some constants c and n0, we have f (n) ≤ ch(n) for all n ≥ n0. Also, for some (potentially different) constants c′ and n0′ , we have g(n) ≤ c′h(n) for all n ≥ n0′. So consider any number n that is at least as large as both n0 and n0′. We have f (n) + g(n) ≤ ch(n) + c′h(n). Thus f(n) + g(n) ≤ (c + c′)h(n) for all n ≥ max(n0, n0′ ), which is exactly what is required for showing that f + g = O(h).
There is a generalization of this to sums of a fixed constant number of functions k, where k may be larger than two.
(2.5) Let k be a fixed constant, and let f1, f2, . . . , fk and h be functions such that fi = O(h) for all i. Then f1 + f2 + . . . + fk = O(h).
(2.6) Suppose that f and g are two functions (taking non-negative values) such that g = O(f ). Then f + g = Θ(f ). In other words, f is an asymptotically tight bound for the combined function f + g.
Proof. Clearly f + g = Ω(f), since for all n ≥ 0, we have f(n) + g(n) ≥ f(n). So to complete the proof, we need to show that f + g = O(f ).
But this is a direct consequence of (2.4): we’re given the fact that g = O(f ), and also f = O(f) holds for any function, so by (2.4) we have f + g = O(f).
This result also extends to the sum of any fixed, constant number of functions: the most rapidly growing among the functions is an asymptotically tight bound for the sum.
**Asymptotic Bounds for Some Common Functions
Polynomials** Recall that a polynomial is a function that can be written in the form f(n)=a0+a1n+a2*n^*2+...+adn^d for some integer constant d>0, where the final coefficient ad is nonzero. This value d is called the degree of the polynomial. For example, the functions of the form *pn^*2 + qn + r (with p = **̸ 0) that we considered earlier are polynomials of degree
(2.7) Let f be a polynomial of degree d, in which the coefficient ad is positive. Then f = O(n^d).
Proof. We write f=a0+a1n+a2*n^*2+...+adn^d, where ad>0. The upper bound is a direct application of (2.5)fi = O(h) for all i. Then f1 + f2 + . . . + fk = O(h). First, notice that coefficients aj for j < d may be negative, but in any case we have ajn^j ≤ |aj|n^d for all n ≥ 1. Thus each term in the polynomial is O(n^d). Since f is a sum of a constant number of functions, each of which is O(n^d), it follows from (2.5) fi = O(h) for all i. Then f1 + f2 + . . . + fk = O(h). that f is O(n^d).
One can also show that under the conditions of (2.7) f = O(n^d), we have f = Ω(n^d), and hence it follows that in fact f = Θ(n^d). This is a good point at which to discuss the relationship between these types of asymptotic bounds and the notion of polynomial time, which we arrived at in the previous section as a way to formalize the more elusive concept of efficiency. Using O(·) notation, it’s easy to formally define polynomial time: a polynomial-time algorithm is one whose running time T(n) is O(n^d) for some constant d, where d is independent of the input size.
So algorithms with running-time bounds like O(*n^*2) and O(*n^*3) are polynomial-time algorithms. But it’s important to realize that an algorithm can be polynomial time even if its running time is not written as n raised to some integer power. To begin with, a number of algorithms have running times of the form O(n^x) for some number x that is not an integer. For example, in Chapter 5 we will see an algorithm whose running time is O(*n^*1.59); we will also see exponents less than 1, as in bounds like O(√n) = O(*n^*1/2).|
algorithmのinput size **d(degree)**はintegerだけじゃないよという普通の話。
To take another common kind of example, we will see many algorithms whose running times have the form O(n log n). Such algorithms are also polynomial time: as we will see next, log n ≤ n for all n ≥ 1, and hence n log n ≤ *n^*2 for all n ≥ 1. In other words, if an algorithm has running time O(n log n), then it also has running time O(*n^*2), and so it is a polynomial-time algorithm.
**Logarithms 2^3 = 8 ⇔ 3 = log2 8, 2x = 9 → x = log2 9 a^x = M ⇔ x = loga M (M = antilogarithm(result)) **Recall that logb n is the number x such that b^x = n. One way to get an approximate sense of how fast logb n grows is to note that, if we round it down to the nearest integer, it is one less than the number of digits in the base-b representation of the number n. (Thus, for example, 1 + log2 n, rounded down, is the number of bits needed to represent n.) So logarithms are very slowly growing functions. In particular, for every base b, the function logb n is asymptotically bounded by every function of the form n^x, even for (non-integer) values of x arbitrary close to 0.
(2.8) For every b>1 and every x>0*, we have* logb n=O(n^x).
logb n=O(n^x)は書き換えているだけ。x=exponential, b=base, n=antilogarithm
One can directly translate between logarithms of different bases using the following fundamental identity: loga n = logb n /logb a
This equation explains why you’ll often notice people writing bounds like O(log n) without indicating the base of the logarithm.
This is not sloppy usage: the identity above says that
log n = 1/logb a · logb n
so the point is that
loga n = Θ(logb n) and the base of the logarithm is not important when writing bounds using asymptotic notation.
Exponentials
******Exponential functions are functions of the form f (n) = r^n for some constant base r.
f(3) = 2^3
Here we will be concerned with the case in which r > 1, which results in a very fast-growing function.
In particular, where polynomials raise n to a fixed exponent, exponentials raise a fixed number to n as a power; this leads to much faster rates of growth. One way to summarize the relationship between polynomials and exponentials is as follows.
(2.9) For every r >1 and every d >0*, we have n^d*=O(r^n).
In particular, every exponential grows faster than every polynomial. And as we saw in Table 2.1, when you plug in actual values of n, the differences in growth rates are really quite impressive.
Just as people write O(log n) without specifying the base, you’ll also see people write “The running time of this algorithm is exponential,”without specifying which exponential function they have in mind.
Unlike the liberal use of log n, which is justified by ignoring constant factors, this generic use of the term “exponential” is somewhat sloppy.
基本的にlog n はbaseの要素は無視。“The running time of this algorithm is exponential”
In particular, for different bases r > s > 1, it is never the case that r^n = Θ(s^n). Indeed, this would require that for some constant c > 0, we would have r^n ≤ cs^n for all sufficiently large n.
But rearranging this inequality would give (r/s)^n ≤ c for all sufficiently large n.
Since r > s, the expression (r/s)n is tending to infinity with n, and so it cannot possibly remain bounded by a fixed constant c.
この場合constant Cはboundにならない、(r/s)^nは無限に増え続けるから。
So asymptotically speaking, exponential functions are all different. Still, it’s usually clear what people intend when they inexactly write “The running time of this algorithm is exponential”—they typically mean that the running time grows at least as fast as some exponential function, and all exponentials grow so fast that we can effectively dismiss this algorithm without working out further details of the exact running time. This is not entirely fair. Occasionally there’s more going on with an exponential algorithm than first appears, as we’ll see, for example, in Chapter 10; but as we argued in the first section of this chapter, it’s a reasonable rule of thumb.
Taken together, then, logarithms, polynomials, and exponentials serve as useful landmarks in the range of possible functions that you encounter when analyzing running times. Logarithms grow more slowly than polynomials, and polynomials grow more slowly than exponentials.