オーダ
このサイトではいくつかのアルゴリズムを紹介していますが、これはより効率の良い(実行速度の速い)アルゴリズムを見つける目的があります。
ここではアルゴリズムの実行効率の評価方法としてオーダ(計算量)という指標を学習します。
それぞれのアルゴリズムについてはこちら。
ソートや探索といったアルゴリズムは、処理するデータによって計算する量が変わります。
処理するデータ件数を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(定数) | 小 |