1. 概要

このチュートリアルでは、アルゴリズムの複雑さの下限と下限の違いを調べます。

2. バッハマン-ランダウの記号

漸近表記は、バッハマン-ランダウ表記とも呼ばれ、アルゴリズムの時間または空間の複雑さを表す一般的な方法です。 その基本的な考え方は、関数またはアルゴリズムの動作は、その入力として、ある程度の制限があり、予測可能になる傾向があり、他の漸近関数との関係も予測可能になるというものです。

関数ではなくアルゴリズムを研究するときは、単に。に置き換えます。 後者は、アルゴリズムに提供される入力のサイズに対応します。 その場合、他のいくつかのアルゴリズムまたは関数に関連して、アプローチとしてのアルゴリズムの漸近的振る舞いを一般的に研究します。

3. 入力のサイズと境界

アルゴリズムの入力は通常、リスト、データベース、変数、グラフ、またはその他のタイプのデータ構造で構成されます。 そのサイズに関連して、特定の入力で実行されるアルゴリズムに最大または最小の時間制限があるかどうかを知りたいです。 これらの制限を次のように呼びます。

  • 下限、最小保証時間
  • 上限、最大保証時間

単純な入力を使用する単純なプログラムには、計算時間とそれに対応する制限があり、調査が容易です。 彼らにとって、私たちは実験を通して彼らの実際の計算時間を学び、それによって彼らの下限と上限に関するアイデアを定式化することができます。 ただし、より複雑なプログラムの場合、必ずしもそうとは限りません。

もちろん、可能な限り最も単純なプログラムは空のプログラムであり、入力のサイズに関係なくすぐに実行されます。 空のプログラムの場合、入力のサイズの関数として、必要な最小時間と最大時間は完全に一致します。 ただし、すべての重要なケースで、この完全な対応は保証されないため、保証される最小計算時間と最大保証計算時間を区別する必要があります。

4. Big-O表記

Big-O表記は、アルゴリズムの上限を定義します。 アルゴリズムに上限がある場合、これは、最悪のシナリオでも、最大で一定の時間で実行されることが保証されていることを意味します。

例として、マージソートの時間計算量はです。 ヒープソートも複雑であり、最悪の場合、2つの形式が同等になります。 線形探索は、代わりに、の計算の複雑さを持っているため、前の2つよりも予想どおりに高速になります。

ただし、アルゴリズムに上限がある場合、計算時間の上限の最良の近似であるという保証はないことに注意してください。 実際、現在使用しているものよりもさらに優れた近似値がある可能性があります。

たとえば、特定のアルゴリズムが。の上限である場合、それも。の上限であると言うこともできます。 前者は、当然のことながら、後者よりもはるかに優れた近似ですが、ステートメントは依然として有効です。

5. ビッグオメガ表記

反対に、 BigOmega記号で示す下限があります。 実行に少なくとも操作が必要な場合、アルゴリズムの計算時間は最小であると言います。

たとえば、すべてのアルゴリズムの最小計算時間はわずかです。 また、線形検索にはのベストケースシナリオがあります。これは、検索している要素がリストの最初にある場合に発生します。

代わりに、文字列内のすべての文字を解析するには、サイズがの文字列が必要です。 これは、最後の文字が満たされた場合にのみ終了条件に達するためです。 また、せいぜい操作が必要ですが、それについては次に詳しく説明します。

6. ビッグシータ表記

最後に、との定義に基づいて、大きなシータ表記を定義することもできます。 アルゴリズムは、その下限の複雑さがであり、その上限がである場合にのみ、計算の複雑さを持ちます。 正式な表記法を使用すると、次のように言うことができます。

前のセクションで、サイズの文字列内のすべての文字の解析は、下限が。で、上限が。であることに注意しました。 結果として、このアルゴリズムは緊密にバインドされていると言えます。 したがって、文字列の解析には計算の複雑さが。であると簡単に言うことができます。

7. 結論

この記事では、下限の表記と厳密な境界の表記の違いを調べました。

厳密な境界は、アルゴリズムの計算の複雑さの下限と上限の両方が同じであることを意味します。