ビッグ・オア・マージ・ソート

Question

マージ・ソートのためにビッグ・オーで講義をしましたが、私は混乱します。示されたもの

である：

0マージ[< ----- N -------->] = N

1マージ[<、-N/2-- [n/4] [n/4] [n/4] =（n/2 + n/2）= n/2] 2（N/4 + N/4）= N

....

ログ（N）は、n =

が合計=（N + N + N + ... + N）= LG N = O（nはn個のログ）

私はなぜ（N + N +理解していないマージします。 .. + n）は、nのlog base 2と2回のマージ= 2（n/4 + n/4）のためにどのように表現することができますか？

Answer 1

あなたの質問に書かれた以下の部分の最後の行は、

0マージ[< ----- N -------->] = N

n/2] =（n/2 + n/2）= n

2マージ[n/4] [n/4]マージ[n/4] [n/4] [n/4] [n/4] = 2（n/4 + n/4）= n

....

n merges = n - この行は間違っています！

が間違っています。サイズnの合計n個のマージはありませんが、サイズnのログn個のマージはありません。

すべてのレベルで、問題のサイズを半分の2つの問題に分割します。あなたがダイビングを続けると、あなたができる部門はLog nです。 （の合計部門可能としましょうどうしますか？あるX。その後、N = ^X 2またはX =ログのn。）

各レベルでは、ログのために、したがって、O（n）との合計作業を行うので、すべての作業の合計はO（n Log n）になります。

Answer 2

log（n）とaあなたのツリーのnの幅。 :)

Answer 3

ログの部分は、「1つだけの要素が残る前にデータを2回に分けることができますか？」の結果です。これはあなたの再帰ツリーの深さです。 nの倍数は、ツリー内の各レベルについて、そのレベルですべてのステップをマージした後で、データセット内のすべての要素を一度調べるという事実から来ています。 1つのマージの場合

recurse downwards: 
    n unsorted elements 
    [n/2][n/2] split until singletons... 
    ... 
merge n elements at each step when recursing back up 
    [][][]...[][][] 
    [ ] ... [ ] 
    ... 
    [n/2][n/2] 
    n sorted elements 

Answer 4

、各サブアレイをソートするN/2に比例する時間がかかる場合にソートされる2個のサブアレイを有しています。その意味で、これらの2つのサブ配列をソートするには、nに比例する時間が必要です。

あなたは2つのマージを行っている場合も同様に、それぞれが再びNまで合計するN/4に比例する時間を割いされる場所にソートされる4つのサブ・アレイがあります。

同様に、あなたはn個マージを持っている場合、それはすべてのサブ配列をソートするためにNに比例する時間がかかります。その意味で、マージソートにかかる時間を以下のように書くことができます。

T（N）= 2 * T（N/2）+ N

は、あなたは、この再帰呼び出しがn/(2^h) = 1まで（時間の高さに言う）深い行くことができることを理解するであろう。ここにログを取ることによって、我々はh = log（n）となる。それがlog（n）がどのように現れたかです。ここでログはベース2から取得されます。

もしログ（n）の各ステップはNに比例する時間を要するステップを有しているので、かかる合計時間は

N *ログ（N）

、のように表すことができます。

大きなO表記では、これを上限として与えますO(nlog(n))。あなたはアイデアを持っているといいですね。

次の再帰ツリーのイメージは、さらにあなたを啓発します。

Answer 5

非常に簡単です。それぞれのマージには、O（n）が必要です。マージの回数は、ログn（ベース2）です。これは、各マージがソートされたセクションのサイズを2倍にするためです。