algorithm - 归并排序在递归版本中的运行时间

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.