分裂征服アルゴリズムの時間複雑度

Question

分裂征服アルゴリズムの時間複雑度の理解に助けてください。

この例を考えてみましょう。 http://www.geeksforgeeks.org/archives/4583方法2： それはT（n）= 3/2n-2を与えました、なぜ私は理解できませんか？

私は余分なページを開いても申し訳ありませんが、私は実際にこのようなアルゴリズムの複雑さを高レベルで理解したいと思っています。

Answer 1

なんらかの理由でこのリンクを開くことはできません。私はまだそれを試してみましょう。 分割と征服の戦略を使用する場合、問題を多くの小さな問題に分割し、小さな問題の解決策を組み合わせて主な問題の解決策を得ることです。 小さな問題を解決するには：それらをさらに分解します。問題が直接処理できるほど小さいレベルに達するまで、この分割プロセスは続きます。

時間の複雑さを計算する方法： あなたのアルゴがかかる時間をT（n）とします。取られた時間は、問題のサイズすなわちnの関数であることに留意されたい。

さて、あなたが何をしているのか注目してください。あなたは、サイズn/kのそれぞれk個の部分を言ってみましょう（サイズが同じでないかもしれないので、それらの時間を個別に加えなければなりません）。さて、あなたはこれらのk個の部分を解くでしょう。問題のサイズが現在n/kに縮小されているため、各部分の時間はT（n/k）になります。そしてあなたはこれらのkを解いています。したがって、k * T（n/k）時間がかかります。

これらの小さな問題を解決したら、それらのソリューションを組み合わせます。これにはもう少し時間がかかります。そしてその時はあなたの問題の大きさの関数になります。 （それは一定であってもよい）。その時間をO（f（n））とする。

だから、あなたのアルゴリズムで撮影した合計時間は次のようになります。 T（N）=（K・T（N/K））あなたは漸化式を持っている

+ O（nはF（））今あなたはT（n）を得るために解くことができます。このリンクとして

Answer 2

を示す：T(2)ため

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

を、それが返す前に、単一の比較でベースです。 T(1)の場合、比較のないベースです。 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
我々は、各k < n
T(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2
（*）誘導仮定のためT(k) = (3/2)k - 2を想定しているため真であります

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