道 2
アルゴリズムとは
- 問題を解くための、決まった手順のことです。
- どの手順も、順次、分岐、反復の 3 つの形で書けます。
- 同じ問題でも手順しだいで速さが大きく変わり、100 万件から探すのに 100 万回かかる手順と 20 回で済む手順があります。
探す、並べる、しまう、たどる。動きを可視化で見て、比べた回数を測り、面接の問題と基本情報の過去問で確かめます。
- 前提
- 道 1 の計算量の回 (for が書ければ読めます)
- 回
- 11 回 (今すぐ学べる 11 回)
- 最後に
- 基本情報 科目B と面接問題で確かめる
文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日
石 1 つが 1 回です。ログインすると、つないだコースのレッスンを全部済ませた回の石が緑に変わり、次に読む回に色が付きます。薄い石は準備中の回です。この道の回
2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順修了の条件身近な手順を、3 つの形だけで書き直せる学べる 2-1線形探索と二分探索100 万件でも 20 回で見つかる修了の条件データが 1,000 倍になっても、二分探索で真ん中を見る回数が 10 回しか増えない理由を説明できる学べる 2-2遅いソート 3 つ挿入、選択、バブル修了の条件データが 2 倍で比べる回数が約 4 倍になることを、測った数で示せる学べる 2-3速いソート 2 つマージ、クイック、平均と最悪修了の条件クイックソートが遅くなる並びを 1 つ作って見せられる学べる 2-4スタックとキュー積む順と並ぶ順修了の条件元に戻す機能がスタックで作れる理由を説明できる学べる 2-5再帰自分を呼んで小さくする修了の条件再帰の呼び出しが積み上がる様子を、紙に書いて追える学べる 2-6木と二分探索木たどる順、片寄り修了の条件片寄った木が遅くなる様子を、可視化で再現できる学べる 2-7ハッシュ表鍵から一気に引く、衝突修了の条件衝突が多いと遅くなる理由を、実際に起きた事例で説明できる学べる 2-8グラフと最短経路幅優先、深さ優先、ダイクストラ修了の条件乗り換え案内のような問題を、点と線に直して解ける学べる 2-9動的計画法同じ計算を 2 度しない修了の条件素直な再帰が遅い理由と、表に残すと速くなる理由を説明できる学べる 2-10試験と面接で確かめる基本情報 科目B、道場 10 問、面接 20 問修了の条件見たことのない問題を、計算量を言いながら 30 分で解ける学べる
回 2-0 この頁で読む回
アルゴリズムとは
読み終えたら身近な手順を、順次、分岐、反復の 3 つの形だけで書き直せる。
1 問い
480 円、320 円、650 円、299 円、410 円の 5 つの値段から、いちばん安い物を見つけてください。目で見ればすぐですが、その見つけ方を、知らない人に 1 行ずつ渡せる形で書けますか。
2 仕組み
アルゴリズムとは、問題を解くための決まった手順のことです。どんな手順も、次の 3 つの形の組み合わせで書けます。
- 順次。上から順に 1 つずつ進む。「最初の値段を、今いちばん安い値段として覚える」
- 反復。同じことを繰り返す。「残りの値段を 1 つずつ見る」
- 分岐。条件で道を分ける。「見た値段が覚えている値段より安ければ、覚え直す」
料理のレシピや、乗り換え案内が経路を探す手順も、この 3 つで書けばアルゴリズムです。プログラミングは、その手順をコンピュータが読める言葉で書くことです。
3 動かす
上の手順をそのままコードにしました。実行すると 299 が出ます。値段を足したり変えたりして、もう一度実行してください。
4 測る
この手順は、最初の値段を覚えたあと、残りの値段を 1 回ずつ見て比べます。値段の数を 5 個、10 個、1,000 個と変えて、比べた回数を数えてみます。値段の並びは実行ごとに混ぜますが、比べた回数はいつも値段の数より 1 少なくなります。
データが 2 倍になると、回数もほぼ 2 倍になる。この増え方を O(n) と書きます。次の回 2-1 では、データが 1,000 倍になっても、真ん中を見る回数が 10 回しか増えない手順を測ります。
5 説明
次の 3 つに、自分の言葉で 1 行ずつ答えてから、次の回へ進んでください。
- 朝起きてから家を出るまでの手順の中で、反復と分岐はどこにありますか
- いちばん高い値段を探すには、上のコードのどこを変えますか
- 値段が 100 万個あるとき、この手順は何回比べますか
答えの例2 つ目は if の不等号の向きを p > cheapest に変えます (名前も cheapest から highest に変えると読みやすくなります)。3 つ目は 999,999 回です。最初の 1 つは覚えるだけで、残りの値段と 1 回ずつ比べるので、値段の数より 1 少なくなります。
この道につながる実例
ほぼすべての二分探索に潜んでいた整数の上限越え
2006年6月2日に公表
広く使われていた Java の二分探索で、真ん中の位置を (low + high) / 2 で求める式が、とても大きな配列のときに整数の上限を超え、負の数になっていました。道 1 の 2 進数と、道 2 の二分探索がつながる例です。
Google Research Blog (英語)ハッシュの衝突を狙って Web サーバーを止める
2011年12月28日に公表
多くの言語のハッシュ表で、狙って衝突させる鍵を大量に送ると表への出し入れが極端に遅くなり、Web のサービスが止まり得ると公表されました。ハッシュ表の最悪の計算量が、そのまま障害になった例です。
oCERT-2011-003 (英語)よくある問い
アルゴリズムとは何ですか
問題を解くための、決まった手順のことです。どの手順も、上から順に進む (順次)、条件で道を分ける (分岐)、同じことを繰り返す (反復) の 3 つの組み合わせで書けます。料理のレシピや乗り換え案内の経路の探し方も、手順として書けばアルゴリズムです。
データ構造とは何ですか
データのしまい方です。並べてしまう配列、上に積むスタック、鍵で引くハッシュ表、枝分かれする木などがあります。同じアルゴリズムでも、しまい方で速さが大きく変わるので、2 つは組で学びます。
計算量とは何ですか
データが増えたときに、手順の回数がどう増えるかの見積もりです。O(n) はデータが 2 倍で回数も 2 倍、O(n²) は 2 倍で 4 倍、O(log n) は 2 倍で 1 回増えるだけ、を表します。この道では、比べた回数を実際に数えて確かめます。
数学が苦手でも学べますか
学べます。この道で使う数は、足し算、掛け算、2 の累乗だけです。式で証明する代わりに、データを倍にして比べた回数を数え、増え方を数で見ます。
ヒューリスティックとは何が違いますか
アルゴリズムは決まった手順で、いつも同じ答えに着きます。ヒューリスティックは、いつも最善とは限らないが十分に良い答えを早く出す、経験に基づく近道です。
SNS のアルゴリズムとは何のことですか
SNS で言うアルゴリズムは、どの投稿を誰の画面のどの順に出すかを決める手順のことです。並べ替えと絞り込みの手順なので、この道のソートと探索の考え方につながっています。
どのくらいで身につきますか
つないだコースの目安は、アルゴリズム基礎が約 4.5 時間、データ構造とアルゴリズム応用が約 4.5 時間です (2026年10月26日のコースの頁の値)。面接の問題と過去問で確かめる時間は人によって変わります。
