コンピュータを速くするより、手順を変えるほうが効く。

100万人の名簿から1人を探す。前から順に調べれば最悪100万回、並んでいれば20回、名前から棚を計算すれば1回。同じ答えでも、手順しだいで手間は何万倍も変わる。手間の増え方を測る物差し「計算量」を手に入れて、探す・並べる・道を探す・同じ計算を省く、の4つの仕事で、速い手順がなぜ速いのかを、自分の手で数えて確かめよう。

クエストを選ぼう!

ステージ1から順番にクリアしよう(前のステージをクリアすると次が解放されます)

1
計算量⏱ 約12分
線形探索と計算量

名簿を前から順に調べると何回比べる? 手間の増え方で速さを測る O 記法を定義する。

はじめる →
2
二分探索⏱ 約12分
二分探索

並んだ名簿なら、真ん中と比べて半分を捨てられる。1000人でも10回で見つかる理由と log の意味。

はじめる →
3
ハッシュ表⏱ 約13分
ハッシュ表

名前から棚の番号を計算して、その棚だけを見る。衝突と負荷率、得意なことと苦手なこと。

はじめる →
4
ソート⏱ 約12分
バブルソート

隣どうしを比べて大きいほうを右へ。バブルソートを1手ずつ動かし、比べる回数 N(N−1)/2 を数える。

はじめる →
5
分割統治⏱ 約14分
クイックソート

基準より小さいか大きいかで2つに分け、それぞれを同じやり方で。平均 O(N log N) と、並んだ入力での最悪 O(N²)。

はじめる →
6
BFS⏱ 約13分
キューと幅優先探索

先に並んだものから取り出すキューで、スタートから近い順に町を調べる。最少の歩数が求まる理由。

はじめる →
7
最短経路⏱ 約15分
ダイクストラ法

道に長さがあるときは、まだ確定していない町のうち一番近いものから確定する。道の長さ0以上という条件の意味。

はじめる →
8
動的計画法⏱ 約14分
再帰と動的計画法

階段の上り方を再帰で素直に書くと、同じ計算をくり返して爆発する。表に書いて使い回せば n 回。

はじめる →
9
まとめ⏱ 約10分
計算量で選ぶ

ここまでの手順を計算量で並べ、N を増やして差を見る。速いアルゴリズムの見つけ方と、データ構造の選び方。

はじめる →