は、データ構造のコースからの質問にいくつかの助けが必要です： 私はマージのこの再帰関数（擬似コード）与えられた：再帰マージ機能解析
Mergesort_1/3(A, p, r)
if p < r
then q = (p+(r-p)/3) // round the result down
Mergesort_1/3 (A,p,q)
Mergesort_1/3 (A,q+1,r)
Merge(A,p,q,r)
をし、これらの質問です：
は、古典的マージの要旨は、以下の再帰であることを証明：
を古典的なmergesortの複雑さとします。前述の手順は、それぞれO(1)（*）、2*O(TC(ceil(n/2)))、およびO(n)となります。これは再帰に役立ちますTC(n) = cc_0 + cc_1 * n + 2 * TC(ceil(n/2))。
リストが不均等に分割されている一般化されたマージソートを考えてみましょう。分割およびマージの複雑さは、（TG(x+1)代わりにTG(ceil(x))を使用して、ca_0、ca_1はO(_)表記に隠された定数である。mergesort_1/3用a=3）一般マージするための再帰TG(n) = ca_0 + ca_1 * n + TG(1/a * n + 1) + TG((a-1)/a * n + 1))への融資、同じままです。
この再発は、Akra-Bazzi-Methodを使用して解決できます。この目的のために は、再発は
k = 2
a_1 = 1
a_2 = 1
b_1 = 1/a
b_2 = (a-1)/a
g(x) = ca_0 + ca_1 * x
h_1(x) = 1
h_2(x) = 1
x_0 = 2
-> TG(x) = ca_0 + ca_1 * n + 1 * TG(1/a * x + 1) + 1 * TG((a-1)/a * x + 1) ; x >= x_0.
はAkra-Bazzi定理が必要です...設定することによって行うことができます
a_i, b_i const.
a_i > 0
0 < b_i < 1
|g(x)| = O(x^c); c const.
|h(x)| = O(x/(log(x))^2)
で
TG(x) = g(x) + \sum_i=1..k (a_i * TG(b_i * x + h_i(x)) ; x >= x_0.
として書き込まれる必要があります指数pは\sum_i=1..k (a_i * (b_i)^p) = 1にあります。そして、以下が成り立つ：
TG(x) = Θ (x^p \integral_(1, x) (g(u)/(u^(p+1)) du))
具体的には、
a_1 * b_1^p + a_2 * b_2^p = 1
=> (1/a)^p + ((a-1)/a)^p = 1
<=> p = 1
...とこれを...
TG(x) = Θ (x \integral_(1, x) ((ca_0 + ca_1 * u)/u^2 du))
= Θ (x [ - ca_0/u + ca_1 * log(u) ]_(1,x))
= Θ (- ca_0 + ca_1 * x * log(x) + ca_0 * x - ca_1 * x * log(1))
= Θ (x * log(x))
（*）厳密にバイナリ表現とメモリアクセスの基本的な算術演算がO(log n)あるので、これは間違っている話します。しかしながら、これは複雑さに関して漸近的に差を生じさせない。
2つではなく、このmergesortはパーティションを3つの等しいサイズのチャンクにします。したがって、サイズnの問題をサイズn/3の3つの問題に減らしています。さらに、マージするときは、3つのn/3サイズのソートされたチャンクをすべて通過しなければならず、その結果、合計n個の要素が処理されます。
Using Master Theorem（N/3）+ O（N）：ここ= 3、B = 3、Cしたがって、再発は次のように書くことができます。 = 1.Log Log ba = Log 3 = 1 = c。
したがって、再発は第2のケースに入り、T（n）=Θ（n c * Log（n））=Θ（n * Log（n））になります。