1

質問の例として、c>2配列をほぼ同じサイズの配列に分割するマージソートのバリアントを作成するように求められます (c = 2通常のマージを使用する場合) 。

これが解決策です：

 cmerge(a1, a2, .... ac)
    if c = 2 return Merge(a1, a2)
     else 
     b1 = cmerge(a1, a2,...a(c/2), floor(c/2))
     b2 = cmerge(a(roof(c/2)),... ac, roof(c/2))
     return merge(b1,b2)

彼らがこの解決策をどこで得たのかは理解していますが、繰り返し関係を求めると少し混乱します。O(n log c) 質問では、最初のケースを明確にするcソートされた配列をマージできると述べています

T(n) = c(T(n/c)) + nlogc if n>= c
T(n) = theta(n^2) for n<c   <----------- can someone explain where they are getting this?

n^2がどこから来ているのか本当にわかりません。2 番目のケースでは、MERGE への呼び出しが 1 つだけではありませんか? theta(n)私が覚えていればマージです。

4

0 に答える 0