人が増えると、なぜ遅くなるのか
友だち10人のグループなら、全員の名前を確かめるのは一瞬です。学校全体の1000人だと、どうでしょう。
手順によっては、人数が10倍になると、仕事も10倍になります。別の手順では、仕事が100倍に増えてしまいます。
このレッスンのゴール
メモ
手順のステップ数が、データの数に対してどう増えるかで、アルゴリズムを比べられる。
重要な言葉
| ことば | いみ |
|---|---|
| ステップ数 | 手順が一回の実行でする、基本の操作の回数 |
| 計算量 | データが増えたとき、ステップ数がどう増えるか |
| ビッグオー | 計算量を O(n) のような形で書く表し方 |
| 線形 | データが2倍になると、ステップ数も2倍になる増え方 |
| 二乗 | データが2倍になると、ステップ数が4倍になる増え方 |
学生が入力するセルは、このプレビューでは空白です。
速さは秒ではなくステップ数で比べる
同じプログラムでも、速いパソコンと古いパソコンでは、かかる秒数が違います。秒数では、手順そのものの良し悪しが分かりません。
そこで、手順が何回「比較」や「足し算」をするかを数えます。ステップ数は、どのパソコンでも同じです。
比較の回数を数える
numbers = [8, 15, 21, 34, 42, 57, 63, 70]
def count_linear(items, target):
steps = 0
for value in items:
steps = steps + 1
if value == target:
return steps
return steps
# 42 は5番目なので、5ステップ
print(count_linear(numbers, 42))
# 99 はないので、全部見て8ステップ
print(count_linear(numbers, 99))
# target を 8 に変えて、何ステップか確かめましょう
ビッグオーで増え方に名前を付ける
データの数を n とします。ステップ数が n に比例して増えるなら、O(n)、「オーダーn」と書きます。線形探索がこれです。
半分ずつ捨てる二分探索は、O(log n) です。log n は、n を何回半分にすると1になるか、という数です。
例：四つの増え方
| 書き方 | 名前 | データが2倍になると | 例 |
|---|---|---|---|
| O(1) | 一定 | ステップ数は同じ | リストの先頭の値を取る |
| O(log n) | 対数 | ステップが1つ増える | 二分探索 |
| O(n) | 線形 | ステップ数が2倍 | 線形探索 |
| O(n²) | 二乗 | ステップ数が4倍 | バブルソート |
学生が入力するセルは、このプレビューでは空白です。
二分探索の最大ステップ数を計算する
docker exec jupyter python3 -c 'print([int(__import__("math").log2(n)) + 1 for n in [10, 100, 1000, 1000000]])'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
データが増えても、あまり増えない
実行の結果は [4, 7, 10, 20] です。データの数が10から100万へ10万倍になっても、二分探索の最大ステップ数は4から20にしか増えません。
ビッグオーは、細かい数ではなく、増え方の形だけを見ます。だから、O(2n) も O(n) と書きます。
全部の組を比べると二乗で増える
n個の値の全部の組を比べる手順を考えます。組の数は、n × (n - 1) ÷ 2 です。バブルソートの比較の回数と同じ形です。
n が10倍になると、組の数はおよそ100倍になります。これが二乗の増え方です。
組の数を計算する
docker exec jupyter python3 -c 'print([n * (n - 1) // 2 for n in [10, 100, 1000]])'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例：データの数と組の数
| データの数 | 組の数 | 10個のときの何倍か |
|---|---|---|
| 10 | 45 | 1倍 |
| 100 | 4950 | 110倍 |
| 1000 | 499500 | 11100倍 |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
ビッグオーが小さいほうが、いつでも速いと考えがちです。ビッグオーが表すのは、データが増えたときの増え方です。データがとても少ないときは、単純な手順のほうが速いこともあります。