In that last analysis of grid graphs,
we ended up discovering that the number of edges is 2n - 2√n,
which is such a terrible function, but the fact of the matter is
as these analyses get more and more complicted
getting detailed answers like this is more and more cumbersome.
Researchers have worked out a scheme for talking about functions in a much more
high level way while still being completely rigorous but without it getting bogged down
in all the details, and this is the notion of asymptotic growth.
You may have heard it described in the form of Big Oh notation,
and we're going to get to Big Oh in a moment, but we need to start off with Big Theta.
Θ(g(n)) is actually a set of functions, specifically the set of functions that grow
equally quickly as g(n).
To be a bit more formal about it, we say that some function f(n) is in the set
of functions equally fast growing as g(n),
if and only if there are some constants c1 and c2 and some threshold n0
such that for any n bigger than n0, we have something that looks like this--
the function f(n) for all these values of n--all these big values of n--
is sandwiched between c1 * g(n) and c2 * g(n).
To illustrate this idea with a picture imagine we have some function f(n).
It grows. As n gets bigger, f(n) gets bigger.
We also have some function g(n) that we can multiply by c1 or we can multiply
by some bigger number c2.
What we find is that once we get out to the right of some threshold n0
f(n) is always between c2g(n) and c1g(n).
In the beginning maybe weird things happen, but once we get out far enough asymptotically
in the limit as things get really big, f(n) lies between c2g(n) and c1g(n).
If that's the case, if such c1, c2, and n0 exist, then we can say that f(n) is in Θ(g(n)).
前回の格子グラフの分析では
エッジの数の計算式として最終的に得られたのは
2n-2√nでした
何ともやっかいな関数ですが実のところ
こうした分析が複雑になるほど
得られる解答もこのように扱いにくくなっていきます
研究者はもっと高度な形で
関数を説明する方法を考え出しました
やはり難解なものですが
細部にとらわれずに扱えるようになります
漸近的成長という概念です
それはビッグ・オー記法などの形で表されています
ただし先にビッグ・シータ記法から説明しましょう
Θ(g(n))とは関数の集合を表しています
具体的にはg(n)と等しい速さで成長するという関数です
もう少し正確に説明します
ある関数f(n)が
g(n)と成長率の等しい関数の集合に属する
その必要十分条件は
定数c₁、c₂およびある閾値n₀について
n₀より大きなすべてのnにおいて
この大きな値nのすべてに対する関数f(n)は
c₁g(n)≦f(n)≦c₂g(n)となるということです
この概念を図で説明します
ある関数f(n)を考えましょう
nが増加するとf(n)も増加します
さらにある関数g(n)にc₁をかけたものと
より大きなc₂をかけたものもあります
図に示されているように閾値n₀の右側に出ると
f(n)は常にc₂g(n)とc₁g(n)の間にあることが
分かります
始まりは不可解かもしれませんが漸近的に成長して
十分大きな極限になると
f(n)はc₁g(n)とc₂g(n)の間にあるのです
それが成り立ちそうしたc₁、c₂、n₀が存在するなら
f(n)はΘ(g(n))に属すると言えます