読み方のヒント
矢印ボタン(または ← → キー)でページを移動できます。
アルゴリズムの速さは、データの数nが増えたときに、処理の回数がどのように増えるかで比べます。これをO記法で表します。
| 表し方 | 増え方 | 例 |
|---|---|---|
| O(1) | nに関係なく一定 | 配列の番号で1つ取り出す |
| O(log n) | nが2倍になっても1回増えるだけ | 2分探索 |
| O(n) | nに比例 | 線形探索、最大値を求める |
| O(n log n) | nとlog nの積 | クイックソート(平均) |
| O(n²) | nの2乗に比例 | 選択ソート、バブルソート |
データが10倍になると、O(n)の処理は約10倍、O(n²)の処理は約100倍の時間がかかります。
24 / 30