クエストを選ぼう!
ステージ1から順番にクリアしよう(前のステージをクリアすると次が解放されます)
1
線形探索と計算量
名簿を前から順に調べると何回比べる? 手間の増え方で速さを測る O 記法を定義する。
はじめる →2
二分探索
並んだ名簿なら、真ん中と比べて半分を捨てられる。1000人でも10回で見つかる理由と log の意味。
はじめる →3
ハッシュ表
名前から棚の番号を計算して、その棚だけを見る。衝突と負荷率、得意なことと苦手なこと。
はじめる →4
バブルソート
隣どうしを比べて大きいほうを右へ。バブルソートを1手ずつ動かし、比べる回数 N(N−1)/2 を数える。
はじめる →5
クイックソート
基準より小さいか大きいかで2つに分け、それぞれを同じやり方で。平均 O(N log N) と、並んだ入力での最悪 O(N²)。
はじめる →6
キューと幅優先探索
先に並んだものから取り出すキューで、スタートから近い順に町を調べる。最少の歩数が求まる理由。
はじめる →7
ダイクストラ法
道に長さがあるときは、まだ確定していない町のうち一番近いものから確定する。道の長さ0以上という条件の意味。
はじめる →8
再帰と動的計画法
階段の上り方を再帰で素直に書くと、同じ計算をくり返して爆発する。表に書いて使い回せば n 回。
はじめる →9
計算量で選ぶ
ここまでの手順を計算量で並べ、N を増やして差を見る。速いアルゴリズムの見つけ方と、データ構造の選び方。
はじめる →