計算量とは、手数の増え方
計算量とは、データが増えたときに、アルゴリズムの手数がどれだけ増えるかを表す言葉です。
これが分かると、プログラムを動かす前に、遅くなるかどうかを見抜けます。客が千人の店のレジが、百万人の店でも使えるのか。その答えは、手数を数えれば出ます。
このレッスンのゴール
メモ
アルゴリズムのステップ数を数えて、その増え方を一定、線形、2乗、対数のどれかで言える。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| アルゴリズム | 問題を解く手順。決まった順に行う | |
| ステップ | 手順の中の、1回の比較や1回の足し算 | |
| 入力の大きさ | データの個数。ふつう n と書く | n = 1000 |
| 計算量 | n が増えたとき、ステップ数がどう増えるか | |
| 線形 | n が2倍なら、ステップ数も2倍になる増え方 | |
| 対数 | 2で割り続けて1になるまでの回数に近い増え方 |
学生が入力するセルは、このプレビューでは空白です。
手数はステップで数える
同じ手順でも、速いパソコンと遅いパソコンでは、かかる秒数が違います。だから秒数では、手順そのものを比べられません。
そこで、ステップを数えます。1回の比較、1回の足し算を、1ステップとします。ステップの数は、どのパソコンでも同じです。
値段5個の最大値探し
| 何をするか | 比べる回数 | 合計 |
|---|---|---|
| 最初の値段 120 を、暫定の最大とする | 0回 | 0 |
| 80 と 120 を比べる | 1回 | 1 |
| 300 と 120 を比べる | 1回 | 2 |
| 45 と 300 を比べる | 1回 | 3 |
| 210 と 300 を比べる | 1回 | 4 |
学生が入力するセルは、このプレビューでは空白です。
比べた回数を数える
# 一番高い値段を探しながら、比べた回数を数えます。
prices = [120, 80, 300, 45, 210]
best = prices[0]
steps = 0
for i in range(1, len(prices)):
steps = steps + 1
if prices[i] > best:
best = prices[i]
print("一番高い値段:", best, "比べた回数:", steps)
# prices の数を2倍の10個にして、もう一度実行しましょう。回数はどうなりますか。
増え方には名前がある
n 個のデータに対して、ステップ数は大きく4つの増え方に分かれます。
一定は、n が増えても変わりません。線形は、n と同じだけ増えます。2乗は、n かける n です。対数は、n を2で割り続けて1にする回数で、とてもゆっくり増えます。
n が増えたときのステップ数
| 増え方 | 式 | n = 10 | n = 100 | n = 1000 |
|---|---|---|---|---|
| 一定 | 1 | 1 | 1 | 1 |
| 対数 | 2で割る回数 | 4 | 7 | 10 |
| 線形 | n | 10 | 100 | 1000 |
| 2乗 | n かける n | 100 | 10000 | 1000000 |
学生が入力するセルは、このプレビューでは空白です。
ラボの端末で増え方を確かめる
下の Run は、あなたのラボの端末で動きます。seq は1から1000まで1行ずつ出し、wc -l は行の数を数えます。
線形の増え方は、1000個なら1000ステップです。2乗は、その1000倍を掛けるので百万になります。
1000行を数える
seq 1 1000 | wc -lここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
二重ループの回数
python3 -c "print(1000 * 1000)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
百万を2で割れる回数
python3 -c "import math; print(math.ceil(math.log2(1000000)))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
計算量は、実行にかかる秒数だと思いがちです。time で測る秒数は、機械が変わると変わります。計算量は、n が増えるときのステップ数の増え方です。機械には左右されません。
2で割る回数を数える
# 1000 を2で割り続けて、1になるまでの回数を数えます。
n = 1000
steps = 0
while n > 1:
n = n // 2
steps = steps + 1
print("割った回数:", steps)
# n を 2000 にして実行しましょう。回数は1つしか増えません。
さらに挑戦: 三重ループ
課題が通ったら、三重ループが何回まわるかを考えましょう。n = 10 のとき、n かける n かける n で千回です。
n が2倍になると、ステップ数は何倍になりますか。2乗の場合と比べて、自分の言葉で説明しましょう。