我了解到归并排序的时间函数就在下面。
T(n) = 2T(n/2) + Θ(n) if n>1
我明白为什么 T(n) = 2T(n/2)+ A
但是为什么 A = Θ(n)
?
我觉得A
可能是时间的划分,但是我不明白为什么要表示成Θ(n)
请帮忙!
最佳答案
不,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
.
关于algorithm - 归并排序在递归版本中的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43049886/