はじめに
アルゴリズムの一般的な特性とそれらの表現の形式モデルを研究するのはこの科学であるため、プログラマーはアルゴリズムの理論の基礎を知ることが重要です。 コンピュータサイエンスのレッスンからでも、フローチャートを作成するように教えられます。これは、後で学校よりも複雑なタスクを書くのに役立ちます。 また、特定の問題を解決する方法がほぼ常にいくつかあることも秘密ではありません。多くの時間を費やすものもあれば、リソースの解決に役立つものもあります。
特に問題のクラスを解決するためのアルゴリズムを開発するときは、タスクに応じて常に最適なものを探す必要があります。
また、さまざまなボリュームと数量の初期値でアルゴリズムがどのように動作するか、必要なリソース、最終結果を出力するのにかかる時間を評価することも重要です。
これは、アルゴリズムの理論のセクション-アルゴリズムの漸近解析の理論によって扱われます。
この記事では、主要な評価基準を説明し、最も単純なアルゴリズムの評価例を紹介することを提案します。 アルゴリズムの評価方法に関するHabrahabrに関する記事は既にありますが、主に高校生を対象としています。 この出版物は、その記事の延長とみなすことができます。
定義
アルゴリズムの複雑さの主な指標は、問題の解決に必要な時間と必要なメモリ量です。
また、タスクのクラスの複雑さを分析するとき、特定の量のデータ（ 入力のサイズ）を特徴付ける特定の数が決定されます 。
したがって、 アルゴリズムの複雑さは入力サイズの関数であると結論付けることができます。
アルゴリズムの複雑さは、同じ入力サイズで異なる場合がありますが、入力データは異なります。
最悪 、 中、または最高の場合には、複雑さの概念があります。 通常、最悪の場合の複雑さが評価されます。
最悪の場合、 時間の複雑さは、特定のサイズの問題を解決するときにアルゴリズムの操作中に実行される操作の最大数に等しい入力サイズの関数です。
最悪の場合、 容量の複雑さは、特定のサイズの問題を解決するときにアクセスされたメモリセルの最大数に等しい入力サイズの関数です。
アルゴリズムの成長順序
複雑度の増加の順序 （または公理的複雑度）は、入力サイズが大きいアルゴリズムの複雑度関数のおおよその動作を示します。 このことから、時間の複雑さを評価する場合、基本操作を考慮する必要はなく、アルゴリズムのステップを考慮するだけで十分であることがわかります。
アルゴリズムのステップは、連続して配置された基本操作のセットであり、その実行時間は入力のサイズに依存しません。つまり、ある定数によって上に制限されます。
漸近推定の種類
O-最悪の場合のスコア
複雑さf（n）> 0 、同じ次数の関数g（n）> 0 、入力サイズn> 0を考慮してください。
f（n）= O（g（n））で 、定数c> 0 、 n 0 > 0がある場合、
0 <f（n）<c * g（n）、
n> n 0の場合 。
この場合の関数g（n）は、f（n）の漸近的に正確な推定値です。 f（n）がアルゴリズムの複雑さの関数である場合、複雑さの順序はf（n）-O（g（n））として定義されます。
この式は、定数因子までg（n）より速く成長しない関数のクラスを定義します。
漸近関数の例
| f（n） | g（n） |
|---|---|
| 2n 2 + 7n-3 | n 2 |
| 98n * ln（n） | n * ln（n） |
| 5n + 2 | n |
| 8 | 1 |
Ω-ベストケーススコア
定義は最悪の場合のスコアの定義に似ていますが、
f（n）=Ω（g（n）） if
0 <c * g（n）<f（n）
Ω（g（n））は、定数gまで関数g（n）より遅くならない関数のクラスを定義します。
Θ-平均ケースのスコア
この場合、 n> n 0の関数f（n）はc 1 * g（n）とc 2 * g（n）の間にあることに注意してください。ここでcは定数因子です。
たとえば、 f（n）= n 2 + nの場合 、 g（n）= n 2 。
アルゴリズム評価基準
均一重み付け基準（RVC）は、アルゴリズムの各ステップが1単位の時間で実行され、メモリセルが1単位のボリュームで実行されることを前提としています（定数に正確）。
対数加重基準（LCV）は、特定の操作によって処理されるオペランドのサイズと、メモリセルに格納されている値を考慮します。
LCVの時間の複雑さは、 l（O p ）の値によって決まります。ここで、 O pはオペランドの値です。
LCVの容量の複雑さは、 l（M）の値によって決まります。ここで、 Mはメモリセルのサイズです。
階乗を計算するときの複雑さの評価の例
階乗を計算するアルゴリズムの複雑さを分析する必要があります。 これを行うために、言語Cの擬似コードでこのタスクを作成します。
void main() { int result = 1; int i; const n = ...; for (i = 2; i <= n; i++) result = result * n; }
均一な重量基準による時間の複雑さ
このタスクの入力サイズがnであると判断するのは十分簡単です。
ステップ数は（n-1）です。
したがって、RBCの時間の複雑さはO（n）です。
対数重み基準による時間の複雑さ
この段落では、評価する必要がある操作を強調する必要があります。 まず、これらは比較演算です。 第二に、変数を変更する操作（加算、乗算）。 割り当て操作は即座に発生すると想定されているため、考慮されません。
したがって、このタスクでは、3つの操作が区別されます。
1） i <= n
i番目のステップで、 log（n）を取得します 。
ステップは（n-1）であるため、この操作の複雑さは（n-1）* log（n）になります。
2）i = i + 1
i番目のステップで、 log（i）を取得します 。
したがって、合計
。
3）結果=結果* i
i番目のステップで、 log（（i-1）！）を取得します 。
したがって、合計
。
結果の値をすべて加算し、 nの増加とともに明らかにゆっくりと成長する項を破棄すると、最終式が得られます
。
均一な重量基準による容量性の複雑さ
ここではすべてが簡単です。 変数の数を数える必要があります。 タスクで配列が使用されている場合、配列の各セルは変数と見なされます。
変数の数は入力のサイズに依存しないため、複雑度はO（1）になります。
対数重み基準を使用した容量の複雑さ
この場合、メモリセルの最大値を考慮してください。 値が定義されていない場合（たとえば、オペランドi> 10）、何らかの制限値V maxがあると見なされます。
この問題には、値がn（i）を超えない変数と、値がnを超えない変数があります！ （結果） 。 したがって、スコアはO（log（n！））です。
結論
アルゴリズムの複雑さを研究することは、かなり魅力的な作業です。 現時点では、最も単純なアルゴリズムの分析は、コンピューターサイエンスとIT分野の応用数学に関係する専門技術のカリキュラム（正確には、「コンピューターサイエンスとコンピューターエンジニアリング」の一般化された方向）に含まれています。
複雑さに基づいて、タスクのさまざまなクラス、 P 、 NP 、 NPCが区別されます。 しかし、これはもはやアルゴリズムの漸近解析の理論の問題ではありません。