アルゴリズムの設問でつまずくのは、たいてい「速い／遅いを何で測るのか」と「どの入れ物を使うのか」の2点です。前者の物差しがO記法（オーダー）、後者がデータ構造。この2つは独立ではなく、選んだデータ構造で処理量のオーダーが決まるという関係でつながっています。ここを線でつなぐと、擬似言語を読む速さが変わります。
計算量は秒数ではなく回数で測ります。機械の速さや言語に左右されないよう、入力の個数 n が増えたときに、基本操作の回数がどう伸びるかだけを見る。だから定数倍や小さい項は捨てて、いちばん強く効く項だけを書きます（3n²+5n+8 なら O(n²)）。
O記法 ― nが増えたとき何回になるか
言葉で覚えるより、実際の回数を並べたほうが早いです。n が 10 → 100 → 1000 と増えたときの目安を比べます。
| オーダー | n=10 | n=100 | n=1000 | 典型例 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 配列の添字アクセス／ハッシュ表の探索（平均） |
| O(log n) | 約3 | 約7 | 約10 | 二分探索／平衡した二分探索木の探索 |
| O(n) | 10 | 100 | 1000 | 先頭から全部見る線形探索／合計を求める |
| O(n log n) | 約33 | 約664 | 約9966 | マージソート／ヒープソート |
| O(n²) | 100 | 10000 | 1000000 | 二重ループ／選択ソート・バブルソート |
オーダーの見つけ方は「ループの入れ子の深さを数える」のが基本です。n回まわるループが1つ＝O(n)、その中にもう1つ n回のループ＝O(n²)。ループの中で範囲が毎回半分になっていればO(log n)。さらに、ループの外に置いた処理は何回まわっても増えないので、オーダーには効きません。「いちばん深いところが何回実行されるか」だけを見ます。
入れ子でもいつも O(n²) とは限りません。内側のループが j を i から n まで のように外側に連動して短くなる場合、合計は n(n+1)/2 回＝それでもO(n²)ですが、内側が定数回（例：常に3回）ならO(n)です。内側の回数が n に比例するかどうかを必ず確認してください。
配列と連結リスト ― 添字が速いか、途中挿入が速いか
配列
- 要素が連続して並ぶので、添字から場所を計算できる
- k番目の取り出し：O(1)（一発）
- 途中への挿入・削除：O(n)（後ろを全部ずらす）
- 向く用途：位置指定で頻繁に読む／二分探索の土台
連結リスト
- 各要素が次の要素の位置（ポインタ）を持つ
- k番目の取り出し：O(n)（先頭からたどる）
- 場所が分かっている所への挿入・削除：O(1)（つなぎ替えるだけ）
- 向く用途：並びの途中で出し入れが多い／要素数が読めない
つまりどちらが優れているかではなく、何を速くしたいかです。「k番目を何度も見る」なら配列、「途中に差し込む・抜く」が主なら連結リスト。設問はこのトレードオフを突いてきます。
スタックとキュー ― 出す順番が逆
スタック（LIFO）
後に入れたものが先に出る。入口と出口が同じ側。
操作：push（積む）／pop（取り出す）。関数呼び出しの戻り先管理、深さ優先探索（DFS）。
キュー（FIFO）
先に入れたものが先に出る。入口と出口が反対側。
操作：enqueue（並ぶ）／dequeue（出す）。順番待ちの処理、幅優先探索（BFS）。
深さ優先探索＝スタック（行けるところまで潜り、行き止まりで直前の分岐に戻る＝最後に積んだものから戻る）。幅優先探索＝キュー（近い順に全部見てから次の層へ＝先に見つけた候補から処理する）。だから最短手数を求める探索はキュー（BFS）が基本になります。再帰で書いた深さ優先探索は、内部でスタックを使っているのと同じことです。
木と二分探索木 ― 高さが log n なら速い
左の子＜親＜右の子。1回の比較で候補が半分になる（50を見て、40なら左だけ残る）
二分探索木は「左の子は親より小さい、右の子は親より大きい」を全ノードで守る木です。根から比べていけば1段下りるたびに候補が半分になるので、探索は木の高さに比例します。バランスの取れた木なら高さは約 log₂n＝n=1000でも10回ほどで見つかります。
二分探索木はいつも O(log n) ではありません。すでに昇順に並んだデータを順に挿入すると、右へ右へ一直線に伸びて連結リストと同じ形になり、探索はO(n)に劣化します。これを防ぐため、挿入・削除のたびに木の形を組み替えて左右の高さの差を一定以内に保つのが平衡（バランス）木です。「最悪の場合の計算量」を問われたら、この偏りを疑ってください。
ハッシュ表 ― 鍵から位置を計算する
探索を速くするもう一つの道がハッシュ表です。木のように「比べて絞る」のではなく、鍵をハッシュ関数に入れて格納位置を直接計算します。比較しないので、うまく散っていれば平均 O(1)。位置さえ出れば一発で届きます。
| 操作 | 配列（未整列） | 二分探索木（平衡） | ハッシュ表 |
|---|---|---|---|
| 探索 | O(n) | O(log n) | 平均 O(1)／最悪 O(n) |
| 挿入 | O(1)（末尾） | O(log n) | 平均 O(1) |
| 順番に取り出す | 要ソート O(n log n) | O(n)（そのまま昇順） | 不得意（順序を持たない） |
違う鍵から同じ位置が計算されることがあり、これを衝突（コリジョン）と呼びます。処理の仕方は大きく2つ。チェイン法＝同じ位置に来たものを連結リストでぶら下げる。オープンアドレス法＝空いている別の位置を順に探して入れる。どちらも衝突が増えるほど「たどる回数」が伸びるので、詰まりすぎ（使用率が高い）と平均O(1)が崩れ、最悪はO(n)になります。だから表は余裕を持った大きさにし、散らばりの良いハッシュ関数を選びます。
試験での使い方 ― 読み方の手順
擬似言語の問題は、次の2手で機械的に崩せます。①ループの入れ子の深さを数える：いちばん内側の行が何回実行されるかだけを見て、n・n²・log n のどれかに当てはめる。②トレース表を書いて変数の遷移を追う：n を3〜5程度の小さい値に置き換え、変数を列に並べて1行ずつ値を書き下す。空欄補充も「その行を通ったとき何が成り立っていればよいか」が表から見えます。頭の中で追わず、必ず紙に表を書くのが最短です。
トレース表は、ループ変数と作業用変数を列に取り、1周ごとに1行を足していきます。
| 周回 | i | a[i] | 最大値 | 判定（a[i] > 最大値） |
|---|---|---|---|---|
| 開始 | ― | ― | a[1]=3 | ― |
| 1周目 | 2 | 7 | 7 | 真 → 更新 |
| 2周目 | 3 | 5 | 7 | 偽 → 据え置き |
| 3周目 | 4 | 9 | 9 | 真 → 更新 |
設問が「処理時間はどうなるか」「データ件数が10倍になったら」と聞いてきたら、それはオーダーを答えさせる問いです。O(n)なら約10倍、O(n²)なら約100倍、O(log n)ならほとんど変わらない、と換算できます。逆に「改善案」を問われたら、線形探索を二分探索やハッシュ表に置き換える、二重ループを1回のループ＋表引きに畳む、が定番の方向です。