「Pythonではじめるアルゴリズム入門」の学習記録です。学習に使ったファイルやコードなどをアップしていきます。
今回はアルゴリズムの計算量、および「良い」アルゴリズムの定義について学びました。コードよりも座学内容が多めです。
計算コスト・実行時間を考慮したアルゴリズム
「良い」アルゴリズムとはデータ量に対する計算コスト・実行時間が少ないアルゴリズムを指します。例えばフィボナッチ数の計算などではメモ化を活用した方が良いアルゴリズムとなります。環境・言語に依存せずにアルゴリズムを評価する指標として、計算量が用いられます。
- 時間計算量 - 処理にかかる時間
- 空間計算量 - 処理に要する記憶容量
メモ化を活用すると時間計算量が減る代わりに、処理に要する空間計算量が増える場合もあります。
オーダーの比較
入力量に対する計算量の増分を自然対数・指数などで表現する記法を、オーダー記法といいます。複数のアルゴリズムを検討する際、どれが効率が良いかを大雑把に検定できます。アルゴリズムの計算量を考える際は、最も処理に時間がかかるデータの処理＝最悪計算量, もしくは最悪計算量になるケースが少ない場合は平均計算量を基準とします。
| オーダー記法 | アルゴリズム |
|---|---|
| O(1) | リスト・コレクション等へのアクセス |
| O(logn) | 二分探索 |
| O(n) | 線形探索 |
| O(n*logn) | マージソート、ヒープソート |
| O(n^2) | 選択ソート、挿入ソート、バブルソート、シェルソート |
| O(n^3) | 行列の掛け算 |
| O(2^n) | ナップサック問題 |
| O(n!) | 巡回セールスマン問題 |
データ構造と計算量
データを複数処理する場合、多くの場合リストやコレクションをイテレーターを使って順次処理します。実装するアルゴリズムによっては、1つの要素に次のデータのアドレスを合わせた連結リストを使った方が良いアルゴリズムにできる場合があります。リストに要素を追加・削除すると必要な計算量はO(n)となるが、連結リストならO(1)で済みます。一方、読み取り自体は連結リストの方が計算量が多くなる場合があります。
巡回セールスマン問題のような最初はn通り、次はn-1通り...のような問題の計算量はO(n!)となります。このような多項式時間で解けないことが証明されている問題は、P=/NP予想で著名なNP困難問題に属します。
| 分類 | 説明 |
|---|---|
| クラスP | 多項式時間で「判定」可能な問題 |
| クラスNP | 多項式時間で「検証」可能な問題 |
| NP困難 | 多項式時間で判定できない問題 |
P=NPであることが証明されれば、かなりおおざっぱな理解になりますがハミルトン閉路問題・RSA暗号の作成など、O(n!) の計算量を要するアルゴリズムが原理的にはO(n) の計算量で解けるより良いアルゴリズムに代替できる可能性があります。一方、NP困難な問題は多項式時間での判定は出来ません。
探索のアルゴリズム
線形探索
プログラミングにおける探索
リストに特定の値があるか、最初から最後までしらみつぶしに探索する → 線形探索。計算量は**O(n)**となる
"""
プログラミングにおける探索
リストに特定の値があるか、最初から最後までしらみつぶしに探索する → 線形探索
O(n)
"""
data = [50,30,90,10,20,70,60,40,80]
found = False
data_look =40
print("探索するデータ: "+ str(data_look))
for i in range(len(data)):
if data[i] == data_look:
print("発見したデータのインデックス: "+ str(i))
found = True
break
if not found:
print("データが見つかりませんでした。")
探索するデータ: 40
発見したデータのインデックス: 7
二分探索
探索範囲を半分に分け、入っていない方は処理しない → 二分探索。計算量はO(log(n))。二分探索を使うと計算量が対数に比例するので、かなり計算効率がよくなる。特に計算量が線形探索の20%以下となる、10個以上のリストを探索する場合で効果的。
二分探索を使えるケースは、リストが昇順・降順で並んでいる場合に限られる。
"""
より効率的な探索
探索範囲を半分に分け、入っていない方は処理しない → 二分探索
O(log(n))
二分探索を使うと計算量が対数に比例するので、かなり計算効率がよくなる。
特に計算量が線形探索の20%以下となる、10個以上のリストを探索する場合で効果的
二分探索を使えるケースは、リストが昇順・降順で並んでいる場合に限られる
"""
def binary_search(data,value):
#左端・右端のインデックス
left = 0
right = len(data)-1
#探索範囲の中央
while left <= right:
mid = (left + right)//2
#中央の値と一致→ 位置を返し、探索範囲を切り替える
if data[mid] == value:
return mid
elif data[mid] < value:
left = mid + 1
else:
right = mid -1
#見つからなかった場合は値を返さない
return -1
data = [10,20,30,40,50,60,70,80,90]
data_look = 90
result = binary_search(data, data_look)
print("探索するデータ: "+ str(data_look))
print("発見したデータのインデックス: "+ str(result))