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

Question

アルゴリズムの最悪の場合の複雑さを判断する方法を誰かに説明してもらえますか? 式 W(n) = max{t(I)|D の I 要素) を使用する必要があることはわかっています。ここで、D はサイズ n の入力のセットです。各要素に対して実行された操作の数を計算し、その最大値を取得しますか? これを達成するためのより簡単な方法は何ですか?

Answer 1

方程式から出発することは、少し逆算して考えることです。あなたが本当に気にかけているのは、スケーラビリティです。つまり、入力のサイズを増やしたときにどうなるかです。

たとえば、ループがあるだけの場合、O(n) 時間の複雑さのアルゴリズムがあります。ただし、別のループ内にループがある場合は、O(n^2) になります。これは、サイズ n の入力に対して n^2 個の処理を実行する必要があるためです。

最悪のケースについて話しているときは、通常、時期尚早に停止する可能性のあるループがある可能性がある非決定論的アルゴリズムについて話している. このためにやりたいことは、最悪の事態を想定して、ループができるだけ遅く停止するふりをすることです。したがって、次の場合：

for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(rand() > .5) j = n; } }

最悪のケースは O(n^2) です。中間ループが早期に破綻する可能性が非常に高いことはわかっていますが、考えられる最悪のパフォーマンスを探しています。

Answer 2

その方程式は、アルゴリズムというよりも定義です。

問題のアルゴリズムは、入力のサイズ以外を気にしますか? そうでない場合、W(n) の計算は「簡単」です。

もしそうなら、病理学的なインプットを考え出してみてください。たとえば、クイックソートを使用すると、ソートされた入力が異常であることは明らかであり、カウントを行って O(n^2) ステップかかることを確認できます。その時点で、次のいずれかを行うことができます

1. あなたの入力が「最大限に」病的であると主張する
2. 任意の入力でランタイムに一致する上限を示す

#1の例:

クイックソートの各パスは、ピボットを適切な場所に配置し、2 つの部分を再帰します。( handwave アラート) 最悪のケースは、残りのアレイをピボットの片側に置くことです。ソートされた入力はこれを実現します。

#2 の例:

クイックソートの各パスはピボットを適切な場所に配置するため、パスは O(n) を超えることはありません。各パスに必要な作業は O(n) 以下です。そのため、クイックソートに O(n^2) を超える入力が発生することはありません。

この場合、#2 の方がはるかに簡単です。