递归版本中合并排序的 运行 时间

Question

我了解到归并排序的时间函数就在下面。

T(n) = 2T(n/2) + Θ(n) if n>1

明白为什么了T(n) = 2T(n/2)+ A

但是为什么 A = Θ(n)？

我觉得A可能是在划分时间，但是我不明白为什么要表达成Θ(n)

请帮忙！

Answer 1

不是，A不是分割步骤。 A是线性合并步骤

void merge(int a[], int b[], int p, int q, int c[])
/* Function to merge the 2 arrays a[0..p} and b[0..q} into array c{0..p + q} */
{
    int i = 0, j = 0, k = 0;

    while (i < p && j < q) {
        if (a[i] <= b[j]) {
            c[k] = a[i];
            i++;
        }
        else {
            c[k] = b[j];
            j++;
        }
        k++;
    }
    while (i < p) {
        c[k] = a[i];
        i++;
        k++;
    }
    while (j < q) {
        c[k] = b[j];
        j++;
        k++;
    }
}

当 p 和 q 是子数组长度时，此合并步骤需要 O(p + q) 时间，这里 p + q = n.