1

Divide and Conquer アルゴリズムの Time Complexity を理解するのを手伝ってくれませんか。

これを例に取りましょう。 http://www.geeksforgeeks.org/archives/4583方法 2: T(n) = 3/2n -2 が得られましたが、その理由がわかりません。

申し訳ありませんが、開くための余分なページを提供した場合でも、そのようなアルゴリズムの複雑さを自分で見つけることができるように、少なくとも高いレベルまで理解したいと思っています。答えていただければ幸いです。

4

2 に答える 2

2

何らかの理由でこのリンクを開くことができません。まだやってみます。分割統治戦略を使用する場合、問題を多くの小さな問題に分割し、小さな問題の解決策を組み合わせて、主要な問題の解決策を取得します。より小さな問題を解決する方法: それらをさらに分割することによって。この分解のプロセスは、問題が直接処理できるほど小さいレベルに達するまで続きます。

時間計算量の計算方法: アルゴリズムにかかる時間が T(n) であると仮定します。所要時間は問題サイズ ien の関数であることに注意してください。

今、あなたがしていることに注意してください。問題をそれぞれサイズ n/k の k 個のパーツに分割します (サイズが等しくない場合があります。その場合、それらにかかる時間を個別に追加する必要があります)。ここで、これらの k 個の部分を解きます。問題のサイズが現在 n/k に縮小されているため、各部分にかかる時間は T(n/k) になります。そして、あなたはこれらのうちの k を解いています。したがって、k * T(n/k) 時間かかります。

これらの小さな問題を解決したら、それらのソリューションを組み合わせます。これにも時間がかかります。そして、その時間は問題のサイズの関数になります。(一定の場合もあります)。その時間を O(f(n)) とする。

したがって、アルゴリズムにかかる合計時間は次のようになります。 T(n) = (k * T(n/k)) + O(f(n))

これで、T(n) を取得するために解くことができる再帰関係が得られました。

于 2011-12-21T08:51:39.977 に答える
2

このリンクが示すように：

  T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
  T(2) = 1
  T(1) = 0

forT(2)の場合、返す前に単一の比較を行うベースです。T(1)それは何の比較にもならない土台だからです 。
For T(n): 配列の 2 つの半分に対してメソッドを再帰的に呼び出し、2 つの (min,max) タプルを比較して、実際の最小値と最大値を見つけます。これにより、上記のT(n)式が得られます。

If n is a power of 2, then we can write T(n) as:

   T(n) = 2T(n/2) + 2

これはそれ自体をよく説明しています。

  T(n)  = 3/2n -2

ここでは、帰納法でそれを解きます:
基本ケース: n=2 の場合:各(*) 帰納法の仮定は真であると仮定しますT(2) = 1 = (3/2)*2 -2
。T(k) = (3/2)k - 2k < n
T(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2
n/2 < n

誘導が正しいことを証明したので、次のように結論付けることができます。T(n) = (3/2)n - 2

于 2011-12-21T09:01:58.120 に答える