Design-and-analysis-of-algorithms-asymptotic-notations-apriori
漸近記法とアプリオリ分析
アルゴリズムの設計では、アルゴリズムの複雑さの分析が重要な側面です。 主に、アルゴリズムの複雑さは、そのパフォーマンス、動作の速さまたは遅さを懸念しています。
アルゴリズムの複雑さは、データの処理に必要なメモリの量と処理時間に関して、アルゴリズムの効率を表します。
アルゴリズムの複雑さは、*時間*および*スペース*の2つの観点で分析されます。
時間の複雑さ
これは、入力のサイズの観点からアルゴリズムを実行するのに必要な時間を記述する関数です。 「時間」とは、実行されるメモリアクセスの数、整数間の比較の数、内部ループの実行回数、またはアルゴリズムにかかるリアルタイムの量に関連するその他の自然単位を意味します。
スペースの複雑さ
これは、アルゴリズムへの入力のサイズの観点から、アルゴリズムが消費するメモリ量を記述する関数です。 入力自体を保存するために必要なメモリをカウントするのではなく、必要な「余分な」メモリについてよく話します。 繰り返しますが、これを測定するために自然な（ただし固定長の）ユニットを使用します。
スペースの複雑さは、使用されるスペースが最小または明白であるために無視される場合がありますが、時間と同じくらい重要になることがあります。
漸近記法
アルゴリズムの実行時間は、命令セット、プロセッサ速度、ディスクI/O速度などに依存します。 したがって、アルゴリズムの効率を漸近的に推定します。
アルゴリズムの時間関数は* T（n）で表されます。 *n は入力サイズです。
アルゴリズムの複雑さを表すために、さまざまなタイプの漸近表記法が使用されます。 次の漸近表記法を使用して、アルゴリズムの実行時間の複雑さを計算します。
- O -Big Oh
- Ω-ビッグオメガ
- θ-ビッグシータ
- o -Little Oh
- ω-小さなオメガ
O：漸近的上限
「O」（Big Oh）は最も一般的に使用される表記法です。 * nとして正の整数 n の値が存在する場合、関数 f（n） は O（g（n）） である g（n） の順序で表現できます。 〜0〜および次のような正の定数 *c
すべての場合で$ n> n _ \ {0} $の場合は$ f（n）\ leqslant c.g（n）$
したがって、 _ 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）$
Ω：漸近的下限
定数 c が存在する場合、$ f（n）= \ Omega（g（n））$と言います。 n の十分に大きい値すべてに対して、$ f（n）\ geqslant c.g（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）$
θ：漸近タイトバウンド
$ c _ \ {1} .g（n）\ leqslant fという定数* c〜1〜および c〜2〜が存在する場合、$ f（n）= \ theta（g（n））$と言います。 （n） *n の十分に大きい値すべてに対して、\ leqslant c _ \ {2} .g（n）$。 ここで、 n は正の整数です。
これは、関数 g が関数 f の厳密な境界であることを意味します。
例
与えられた関数$ f（n）= 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $を考えてみましょう
*n* のすべての大きな値に対して、$ g（n）= n ^ 3 $、$ 4.g（n）\ leqslant f（n）\ leqslant 5.g（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* を使用して、漸近的に厳密ではない上限を示します。正の定数$ c> 0 $に対して o（g（n）） （nのgの小さなoh）を集合 f（n）= o（g（n）） として正式に定義し、 $ 0 \ leqslant f（n）\ leqslant cg（n）$のような値$ n _ \ {0}> 0 $が存在します。
直観的に、 o-notation では、 n が無限に近づくにつれて、関数 f（n） は g（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）$。
ω–表記法
ω-記法*を使用して、漸近的にタイトでない下限を示します。 ただし、正式には、 *ω（g（n）） （nのgの小さなオメガ）を任意の正の定数* C>のセット _f（n）=ω（g（n）） として定義します。 0_ *および値$ n _ \ {0}> 0 $が存在し、$ 0 \ leqslant cg（n）<f（n）$です。
たとえば、$ \ 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
つまり、 _ n が無限に近づくと、 _ f（n）' は _g（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）$。
アプリオリとアポスティーリ分析
Apriori分析とは、特定のシステムで実行する前に分析が実行されることを意味します。 この分析は、理論モデルを使用して関数が定義される段階です。 したがって、異なるメモリ、プロセッサ、コンパイラを備えた特定のシステムでアルゴリズムを実行するのではなく、アルゴリズムを見るだけで、アルゴリズムの時間と空間の複雑さを判断します。
アルゴリズムのアポストリアリ分析とは、システムで実行した後にのみアルゴリズムの分析を実行することを意味します。 これは、システムとシステムごとの変更に直接依存します。
業界では、ソフトウェアは一般に匿名ユーザー向けに作成され、業界に存在するシステムとは異なるシステムで実行されるため、アポスティアリ分析を実行できません。
Aprioriでは、漸近表記法を使用して、コンピューター間で変化する時間と空間の複雑さを判断します。ただし、漸近的には同じです。
