在合并排序算法递推关系 [英] recurrence relation on a Merge Sort algorithm

问题描述

现在的问题是：

不平衡合并排序 是一个排序算法，这是一个修改后的版本 标准合并排序 算法。唯一不同的是，代替分割 将输入到在每一个阶段2等份，我们把它分成两个不相等的部分 - 第一 2/5的输入的，另一3/5

UNBALANCED MERGE SORT is a sorting algorithm, which is a modified version of the standard MERGE SORT algorithm. The only difference is that instead of dividing the input into 2 equal parts in each stage, we divide it into two unequal parts – the first 2/5 of the input, and the other 3/5.

一个。写出的最坏情况下的时间复杂度的递推关系 非平衡归并排序 算法。

a. Write the recurrence relation for the worst case time complexity of the UNBALANCED MERGE SORT algorithm.

乙。什么是UNBALANCEDMERGESORT的最坏情况的时间复杂度 算法？解决从previous节的递推关系。

b. What is the worst case time complexity of the UNBALANCEDMERGESORT algorithm? Solve the recurrence relation from the previous section.

所以，我在想的递推关系为：T（n）的＆LT; = T（2N / 5）+ T（3N / 5）+ DN。 不知道如何解决它。 先谢谢了。

So i'm thinkin the recurrence relation is : T(n) <= T(2n/5) + T(3n/5) + dn. Not sure how to solve it. Thanks in advance.

推荐答案

我喜欢把它看作运行，其中我日运行是ALL随着深度的递归步骤完全我。

I like to look at it as "runs", where the ith "run" is ALL the recursive steps with depth exactly i.

在每一个这样的运行，最多 N 元素正在处理中（我们将很快证明这一点），所以总的复杂性是由界Ø （N * MAX_DEPTH），现在， MAX_DEPTH 是对数，在每一步的更大的阵列尺寸 3N / 5 ，所以在步骤我，最大的数组大小 3 ^ I / 5 ^ I * N 。
求解带等式：

In each such run, at most n elements are being processed (we will prove it soon), so the total complexity is bounded by O(n*MAX_DEPTH), now, MAX_DEPTH is logarithmic, as in each step the bigger array is size 3n/5, so at step i, the biggest array is of size 3^i/5^i * n.
Sovle the equation:

3^i/5^i * n = 1

，你会发现， I = log_a（N） - 对于一些基本的 A

and you will find out that i = log_a(n) - for some base a

所以，让我们更加正式的：

So, let's be more formal:

声明：

每个元素是由在深度最多只有一个递归调用处理   我为的所有值我。

Each element is being processed by at most one recursive call at depth i, for all values of i.

证明：

通过归纳，在深度0，所有的元素都是由第一次调用处理一次。
让我们有一些元素 X ，让我们有它看看步骤i + 1。我们知道（归纳假设）的 X 进行了深入处理最多一次我，一些递归调用。此调用后调用（或没有，我们要求最多一次），深度 I + 1 的递归调用，并派元素 X 向左或向右，绝不两者。因此，在深度 I + 1 的元素 X 的proccessed最多一次。

By induction, at depth 0, all elements are processed exactly once by the first call.
Let there be some element x, and let's have a look on it at step i+1. We know (induction hypothesis) that x was processed at most once in depth i, by some recursive call. This call later invoked (or not, we claim at most once) the recursive call of depth i+1, and sent the element x to left OR to right, never to both. So at depth i+1, the element x is proccessed at most once.

结论：

由于每一深度处 I 递归的，每个元件设置在处理最多一次，和递归的最大深度是对数，我们得到了一个上限的 O（nlogn）。

Since at each depth i of the recursion, each element is processed at most once, and the maximal depth of the recursion is logarithmic, we get an upper bound of O(nlogn).

我们同样可以证明一个下界的欧米茄（nlogn），但是这是没有必要的，因为排序已经是一个欧米茄（nlogn） 的问题 - 因此，我们可以得出结论：改进后的算法仍然西塔（nlogn）

We can similarly prove a lower bound of Omega(nlogn), but that is not needed, since sorting is already an Omega(nlogn) problem - so we can conclude the modified algorithm is still Theta(nlogn).

如果你想与基本算术来证明这一点，它也可以做，通过感应。

If you want to prove it with "basic arithmetics", it can also be done, by induction.

声明： T（N）= T（3N / 5）+ T（2N / 5）+ N＆LT; = 5nlog（N）+ N
更换时，这将是类似 + N 与 + DN ，我简化它，而是遵循了同样的想法与证明T（n）的＆LT; = 5dnlogn + DN

Claim: T(n) = T(3n/5) + T(2n/5) + n <= 5nlog(n) + n
It will be similar when replacing +n with +dn, I simplified it, but follow the same idea of proof with T(n) <= 5dnlogn + dn

证明

文章：T（1）= 1＆LT; = 1log（1）+ 1 = 1

Base: T(1) = 1 <= 1log(1) + 1 = 1

T(n) = T(3n/5) + T(2n/5) + n 
<= 5* (3n/5) log(3n/5) +3n/5 + 5*(2n/5)log(2n/5) +2n/5 + n
< 5* (3n/5) log(3n/5) + 5*(2n/5)log(3n/5) + 2n
= 5*nlog(3n/5) + 2n
= 5*nlog(n) + 5*nlog(3/5) + 2n
(**)< 5*nlog(n) - n + 2n
= 5nlog(n) + n

（**）是因为日志（3/5）〜= -0.22，所以 5nlog（3/5）＆LT; -n 和 5nlog（3/5）+ 2N＆LT; ñ

这篇关于在合并排序算法递推关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！