ビッグオー記法 (4 min)

今後の一連の動画で、漸近的な記法のフォーマルな扱い、

特にビッグオー記法を、たくさんの例と共に提供したい。

ビッグオー記法は正の整数の関数に関する物だ。
それをT(n)と呼ぼう。

私たちはT(n)の意味について常に同じ認識をするだろう。

アルゴリズムのワーストケースの実行時間が、入力のサイズnのどんな関数となるかを考えていく。

で、問題は、このビデオの残りで答えていきたい問題は、

T(n)がf(n)のビッグオーと言ったら何を意味するのか、という事だ。

言い換えると、ここにある基本的な関数f(n)があるとする。例えばn log nとか。

私はビッグオー記法が本当は何を意味するか、について考えるための、いくつかの考え方を提示するつもりだ。

前菜として、言葉の定義から始めよう。

ある関数がf(n)のビッグオーとはどういう意味か？
それは結局の所、十分に大きな全てのnに対し、

それはf(n)の定数倍を上から抑える。

それを幾つか別の方法で考えてみよう。
この言葉による定義を図に翻訳し、

その後フォーマルな数学に翻訳しよう。

図で表すと、T(n)はこの青い関数で示されると考えられて

f(n)はこの緑の関数で示されると考えられて、

これはT(n)の下に存在している。
だがもしf(n)を二倍にすると、T(n)と交差する関数が得られ

そこから先はこの関数の方が永遠により大きい。
この場合、T(n)はまさに

f(n)のビッグオーだと言える。
その訳は、十分に大きな全てのnに対して

つまり一旦十分にグラフの右側に来れば、

確かにf(n)の定数倍、この場合は二倍が、T(n)の上限となっている。

最後に、実際の数学的な定義を提供しよう。
フォーマルな証明に使う時の為に。

では数学的にはどのように、

結局はf(n)の定数倍にバウンドされなくてはならない、という事を表現出来るのか？
以下のような、2つの定数が存在する事が分かる、

それをcとn0と呼ぼう。
n0より大きな全てのnについて、

T(n)がc * f(n)を越えないような、そんな2つの定数。
つまり、これら2つの定数の役目は、

定数倍と言葉で言った時、十分に大きいと言葉で言った時に

それを定量化する事だ。
cはあきらかにf(n)の定数倍を定量化していて、

n0は十分に大きい、というのを定量化している。
それはそれを越えたら

c掛けるf(n)がT(n)の上限になると主張出来る閾値である。

図に戻ると、cとn0は何にあたるだろう？
cはもちろん、単なる2だろう。

n0は交点、つまり2*f(n)とT(n)が交わる所。

X軸まで垂線を引く。
ここが、この写真でこn0の相対値だ。

以上がフォーマルな定義だ。
ある物がf(n)より大きい事を証明するには、

2つの定数cとn0で、

n0以上の全てのnに対して、c掛けるf(n)がT(n)の上限になっているような物を見つければ良い。

それについての一つの考え方としては、ある関数のビッグオーとなっている何かを作りたい時は、

勝負相手とゲームをしていて、

この不等式が成り立つ事をあなたは示したくて、あなたの勝負相手は

十分大きなnではそれは成り立たない、という事を示さなくてはいけない。
で、あなたが先に定数のcとn0を選ばなくてはいけない。

その後で相手はn0より大きなどんな数を選んでも良い、というゲーム。

その関数がf(n)のビッグオーなら、そしてその時に限り

このゲームに勝てる。
もしあなたが先にc とn0を選んで、相手がどんな大きなnを選んでも

この不等式が成り立つように出来るなら。

もしどうやっても勝ち目が無いなら、それはf(n)のビッグオーでは無い、どんなcとn0を選ぼうと、

相手がいつも、適切な大きい値のnを選ぶ事で、

この不等式をひっくり返せるなら。
最後に一つ、強調しておきたい事がある。

これらの定数は、定数という言葉に込めた意味としては、それらがnと独立である、という事。

この定義を適用し、2つの定数cとn0を選ぶ時は

nがどこにも現れていないのを確認した方が良い。
cは例えば1000とか100万とかかもしれない。

何らかの、nと独立な定数。

ビッグオー記法についてはいくつかの考え方がある。
言葉では、十分に大きな数nに対して

上で縛りたい、という事。
それをどう数学に翻訳するかを示し、

図ではどう表現出来るかを示した。
そしてゲームっぽい理論での考え方を

お見せした。
次のビデオでは、いくつかの例を

見ていこう。