はじめに
Paizaの問題で実行時間オーバーで突破できない問題が出てきてしまい、悔しいのでアルゴリズムを勉強しようと思い立ち、「問題解決のためのアルゴリズムx数学が基礎からしっかり身につく本」で勉強中。学びをメモ程度でもアウトプットしてまとめたいので書く。
今回は計算量について、その見積もり、について学んだことを書いていく。
目次
1.計算量とは
2.定数時間
3. 線形時間
4. 全探索
5. まとめ
1. 計算量とは
結論、答えにたどり着くまでの計算回数。
ただし正確に何回と求めるわけではなく、「ざっくりN回」って感じで求める。よくO(N) のランダウ記法で見かけるよね。
2. 定数時間
例えば「1+1は？」のように「ざっくり1回の計算」のようなものは定数時間。O(1) の記法でよく見ますね。
下記の例題は入力の処理と計算し出力の処理で正確に1回ではないがざっくり1回なんで定数時間です。
(例)
「整数Nが入力として入った時$2N+1$の答えは何ですか？」
N = int(input())
print(2*N+1)
3. 線形探索
一言でいうと「for１個で済む処理」
(例)
「$1 \leqq N \leqq 100$までで$2$で割り切れる数字はいくつありますか？」
counter = 0
for n in range(1, 101):
if n % 2 == 0:
counter += 1
print(counter)
4. 全探索
線形探索と違い「forが二重三重になっている」そのため計算量が指数関数的に増える。
個人的に実装の際に直感的でわかりやすくfor使いがちになっちゃうけどデータ量の多いタスクではダメだよねってことで気を付けたい。
forでも実行時間に問題なければいいのかもだけどやっぱより速くしたいよな。。。
(例)
「二枚のカードの値を組み合わせて合計Sになるものを探そう」
# 前提としてカード情報がAとBの変数に配列で、合計値Sはintとして渡ってくることとする
flag = False # 見つかればTrueにする
for a in A:
for b in B:
if S == (a+b):
flag = True
if flag:
print('Yes')
5. まとめ
結果、全探索遅くね？(ただしデータ量との兼ね合いみようね)
今までforいっぱいもりもりで書いちゃってたので反省、反省(-_-;)
次は残りの二分探索やほかの計算量について書こうと思う。
その次から基本的なアルゴリズムとステップアップしていこう。
追記
続きを書きました。よければ見てください。