はやさを はかる ものさし

かいすうを かぞえる

びょうで はかると まよいます。
はやい コンピューターでは
おそい ほうほうも はやく 見えます。
だから びょうの かわりに
「何かい はたらくか」を かぞえます。
ますが n こ の とき
ほうほう ごとに
はたらく かいすうが ちがいます。

入力の 大きさを えらんで、ほうほう ごとの かいすうを かぞえます。(一つずつ = n かい · 半分ずつ = 少ない)

ますが 少ない ときは
二つが にて 見えます。
8ますなら
一つずつ 8かい、
半分ずつ 3かい。
たいした さは ない。
でも ますを どっと ふやすと
どう なるでしょう?

大きく すると どう なる

ここで ほんとうが 見えます。
n を 大きく すると
ある ほうほうは
ますの ぶん ゆっくり ふえ、
ある ほうほうは
ますが 二ばいだと
仕事が 四ばいに とびます。
n かける n、
それが n二じょうです。

n を おして 大きく してみましょう。n は ますの ぶん ふえますが、n二じょうは ますが 大きく なるほど ばくはつ するように ふえます。

n二じょうが こわいのは
ますが 大きい ときです。
100ますなら
n は 100、
n二じょうは 10000。
1000ますなら
n は 1000、
n二じょうは 百まんです。
小さく はじまっても
すぐ 手に おえなく なります。

カーブを くらべる

三つの そだちを
ならべると
ひと目で 見えます。
log n は
ますが 大きく なっても
ほとんど 上がりません。
n は ななめに まっすぐ、
n二じょうは 上へ そって
はるか 上に つきぬけます。

カーブを おして つけて くらべます。同じ n でも log n・n・n二じょうの たかさは まるで ちがいます。

もう わかりますね。
半分ずつ きるのが
なぜ あんなに はやかったか。
半分ずつは log n、
ますが 千こ でも
十かいで おわります。
一つずつは n、
千こ なら 千かい。
そだつ かたちが
しょうぶを わけたのです。

大きな こうだけ のこす

じっさいの かいすうを かぞえると
3n二じょう+5n+9 のように
しきが ごちゃごちゃです。
でも n が とても 大きく なると
n二じょうが ほかを
ぜんぶ 上まわります。
だから 小さな こうは けして
いちばん 大きく そだつ
n二じょうだけ のこします。

小さな こうを おして 一つずつ けします。3n二じょう+5n+9 で n が 大きいと n二じょうだけ のこり、それが ビッグオー(O)です。

まえの すうじも けします。
3n二じょうでも 100n二じょうでも、
そだつ かたちは 同じ n二じょうですから。
だから ただ
O(n二じょう)と かきます。
ビッグオーは「大きな ますで
どんな かたちで そだつか」を
一ぎょうで かいた なふだです。

ここまで きました

まとめると こうです。
はやさは びょうでは なく
そだつ かたちで はかります。
ます n が 大きく なる とき
log n は ほとんど ふえず、
n は ますの ぶん、
n二じょうは ばくはつ。
しきが ふくざつでも
大きな こう 一つだけ 見れば よく、
その しるしが ビッグオーです。

三つを おして 一ぎょうに まとめます。log n は ほぼ たいら、n は ななめ、n二じょうは 上へ ばくはつ。大きな こうだけ 見れば いいです。

もう ほうほうを 見れば
びょうを はからなくても
はやいか みつもれます。
ますが 二ばいの とき
仕事も 二ばいなら いい、
四ばいに とんだら ようちゅうい。
よい ほうほうは
大きな しごとの まえでも
ゆっくり そだつ ほうほうです。