混合排序的时间复杂度（冒泡排序的修改）

Question

所以我尝试用主定理解决这个问题，但不确定我的解决方案是否正确：

function MixedSort(A[1..n]){
    if (n==1) {
        return A[1];
    }
    m = n/2;
    B[1 ... m] = bubbleSort(A[1...m]) //normal Bubblesort function O(m^2)
    B[m+1 ... n] = MixedSort(A[m+1 ... n])
    return Merge(B[1 ... m], B[m+1 .. n]) //merges 2 sorted arrays in O(n)
}

• T(1) = 1
• T(n) = T(n/2)+n^2+n = T(n/2)+n^2

然后使用主定理并得到 O(n^2) 因为 1<2^2=4

Answer 1

是

O(n^2)

，是的。你甚至不需要主定理就能看到这一点。递归关系如下：（

O((n/2)^2)

和

O(n)

项来自冒泡排序和合并。）

T(n) := T(n/2) + O((n/2)^2) + O(n)

但是

O((n/2)^2)

等价于

O(n^2)

和

O(n^2)

矮人

O(n)

，因此可以省略

O(n)

项，得到

T(n) := T(n/2) + O(n^2).

递归

T(n) = T(n/2) + n^2

可以使用递归树方法来解决。在递归的每个级别，问题大小减半（n/2），处理每个级别需要 O(n^2) 时间。

总时间复杂度是每个级别完成的工作的总和，形成级数：

T(n) = n^2 + (n^2 / 4) + (n^2 / 16) + ... (n^2 / 2^k)

由于该级数的所有项都是常数乘以 n^2，我们可以重新排列为

T(n) = n^2 * (1 + 1/4 + 1/16 + ...)

该级数收敛为常数，因此运行时间为 O(n^2)。