決定から、最も複雑なアルゴリズム

Question

で誰か教えてください私にどのように取り組むべきかを決める最悪の事態を複雑なアルゴリズム.のを知っている必要がありま利用の方程式W(n)=max{t(I)|Iの要素D、Dは入力のサイズnでたい番号を計算実行される操作のための各要素にし、その後そのmax?かくはあります。)

Answer 1

ビット後方にそれを考えている方程式からスタート。何が本当に気にすることは、あなたが入力のサイズを増やすようにしてくださいために何が起こっているか、拡張性である、または。

あなただけのループを持っている場合は、

、たとえば、あなたはO（n）の時間計算アルゴリズムを持っています。あなたがが別のループ内のループを持っている場合は、それが今どのようなサイズのn入力のため^ 2つのたくさんのnしなければならないので、それは、O（N ^ 2）となります。

あなたは最悪のケースについて話しているときは、

、あなたは通常、あなたが途中で停止することができますループを持っているかもしれない非決定的アルゴリズム、について話しています。あなたはこれをやってみたいことは最悪の事態を想定すると、ループはできるだけ遅く停止しますふりです。だから我々が持っている場合：

  

は、のために（INT i = 0; iがn <; iは++）{      （INT J = 0であり、j 0.5）J = Nであれば、      }   }

私たちは、最悪の場合はO（N ^ 2）であることを言うでしょう。我々は中央のループが早く出てバストになる可能性が非常に高いことを知っているにもかかわらず、我々は最悪のパフォーマンスを探しています。

Answer 2

この方程式の定義によるアルゴリズムです。

のアルゴリズム問題のア以外のものは何か？ない場合その計算W(n)"や".

または、上げる病理入力します。例えば、quicksortのですがかなり明らかにソートされた入力は病理学的には、まだ一部の計数しているのを見るのはO(n^2)です。その時点までのいずれか

1. うご入力"を最大限に"病理
2. 展示マッチングが上限に、実行時の任意の入力

例#1:

各パスのquicksortのピボット右のそれぞれのrecurseの二つに大別できます。(handwaveアラート)最悪の場合はその配列の進する。ソートされた入力を実現します。

例#2:

各パスのquicksortのピボットは、ありません以上のO(n)もあります。各パスを必要とする以外にはO(n)です。従って、入力原因となりquicksortによるO(n^2).

この場合には#2がたくさん楽になります。