0

私はクラスでアルゴリズムの複雑さについて調査しています。アルゴリズムの他の複雑さがあるかどうかを知る必要があります。私が知っていて研究したのは2つのタイプです。1-BIGOの複雑さは時間とパフォーマンスであり、その他2 -スペースの複雑さはメモリの複雑さですが、アルゴリズムには他の種類の複雑さがありますか？アルゴリズムは私が見逃している他のものによって測定されていますか？

4

1 に答える 1

5

アルゴリズムの無症状の複雑さの観点から-はい、アルゴリズム（および問題）は空間と時間の観点から測定されます。

しかし、それについて私が言えることはもっとたくさんあります。私はいくつかの問題に対処しようとします：

空間/時間の消費は分析方法から導き出され
ますアルゴリズムの分析には、空間と時間の両方に使用される4つの一般的な方法があります。big-Oは関数のセットですが、どのように関数を導出するのでしょうか。複雑さの関数は、分析方法に従って導き出されます。分析方法は、（通常は）次のいずれかです。

  • 最良の場合
  • 平均的なケース
  • 最悪の場合
  • 償却分析

これらの方法はそれぞれ、どのアルゴリズムでも使用できます。結果が同じであるとは限りません。たとえば、クイックソートには、O(n^2)最悪の場合の時間計算量とO(nlogn)平均的な場合の時間計算量があります。

その他のセット：
大きなO表記に加えて、複雑さを示すために他の表記も使用します。追加の一般的な表記法は次のとおりです（使用法の共通性による）：

  • ビッグシータ（Θ）
  • ビッグオメガ（Ω）
  • 小さいo
  • 小さなオメガ（ω）

分析方法と混同しないでください。BigTheta/BigO /表記のそれぞれは、任意の分析方法（最悪の場合/平均的な場合/ ...）と組み合わせることができます
。BigTheta、Big O、およびそれらの間の違いは、このスレッドで見つけることができます

理論的な複雑さ：理論的な 「複雑さの理論」
の分野では、アルゴリズムではなく問題を分析します。このフィールドでは、問題が多項式で解決できるかどうか（つまり、入力のサイズがnの場合、問題はnの累乗で解決できるかどうか）、多項式で検証できるかどうかを確認します（可能な解決策があれば、それが正しい）。ただし、他のクラスもあります。 一般的な複雑さのクラスは次のとおりです。

さらに、問題が解決可能/決定可能であるかどうかに関心があります。問題の解決可能性を説明するための一般的なクラスは次のとおりです。

実世界：
実世界のアプリでは、理論的な空間/時間の複雑さだけでなく、定数も考慮します（同じ複雑さのクラスであっても、別のアルゴリズムの半分の時間がかかるアルゴリズムの方がはるかに優れています。これは、複雑度クラスが定数を無視するためです。）
また、プログラム/アルゴリズムの実装時間と保守性も考慮します。

于 2012-10-22T10:27:01.383 に答える