STAGE 1
線形探索と計算量
前から順に調べると、何回かかる?
🎯 ミッション
線形探索の比較回数と、O 記法(計算量)の意味を説明できるようになろう。3つの人数で探して比べ、確認クイズに全問正解すれば合格。
未達成

ねこ博士
この旅で解きたい問題から話そう。ある村の村長が困っている。村の名簿には1万人が載っていて、毎日「○○さんはいますか」と聞かれる。村が大きくなって、いずれ100万人になったら、今のやり方では1日が終わってしまう、と。

うさ美
今のやり方というのは?

ねこ博士
名簿の1ページ目から、1人ずつ名前を見比べていく。これを線形探索と呼ぶ(線のように端から順にたどるから)。
この旅で解きたい問題
分かっているもの:コンピュータは1回の比較や足し算をとても速くこなせる。でも、データの数が増えると、手間の増え方しだいで現実的な時間に終わらなくなる
知りたいもの:同じ答えを、もっと少ない手間で出す手順(アルゴリズム)の作り方。そして、手順の速さを比べる物差し
道順:物差し=計算量(1)→ 探す(2〜3)→ 並べる(4〜5)→ 道を探す(6〜7)→ 同じ計算を省く(8)→ まとめ(9)

ねこ博士
アルゴリズムというのは、問題を解くための、誰がやっても同じ結果になる手順のことだ。料理のレシピのように、1つ1つの手順がはっきり決まっている。では、線形探索で N 人の名簿から1人を探すとき、比べる回数は何回かな。

うさ美
運がよければ1人目で見つかるので1回。運が悪ければ最後の人か、名簿にいない場合で N 回。いない人を探すときは、全員を見ないと「いない」と言えないので、必ず N 回です。

ねこ博士
そう。アルゴリズムの速さを考えるときは、ふつう一番運が悪い場合(最悪の場合)を考える。「どんなに運が悪くても、これだけあれば終わる」と約束できるからね。ならした平均(平均の場合)を考えることもある。線形探索の平均はどのくらい?

うさ美
名簿のどこにいるかが均等なら、真ん中あたりで見つかることが多いので、だいたい N の半分です。

ねこ博士
村長が1人と見比べるのに3秒かかるとしよう。100万人の名簿だと、最悪でどのくらいかかるかな。

うさ美
100万 × 3 = 300万秒。1日は 86400 秒だから、約35日。コンピュータならずっと速いですけど、人数に比例して遅くなることは変わらないですね。

ねこ博士
そこで大事なのが、「1回が何秒か」ではなく、N が増えたときに手間がどう増えるかという見方なんだ。コンピュータを10倍速くしても、手間の増え方が変わらなければ、N が10倍になったら元通りだ。

ねこ博士
この「増え方」を表す書き方が O 記法(オーダー記法)だ。線形探索の手間は、最悪で N 回、平均で N の半分。どちらも「N に比例して増える」。こういうとき、細かい係数(半分、3秒など)は気にせずに O(N) と書いて「オーダー N」と読む。
O 記法:N が大きくなったときに、手間が N の何に比例して増えるかだけを書く。係数や、小さい項は無視する
例:3N + 5 回 → O(N) / N ÷ 2 回 → O(N) / N × N 回 → O(N²) / N によらず10回 → O(1)
この手間の増え方を計算量(時間計算量)と呼ぶ。線形探索は O(N)

うさ美
係数を無視していいんですか? 3N と N では3倍違うのに。

ねこ博士
N が小さいうちは係数も効く。でも N が大きくなると、増え方の違いのほうがずっと大きくなる。たとえば、100N 回かかる手順と、N × N 回かかる手順。N が 10 なら、どちらが速い?

うさ美
100×10=1000 回と、10×10=100 回。N × N のほうが速い。でも N が 1000 なら、10万回と100万回で、100N のほうが速くなる。N が 100 を超えたら、ずっと 100N のほうが速いままですね。

ねこ博士
そう。データが多いときに勝つのは、増え方の小さいほうなんだ。だから、手順を比べるときは、まず O 記法で増え方を比べる。次のステージでは、村長の名簿が「五十音順に並んでいる」ことを使って、O(N) よりずっと増え方の小さい探し方を作ろう。
確認クイズ
Q1. N 人の名簿に、探している人がいない場合、線形探索で比べる回数は?
正解! いないことを確かめるには、全員を見るしかない。これが線形探索の最悪の場合。
Q2. 手間が「2N + 10 回」の手順の計算量を O 記法で書くと?
正解! 係数の2や、足された10は無視して、N に比例することだけを書く。
Q3. アルゴリズムの速さを「N が増えたときの手間の増え方」で比べる理由は?
正解! 機械を速くしても増え方は変わらない。N が大きくなるほど、増え方の小さい手順が勝つ。