オーダ
このサイトではいくつかのアルゴリズムを紹介していますが、これはより効率の良い(実行速度の速い)アルゴリズムを見つける目的があります。
ここではアルゴリズムの実行効率の評価方法としてオーダ(計算量)という指標を学習します。
それぞれのアルゴリズムについてはこちら。
https://tunasalmon.com/2019/02/09/%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0%e3%81%ae%e8%a8%98%e4%ba%8b%e3%81%be%e3%81%a8%e3%82%81-%e3%83%97%e3%83%ad%e3%82%b0%e3%83%a9%e3%83%a0%e3%81%ae%e8%80%83%e3%81%88%e6%96%b9%e3%82%92/
ソートや探索といったアルゴリズムは、処理するデータによって計算する量が変わります。
処理するデータ件数をnとした時、アルゴリズムの実行時間がn^2で表せる場合、計算量はO(n^2)となります。
オーダでは、実行時間が多項式である場合は、増加率の最も大きい項のみを計算量とします。
例えば、実行時間がn^2+2nで表せる場合であっても計算量はO(n^2)となります。
単純な計算ですが、各データに対して1回ずつ処理をするプログラムであればO(n)、各データに対してn-1回の処理を行う二重ループのプログラムならO(n^2)となります。
オーダの大小関係
以下がオーダの中身の代表的なすうちの大小関係です。
下に行くほど小さくなり、計算量の少ない上質なアルゴリズムであると言えます。
| n! | 大 |
| 2^n | |
| n^2 | |
| n * log2(n) | |
| n | |
| log2(n) | |
| 1(定数) | 小 |
(adsbygoogle = window.adsbygoogle || []).push({});