女性向けエンジニアスクール
3秒でわかる
問題を解く手順を、誰がなぞっても同じ結果になるように定めたもの。同じ答えを出す処理でも、手順しだいで所要時間が桁違いに変わります。
30秒図解
もう少し詳しく
どういうものか
入力を受け取って答えを出すまでの手順を、あいまいさなく並べたもの。「有限の手数で必ず終わる」「同じ入力なら同じ結果になる」という 2 つの性質が備わっていることが条件になる。プログラムは、このアルゴリズムを特定の言語の文法に翻訳したものにすぎない。
同じ「並んだ数値から目的の値を探す」という問題でも、先頭から順に見ていく線形探索と、真ん中と比べて半分を捨てる二分探索では手順がまったく違う。どちらも正しい答えを出すが、要素が 100 万件あるとき、前者は最悪で 100 万回の比較を要し、後者は 20 回ほどで終わる。手順の違いが、そのまま待ち時間の違いになる。
なぜ必要か
データが少ないうちは、どんな書き方でも一瞬で終わる。差が出るのは件数が増えたときで、手順の選び方が処理時間の伸び方そのものを決める。要素数 n に対して計算量が n で伸びるのか、n の 2 乗で伸びるのかを見積もる考え方が計算量であり、アルゴリズムを学ぶ実用的な目的はここにある。
具体例
同じ「重複を取り除く」処理を 2 通りで書いた例。
# 手順A 1件ずつ既出リストと突き合わせる 計算量は n の2乗
def uniq_slow(items):
result = []
for x in items:
if x not in result: # ここで result 全体を走査している
result.append(x)
return result
# 手順B 見たものを集合に記録する 計算量は n に比例
def uniq_fast(items):
seen = set()
result = []
for x in items:
if x not in seen: # 集合の判定は平均して一定時間
seen.add(x)
result.append(x)
return result出力は同じだが、10 万件を渡すと手順 A は数秒かかり、手順 B は一瞬で返る。
つまずきやすいところ
計算量の記号を、実際の秒数だと思い込むこと。O(n) は「n が 2 倍になれば時間もおよそ 2 倍」という伸び方の話で、絶対的な速さではない。件数が 10 件程度なら 2 乗の手順のほうが速いこともある。
もう 1 つは、正しさの確認を最大ケースだけで済ませること。空の入力、要素が 1 件、全部同じ値、といった端のケースで落ちるアルゴリズムは多い。
覚え方
レシピと同じで、材料と手順が同じなら誰が作っても同じ料理になる。違うのは、下ごしらえの段取りしだいで完成までの時間が変わるところ。
