漸近表記とアプリオリ分析
アルゴリズムの設計では、アルゴリズムの複雑さの分析が重要な側面です。主に、アルゴリズムの複雑さは、そのパフォーマンス、動作の速さまたは遅さに関係します。
アルゴリズムの複雑さは、データの処理に必要なメモリの量と処理時間の観点からアルゴリズムの効率を表します。
アルゴリズムの複雑さは、次の2つの観点から分析されます。 Time そして Space。
時間計算量
これは、入力のサイズの観点からアルゴリズムを実行するために必要な時間を記述する関数です。「時間」とは、実行されたメモリアクセスの数、整数間の比較の数、内部ループが実行された回数、またはアルゴリズムにかかるリアルタイムの量に関連するその他の自然単位を意味します。
スペースの複雑さ
これは、アルゴリズムへの入力のサイズに関して、アルゴリズムが使用するメモリの量を記述する関数です。入力自体を格納するために必要なメモリを数えずに、必要な「追加の」メモリについてよく話します。ここでも、これを測定するために自然な（ただし固定長の）単位を使用します。
使用されるスペースが最小限または明白であるため、スペースの複雑さが無視されることもありますが、時間と同じくらい重要な問題になることもあります。
漸近表記
アルゴリズムの実行時間は、命令セット、プロセッサ速度、ディスクI / O速度などに依存します。したがって、アルゴリズムの効率を漸近的に推定します。
アルゴリズムの時間関数は次の式で表されます。 T(n)、 どこ n 入力サイズです。
アルゴリズムの複雑さを表すために、さまざまなタイプの漸近表記が使用されます。次の漸近表記は、アルゴリズムの実行時間の複雑さを計算するために使用されます。
O −ビッグオー
Ω −ビッグオメガ
θ −ビッグシータ
o −リトルオー
ω −リトルオメガ
O：漸近的な上界
「O」（Big Oh）は、最も一般的に使用される表記法です。機能f(n) 表現できるのは g(n) あれは O(g(n))、正の整数の値が存在する場合 n なので n0 と正の定数 c そのような-
$ f（n）\ leqslant cg（n）$ for $ n> n_ {0} $すべての場合
したがって、機能 g(n) 関数の上限です f(n)、 なので g(n) より速く成長する f(n)。
例
与えられた関数、$ f（n）= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう。
$ g（n）= n ^ 3 $を考えると、
$ n> 2 $のすべての値に対して$ f（n）\ leqslant 5.g（n）$
したがって、の複雑さ f(n) $ O（g（n））$、つまり$ O（n ^ 3）$として表すことができます
Ω：漸近的な下限
定数が存在する場合、$ f（n）= \ Omega（g（n））$と言います c その$ f（n）\ geqslant cg（n）$は、 n。ここにnは正の整数です。機能を意味しますg 関数の下限です f; の特定の値の後n, f 下に行くことはありません g。
例
与えられた関数$ f（n）= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう。
$ n> 0 $のすべての値について、$ g（n）= n ^ 3 $、$ f（n）\ geqslant 4.g（n）$を考慮します。
したがって、の複雑さ f(n) $ \ Omega（g（n））$、つまり$ \ Omega（n ^ 3）$として表すことができます
θ：漸近的タイトバウンド
定数が存在する場合、$ f（n）= \ theta（g（n））$と言います c1 そして c2 その$ c_ {1} .g（n）\ leqslant f（n）\ leqslant c_ {2} .g（n）$ n。ここにn は正の整数です。
これは機能を意味します g 機能のタイトバウンドです f。
例
与えられた関数、$ f（n）= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう。
$ g（n）= n ^ 3 $を考慮すると、$ 4.g（n）\ leqslant f（n）\ leqslant 5.g（n）$のすべての大きな値について n。
したがって、の複雑さ f(n) $ \ theta（g（n））$、つまり$ \ theta（n ^ 3）$として表すことができます。
O-表記
によって提供される漸近的な上限 O-notation漸近的にタイトな場合とそうでない場合があります。バインドされた$ 2.n ^ 2 = O（n ^ 2）$は漸近的にタイトですが、バインドされた$ 2.n = O（n ^ 2）$はそうではありません。
を使用しております o-notation 漸近的にタイトではない上限を示します。
正式に定義する o(g(n)) （nのgの少しああ）セットとして f(n) = o(g(n)) 正の定数$ c> 0 $であり、$ 0 \ leqslant f（n）\ leqslant cg（n）$のような値$ n_ {0}> 0 $が存在する場合。
直感的に、 o-notation、 関数 f(n) に比べて重要ではなくなります g(n) なので n無限に近づく; あれは、
$$ \ lim_ {n \ rightarrow \ infty} \ left（\ frac {f（n）} {g（n）} \ right）= 0 $$
例
同じ関数、$ f（n）= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう。
$ g（n）= n ^ {4} $を考えると、
$$ \ lim_ {n \ rightarrow \ infty} \ left（\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right）= 0 $$
したがって、の複雑さ f(n) $ o（g（n））$、つまり$ o（n ^ 4）$として表すことができます。
ω–表記
を使用しております ω-notation漸近的にタイトではない下限を示します。ただし、正式には、ω(g(n)) （nのgの小さなオメガ）セットとして f(n) = ω(g(n)) 正の定数の場合 C > 0 そして、$ 0 \ leqslant cg（n）<f（n）$のような値$ n_ {0}> 0 $が存在します。
たとえば、$ \ frac {n ^ 2} {2} = \ omega（n）$ですが、$ \ frac {n ^ 2} {2} \ neq \ omega（n ^ 2）$です。$ f（n）= \ omega（g（n））$の関係は、次の制限が存在することを意味します
$$ \ lim_ {n \ rightarrow \ infty} \ left（\ frac {f（n）} {g（n）} \ right）= \ infty $$
あれは、 f(n) に比べて任意に大きくなります g(n) なので n 無限に近づく。
例
同じ関数、$ f（n）= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう。
$ g（n）= n ^ 2 $を考えると、
$$ \ lim_ {n \ rightarrow \ infty} \ left（\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right）= \ infty $$
したがって、の複雑さ f(n) $ o（g（n））$、つまり$ \ omega（n ^ 2）$として表すことができます。
アプリオリとアポスティアリの分析
アプリオリ分析とは、特定のシステムで実行する前に分析を実行することを意味します。この分析は、何らかの理論モデルを使用して関数を定義する段階です。したがって、異なるメモリ、プロセッサ、およびコンパイラを備えた特定のシステムでアルゴリズムを実行するのではなく、アルゴリズムを調べるだけで、アルゴリズムの時間と空間の複雑さを判断します。
アルゴリズムの事後分析とは、システム上で実行した後にのみアルゴリズムの分析を実行することを意味します。これはシステムに直接依存し、システムごとに異なります。
業界では、ソフトウェアは一般的に匿名ユーザー向けに作成されており、業界に存在するシステムとは異なるシステムで実行されるため、Apostiari分析を実行することはできません。
Aprioriでは、コンピューターごとに変化する時間と空間の複雑さを決定するために漸近表記を使用するのはそのためです。ただし、漸近的には同じです。