昨日までのはこちら
100日後にエンジニアになるキミ - 42日目 - クラウド - クラウドサービスについて
100日後にエンジニアになるキミ - 36日目 - データベース - データベースについて
100日後にエンジニアになるキミ - 24日目 - Python - Python言語の基礎1
100日後にエンジニアになるキミ - 18日目 - Javascript - JavaScriptの基礎1
100日後にエンジニアになるキミ - 14日目 - CSS - CSSの基礎1
100日後にエンジニアになるキミ - 6日目 - HTML - HTMLの基礎1
100日後にエンジニアになるキミ - 53日目 - Git - Gitについて
アルゴリズムについて
アルゴリズムalgorithm とは何でしょうか？
ざっくりとした答えは計算手順のことです。
詳しくいうと、プログラムを作るときに用いる問題を解決するための手順・計算方法
となります。
どういう順番でどういう計算をするのか？
ということになります。
アルゴリズムの重要性
世の中には沢山のアルゴリズムが存在しますが似た機能を持つものがたくさんあります。
同じ答えを出すための計算方法は考案者によって違いが出てきます。
その中で一番重要視される項目が計算量です。
ここで簡単なアルゴリズムの例として年齢当てクイズをやってみましょう。
問題
乙 さんの年齢を当てようとしています。
乙 さんが 30 歳以上 46 歳未満だというのはわかっているとします。
あなたは A さんに Yes / No で答えられる質問をすることができます。
乙 さんの年齢を当てられるでしょうか？？？
ここで質問する回数というのが計算量にあたります。
さて何回で当てることができるでしょうか？
回答1
乙 さんは30 歳以上 46 歳未満だというので
当てずっぽうにやるよりは、真面目に1歳ずつ聞いてみました。
あなたは30歳ですか? No
あなたは31歳ですか? No
あなたは32歳ですか? No
あなたは33歳ですか? No
あなたは34歳ですか? No
あなたは変態ですか? Yes(これは答えではない)
あなたは35歳ですか? No
あなたは36歳ですか? No
あなたは37歳ですか? No
あなたは38歳ですか? No
あなたは39歳ですか? No
あなたは40歳ですか? Yes!!!!!!
どうやら 乙さんは40歳とのことですね。答えを知るのに11回掛かりました。
この方法だと相手の年齢によっては最小で1回、最大で16回かかることになります。
このように最初から総当たりで一つづつ調べていく方法のことを
線形探索と言っています。
回答2
あなたはもうちょっと少ない回数で年齢を知ることができないかと考えました。
30 歳以上 46 歳未満ということで年齢幅は16歳分です。
半分ずつになるように聞いていったらどうかと思って試してみました。
あなたは38歳以上ですか? Yes
あなたは42歳以上ですか? No
あなたは40歳以上ですか? Yes
あなたは41歳以上ですか? No
あなたは40歳ですか? Yes
正解には5回でたどり着きました。
この方法だと、相手が何歳であっても5回以内で答えを求めることができます。
このようにデータの真ん中で切ってどちらかに絞って行くタイプのアルゴリズムは
二分探索法という名前がついていたりします。
アルゴリズムによってこの計算回数が大きく変わって来ますが
計算回数の少ないアルゴリズムの方が労力が少なくなるので効率が良いはずです。
今は少ない回数で求められる問題でやっていますが実務で行われる場合は
非常に計算回数が大きいです。アルゴリズムによっては計算が終わらないようなケースも出てきます。
そのため計算量の比較的少ない、効率の良いアルゴリズムを考えることが急務となる場合があります。
計算量(オーダー)について
計算量(オーダー)とは、アルゴリズムを使った演算の性能を表す指標のことで
計算量は大きく二つに分けられます。
-
時間計算量(処理時間の計算量) -
空間計算量(メモリ使用量の計算量)
単に計算量(オーダー)と言った場合は時間計算量のことを指します。
時間計算量はプログラムが命令を実行した回数を調べることで求められます。
正確な数は数えづらいですがステップ数と言う基本単位を使います。
処理を終了するまでに何回その基本単位を実行したかを調べて計算時間とする方法です。
ざっくり計算方法ですが掛け算の九九のような計算を行いその計算量を測ってみます。
n = 9
for i in range(1,n+1):
for j in range(1,n+1):
print('{0:02}'.format(i*j) , end='\t')
print()
01 02 03 04 05 06 07 08 09
02 04 06 08 10 12 14 16 18
03 06 09 12 15 18 21 24 27
04 08 12 16 20 24 28 32 36
05 10 15 20 25 30 35 40 45
06 12 18 24 30 36 42 48 54
07 14 21 28 35 42 49 56 63
08 16 24 32 40 48 56 64 72
09 18 27 36 45 54 63 72 81
この場合ループが二重になっており、それぞれのループでn回処理をおこなっており
print文の処理にかかる時間をcとすると全体では$c*n^2$回の処理が行われています。
nの数が増えると、その二乗分回数が増えていくことになります。
O記法(オーダー記法)について
全体の計算量に大きな影響がない部分を無視して計算量を記述する方法にオーダー記法があり
Oという記号を使います。
これで行くと先ほどの掛け算は$O(n^2)$の計算量になります。
入力の大きさnの変化に対して、計算時間がどの程度変わって行くのかが想像できると思います。
オーダーの比較をしてみると
| 処理時間 | オーダー | 例 |
|---|---|---|
| 短い | O(1) | リストへのアクセス |
| O(logn) | 二分探索 | |
| O(n) | 線形探索 | |
| O(n logn) | マージソート | |
| O(n^2) | 選択ソート、挿入ソート | |
| O(n^3) | 行列の掛け算 | |
| O(2^n) | ナップザック問題 | |
| 長い | O(n!) | 巡回セールスマン問題 |
入力nに対する大体の計算時間は以下の通りです。
| $log n$ | $n$ | $n log n$ | $n^2$ | $n^3$ | $2^n$ | $n!$ |
|---|---|---|---|---|---|---|
| 2 | 5 | 12 | 25 | 130 | 30 | 120 |
| 3 | 10 | 33 | 100 | 1,000 | 1,024 | 3,628,800 |
| 4 | 15 | 59 | 225 | 3.375 | 32,768 | - |
| 4 | 20 | 86 | 400 | 8,000 | 1,048,576 | - |
| 5 | 25 | 116 | 625 | 15,625 | - | - |
| 5 | 30 | 147 | 900 | 27,000 | - | - |
| 7 | 100 | 664 | 10,000 | 1,000,000 | - | - |
| 8 | 300 | 2,468 | 90,000 | 27,000,000 | - | - |
| 10 | 1,000 | 9,966 | 1,000,000 | - | - | - |
| 13 | 10,000 | 132,877 | 100,000,000 | - | - | - |
| 16 | 100,000 | 1,660,964 | - | - | - | - |
| 20 | 1,000,000 | 19,931,568 | - | - | - | - |
こうしてみると$n log n$ぐらいであればまだ比較的計算量が抑えられていますが
$n^2$以降は計算量が爆発してしまいます。
$O(n^2)$なアルゴリズムを$O(n)$や$O(nlogn)$に改善できるかどうかが鍵となるでしょう。
Pythonの標準ソートのアルゴリズムなどはその典型的な例です。
(TimSortは高速な安定ソートでPythonやJavaでの標準ソートアルゴリズムとして採用されているそうです。)
まとめ
アルゴリズムという言葉の理解と計算量について触れておこう。
君がエンジニアになるまであと41日
作者の情報
乙pyのHP：
http://www.otupy.net/
Youtube：
https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw
Twitter：
https://twitter.com/otupython