アルゴリズムの計算量

目次

オーダ

このサイトではいくつかのアルゴリズムを紹介していますが、これはより効率の良い(実行速度の速い)アルゴリズムを見つける目的があります。
ここではアルゴリズムの実行効率の評価方法としてオーダ(計算量)という指標を学習します。

ソートや探索といったアルゴリズムは、処理するデータによって計算する量が変わります。
処理するデータ件数を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(定数)



「アルゴリズムの計算量」への1件のフィードバック

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA