アルゴリズムの最悪の複雑さを判断する

Question

アルゴリズムの最悪の複雑さをどのように判断できるか教えてください。私は、Dがサイズnの入力のセットである場合、式W（n）= max {t（I）| Iの要素）を使用する必要があることを知っています。各要素Iに対して実行された操作の数を計算し、その最大値を取るか？これを達成するための簡単な方法は何ですか？

Answer 1

式から始めると、それは少し後ろ向きに考えられます。あなたが本当に気にしているのは、スケーラビリティです。入力のサイズを大きくすると、それは何をするのでしょうか。

たとえば、ループがある場合は、O（n）回の複雑さのアルゴリズムがあります。しかし、別のループ内にループがある場合は、任意のサイズnの入力に対してn^2を行う必要があるため、O（n^2）になります。

最悪の場合を話しているときは、通常、非決定論的なアルゴリズムについて言及しています。ここでは、ループが早期に停止する可能性があります。あなたがこれに対してしたいことは、最悪の場合を想定し、ループができるだけ遅く停止するように見せかけることです。だから我々が持っている場合は、（i = 0をint型;私< N;私は++）のため

{ のために（int型J = 0; jの< N; J ++）{ （RAND（）> 0.5）場合にj = n; }}

我々は最悪の場合はO（N^2）であることを言うでしょう。ミドルループが早期に破綻する可能性が高いことはわかっていますが、最悪の可能性を探しています。

Answer 2

この方程式は、アルゴリズムよりも定義のほうが多いです。

問題のアルゴリズムは入力のサイズ以外のものを気にしていますか？そうでなければ、W（n）を計算することは「容易」である。

もしそうであれば、病理学的入力を試してみてください。たとえば、クイックソートでは、ソートされた入力が病理学的なものであることはかなり明らかであり、O（n^2）ステップが必要であることを数えることができます。

：その時点で、あなたはどちらか

1. は、あなたの入力が上位1位のいずれかの入力

例の実行時にバインドマッチング展示

「最大限」病的であると主張することができます

クイックソートの各パスは、ピボットを正しい場所に置き、2つの部分で再帰します。 （ハンドウェイアラート）最悪の場合は、ピボットの片側に残りのアレイを配置します。ソートされた入力がこれを達成します。

＃2の例：

クイックソートの各パスは適切な場所にピボットを置くので、O（N）以下ではありません通過します。各パスは、O（n）回の作業を必要としません。このように、入力はクイックソートにO（n^2）以上かかることはありません。

この場合、＃2のほうがはるかに簡単です。