合并排序除以 4 - 伪代码的时间复杂度

Question

我需要写一个合并排序的伪代码（除以4），并计算出它的时间复杂度（显然它的时间复杂度必须是Nlog(n)）。

这是我写的：

    Mergesort4(A){
    If   (n <= 1 ) return (A) 
    if (n=0) return(infinity) (Big number)

    k = (n/4)  m=(2n/4)  z=(3n/4)
    Return Merge4(Mergesort4(A[0..k-1]), Mergesort4(A[k..m-1]), 
                 Mergesort4(A[m..z-1]), Mergesort4(A[z..n-1), A[0..n-1])
    }

Merge4 - 将 B、C、D、R 数组分成 X。

合并函数合并2个数组，并为排序后的元素创建一个新数组。（Merge 函数就像 2-way Merge 排序一样）

Merge4(B,C,D,R,X){
          Merge(B,C,E)
          Merge(D,R,T)
          Merge(E,T,X)
}

时间复杂度让我感到困惑。

显然，T(n)=4T(n/4)（分为4题）

但我不确定除法之后会发生什么。

我最好的猜测是：T(n)=4T(n/4) + O(n)

指南将不胜感激...

Answer 1

最终，最终答案：

Mergesort4(A,p,r)
    If(q < r)
        q = floor( (p+r)/4 )
        Mergesort4(A, p, q)
        Mergesort4(A, q+1, 2q)
        Mergesort4(A, 2q+1, 3q)
        Mergesort4(A, 3q+1, r)
        Merge( A, p, q, q+1, 2q, 2q+1, 3q, 3q+1, r)


Merge( A, p, q, q+1, 2q, 2q+1, 3q, 3q+1, r )

    if(q != 0 && p != 0)
        Merge(A,p,q,2q)
    Merge(A,2q+1,3q,r)
    Merge(A,p,2q+1,r)

合并排序除以 4 - 伪代码的时间复杂度

Merge Sort divided by 4 - Time complexity of the pseudo code

sorting

merge

mergesort

pseudocode

time-complexity