🗺️ アルゴリズムクエスト
STAGE 1 ― 線形探索と計算量 ―
クリア 0 / 9
🧭 地図
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 記法で書くと?

Q3. アルゴリズムの速さを「N が増えたときの手間の増え方」で比べる理由は?

← トップへ