同じ答えでも、早さはちがう
駅から学校まで、行き方が二つあります。どちらも、着く場所は同じです。でも、かかる時間は、ちがいます。
プログラムも同じです。同じ答えを出す手順が、いくつもあります。今日は、どちらが早いかを、回数で比べます。
今日のキーワード
| ことば | いみ | れい |
|---|---|---|
| アルゴリズム | 問題を解くための、手順のことです。 | 順番に探す手順 |
| 手間 | 手順を終えるまでに、かかる作業の量です。 | 要素を見た回数 |
| 比べる回数 | 手間の目安として、数をくらべた回数を数えます。 | items[i] == target を調べた回数 |
| 最悪の場合 | 一番、手間がかかる場合です。 | 探す値が、ないとき |
| データの数 | 手順に渡す、データの個数です。手間は、これで大きく変わります。 | リストの長さ n |
学生が入力するセルは、このプレビューでは空白です。
時間ではなく、回数で比べる
実行にかかった秒数は、パソコンやスマホによって変わります。だから、「何回、比べたか」で数えます。
回数なら、どの機械でも同じです。さらに、データが多くなったとき、どう増えるかも見えます。
やってみよう: 順番に探す回数
def linear_checks(items, target):
count = 0
for item in items:
count = count + 1
if item == target:
break
return count
# 一番後ろにある値を、探します。最悪の場合です。
for n in [10, 100, 1000]:
items = list(range(1, n + 1))
print(n, "個:", linear_checks(items, n), "回")
例: 探す手間の比べ
| データの数 | 順番に探す(最悪) | 半分ずつ探す(最悪) |
|---|---|---|
| 10 | 10回 | 4回 |
| 100 | 100回 | 7回 |
| 1000 | 1000回 | 10回 |
| 10000 | 10000回 | 14回 |
学生が入力するセルは、このプレビューでは空白です。
小さな確認: 探す手間
やってみよう
小さな確認: 探す手間
3問挑戦してみましょう。回答はここで採点され、その後は保存されません。点数を残したい場合や、続きから再開したい場合はログインしてください。ログインして点数を保存
答えはここで採点され、保存されません。アカウントがあれば、結果が残ります。
やってみよう: 並べかえの回数
def sort_checks(n):
items = []
for k in range(n):
items.append(n - k)
count = 0
for i in range(n):
best = i
for j in range(i + 1, n):
count = count + 1
if items[j] < items[best]:
best = j
temp = items[i]
items[i] = items[best]
items[best] = temp
return count
for n in [5, 10, 20, 40]:
print(n, "個:", sort_checks(n), "回")
例: 選択ソートの比べる回数
| データの数 | 比べる回数 | 前の行の何倍か |
|---|---|---|
| 5 | 10回 | (なし) |
| 10 | 45回 | およそ4.5倍 |
| 20 | 190回 | およそ4.2倍 |
| 40 | 780回 | およそ4.1倍 |
学生が入力するセルは、このプレビューでは空白です。
二倍になると、四倍に近くなる
重要
選択ソートは、データが2倍になると、比べる回数が、およそ4倍になります。順番に探す方法は、2倍になると、回数も2倍です。並べかえのほうが、増え方が激しいことがわかります。