合并排序算法的递归关系

Question

问题是：

不平衡的合并排序是一种排序算法，它是标准的合并排序算法。唯一的区别是，而不是划分在每个阶段将输入分成 2 个相等的部分，我们将它分成两个不相等的部分 - 第一个输入的2/5，另外3/5.

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

b。 UNBALANCEDMERGESORT 的最坏情况时间复杂度是多少算法？求解上一节的递归关系。

所以我认为递归关系是：T(n) <= T(2n/5) + T(3n/5) + dn。不知道如何解决。提前致谢。

Answer 1

我喜欢将其视为 "runs"，其中第 i 个 "run" 是深度正好为 i.

的所有递归步骤

在每个这样的运行中，最多n个元素正在被处理（我们很快就会证明），所以总复杂度受限于O(n*MAX_DEPTH)，现在，MAX_DEPTH 是对数的，因为在每一步中较大的数组大小为 3n/5，因此在步骤 i 中，最大数组的大小为 3^i/5^i * n。
求解方程：

3^i/5^i * n = 1

你会发现 i = log_a(n) - 对于某些基础 a

所以，让我们更正式一点：

索赔：

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 中最多被处理一次。此调用稍后调用（或不调用，我们最多声明一次）深度 i+1 的递归调用，并将元素 x 发送到左侧或右侧，而不是同时发送到两者。所以在深度 i+1，元素 x 最多被处理一次。

结论：

由于在递归的每个深度i，每个元素最多处理一次，并且递归的最大深度是对数的，我们得到一个上限O(nlogn)。

我们可以类似地证明 Omega(nlogn) 的下界，但这不是必需的，因为排序已经是一个 Omega(nlogn) 问题 - 所以我们可以得出结论，修改后的算法仍然是 Theta(nlogn).

如果想用"basic arithmetics"来证明，也可以用归纳法来证明

索赔： T(n) = T(3n/5) + T(2n/5) + n <= 5nlog(n) + n
将+n 替换为+dn 时类似，我简化了它，但遵循与T(n) <= 5dnlogn + dn

相同的证明思路

证明:

基础：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

(**)是因为log(3/5)~=-0.22，所以5nlog(3/5) < -n，而5nlog(3/5) + 2n < n

合并排序算法的递归关系

recurrence relation on a Merge Sort algorithm

algorithm

recurrence

mergesort

data-structures