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

Question

こんにちは、私はアルゴリズムを勉強しており、マスター定理を使わずにO

私はO（nlogn）を取得するためにトラブルを抱えています。..

誰もが数学的な方法は、T（N）= 2T（N/2）+ O（n）のからO（nlogn）を取得することを知っています？

おかげ

Answer 1

は再帰ツリーを描く：ツリーの

高さがログになりN各レベル

コストは、一定時間N従って

総コストであることが出てきますO（nlogn）になります。 http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm

そして、あなたが望むならば、あなたはいつも誘導によってそれを証明することができます。パターン（良好簡略化ビットは、むしろnよりO(n)を維持するであろう）

Answer 2

注意：

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))