algorithm - T（n）= 2T（n / 2）+ O（n）からO（nlogn）を取得する方法

Question

O(n log(n))マスター定理を使わずに計算したい。

O(n log(n))再帰式から計算する数学的な方法を知っている人はいますT(n) = 2T(n/2) + O(n)か？

Answer 1

O(n)パターンに注意してください（少し単純化されていますが、保持するよりも保持する方が良いでしょうn）：

T(n) = 2T(n/2) + n
     = 2(2T(n/4) + n/2) + n  = 4T(n/4) + n + n  = 4T(n/4) + 2n
     = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
     = 8(2T(n/16) + n/8)+ 3n = 8T(n/16)+ n + 3n = 16T(n/16) + 4n
     ...                                        = 32T(n/32) + 5n
     ...
                                                = n*T(1) + log2(n)*n
                                                = O(n*log2(n))

Answer 2

再帰ツリーを描画します。

木の高さはlognになります

各レベルのコストは一定時間nになります

したがって、総コストはO（nlogn）になります。http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm

そして、あなたが望むなら、あなたはいつでも誘導によってそれを証明することができます。

Answer 3

再帰ツリーを描画する方法をまだ理解している人のために：

画像：T（n）= 2T（n / 2）+ O（n）アルゴリズムの再帰ツリー

以下のように木を描くと、2で割って、葉が1に等しくなるまで進むたびにわかります。

n/2^k = 1 
2^k = n 
k= log(n)

上記のステートメントは、ツリーの深さがlog（n）であることを証明しています。

各レベルで、O（n）のコストがかかる操作を実行します。

毎回2で除算しますが、両方の部分で操作を実行するため、各レベルでn回の反復が行われます。

深さに等しい回数実行するため、結果として得られる複雑さはO（nlog（n））です。

また、このビデオチュートリアルhttps://youtu.be/1K9ebQJosvoをチェックしてください