| English | 意味 |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | アルゴリズム効率 |
| slow/sləʊ/ | 遅い |
| steps/steps/ | 手順 |
| reasonable/ˈriːzənəbl/ | 妥当な |
| unreasonable/ʌnˈriːzənəbl/ | 妥当でない |
| heuristic/hjuːˈrɪstɪk/ | ヒューリスティック |
正しいだけでは不十分な場合もある
- 2つのアルゴリズムがどちらも正しいにもかかわらず、一方の方がはるかに使い勝手が良いことがあります。
- アルゴリズム効率は、アルゴリズムが消費するリソース（主に時間とメモリ）によって比較されます。
- 正しいが遅いアルゴリズムは、大きな入力に対して無用であることがあります。
- そのため、スケールへの対応を比較する方法が必要です。
アルゴリズム効率性はアルゴリズムを以下のように比較します：
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
効率は、入力が増加するにつれて時間とメモリの関係です。
nが増加するにつれてステップを数える
- 入力の大きさ$n$が増加する際の、アルゴリズムが必要とするステップの数を推定します。
- 線形探索は約$n$のステップを要し、二項探索は約$\log_2 n$、全ペアの比較は約$n^2$を要します。
- $n$ が大きくなると、これらの違いは巨大になります。
- ストップウォッチよりも、成長の形状の方がはるかに重要です。
実行時間がnにどう依存して増加するか
スライド n を重ねて曲線を比較します：log n はほぼ横ばい、n は着実に上昇、n² は爆発的に増加します。これが、クロノメーターではなくスケール性を基準にアルゴリズムを比較する理由です。
各アルゴリズムを入力サイズ n に対するおおよそのステップ数に対応させなさい。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
これらの成長率がどのアルゴリズムがスケールできるかを決定します。
n が大きくなるにつれて、どの成長が不合理と見なされますか？
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
指数関数的成長は非常に速く非現実的になります。
正確な答えを出すのに時間がかかりすぎる場合、______ が十分良い解を素早く見つけます。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
ヒューリスティックは完璧な答えと引き換えに速度を提供します。
妥当 vs 不適切
- 私たちは妥当な実行時間と不適切な実行時間を区別します。
- およそ、$n$ や$n^2$のような成長は妥当であり、追加のアイテムごとにステップが倍増する（$2^n$のような）ものは不適切です。
- 正確な答えが非常に時間がかかる場合は、ヒューリスティックを使用します——速く見つけられた、十分許容できる解です。
- 完璧ではありませんが、完璧な解が時間内に得られない場合に有用です。
1,000,000 個の整列済み要素の二項探索には最大で約何ステップ必要か？ (2^20 ≈ 百万)
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
2^20 が百万をわずかに超えるため、~20 回の半減で十分である。
正しいアルゴリズムでも、大きな入力では使用に耐えられないほど遅いことがあります。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
また、合理的な時間で完了也必须ある必要があります。
実用上に遅すぎる
- これが、大きな入力に対して実際には実行できないほど遅い、正しいアルゴリズムがある理由です。
- 正しいだけでは不十分です——アルゴリズムもまた、妥当な時間で終了する必要があります。
百万個のアイテム。 1,000,000個のソート済みアイテムに対する線形探索は、最大で1,000,000ステップかかることがあります。一方、二分探索は最大でも約20ステップで済み、$2^{20}$は百万をわずかに超えるためです。小規模なリストでは差はほとんど気になりませんが、百万個のアイテムに対しては、二分探索が唯一現実的な選択肢となります。
アルゴリズムの効率性は、入力サイズ $n$ が増加するにつれてリソース比較によりアルゴリズムを評価します：線形 $n$、二分探索 $\log_2 n$、全ペア ⟨$n^2$。$n$ や $n^2$ のような成長は妥当と見なされますが、$2^n$ は非現実的です（ヒューリスティックを使用）。大規模な入力に対してあまりにも遅い正しいアルゴリズムでは不十分です。