誰かが私にどのようにできるか説明してもらえますかアルゴリズムの最悪の場合の複雑さを決定します。方程式W（n）= max {t（I）| I要素のD）を使用する必要があることを私は知っています。ここで、Dはサイズnの入力のセットです。各要素Iに対して実行された操作の数を計算してから、その最大値を取得しますか？これを達成するためのより簡単な方法は何ですか？
回答：
回答№1は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）と言います。中間ループが早期に破綻する可能性が非常に高いことはわかっていますが、可能な限り最悪のパフォーマンスを探しています。
回答№2の場合は0
その方程式は、アルゴリズムというよりも定義です。
問題のアルゴリズムは、その入力のサイズ以外を気にしますか？そうでない場合、W（n）の計算は「簡単」です。
もしそうなら、病理学的に考えてみてください入力。たとえば、クイックソートを使用すると、ソートされた入力が病理学的であることは明らかであり、O（n ^ 2）のステップをとることを確認するためにいくつかのカウントを行うことができます。その時点で、次のいずれかを実行できます
- あなたの入力は「最大限に」病的であると主張する
- 任意の入力でランタイムに一致する上限を示す
＃1の例：
クイックソートの各パスは、ピボットを正しい場所に配置してから、2つの部分を再帰します。 （手波警報）最悪の場合は、ピボットの片側にアレイの残りを配置することです。ソートされた入力はこれを実現します。
＃2の例：
クイックソートの各パスは、ピボットを正しい場所なので、O（n）パスを超えることはありません。各パスに必要な作業はO（n）だけです。そのため、クイックソートがO（n ^ 2）を超える値を入力することはありません。
この場合、＃2の方がはるかに簡単です。