拆分不均匀的合并排序变体？
Mergesort variation with an uneven split?
合并排序的一种变体称为 a-to-b 合并排序(A,low,high) 总是按照 a:b 的比率从索引低到高划分数组 A 的未排序段，而不是使 1:1 division.Compute 成为 a-to-b 归并排序的时间复杂度。
我试图解决并获得了这个：
T(n)=aT(n/b)+O(n)。根据大定理，A)If a>b T(n)=O(n^(loga/logb)(B)If a =b T(n)=O(n^(loga/logb)*n)(C)如果a
为了使数学更简单，我们假设您有一个分数拆分，将 ε 部分的元素放在一个子调用中，其余的 (1 -ε) 另一个的分数。为简单起见，我们假设 1-ε ≥ ε 以便我们可以讨论数组的较大和较小的一半。
使用这种修改后的归并排序，每次调用仍然需要完成线性工作，再加上进行两次递归调用所需的工作，一次针对 εn 个元素，一次针对 (1-ε)n 个元素。这意味着我们有递推关系
T(n) = T(εn) + T((1-ε)n) + O(n)
那么这个递归解决了什么问题呢？好吧，我们可以通过几种不同的方式来考虑这个问题。我认为最简单的选择是想象一个递归树并计算每个级别的工作量。
假设我们有一个非常大的 n 并考虑递归树将采用什么形状。在顶层，我们有一个大小为 n 的调用。在下一层，我们有一个大小为 εn 的调用和一个大小为 (1-ε)n 的调用。在此之下，我们有一个大小为 ε2n 的调用，两个大小为 ε(1-ε)n 的调用，以及一个大小为 (1-ε)2n。 （现在是拿出 sheet 纸并将其画出来的好时机，这样您就可以看到发生了什么 - 通过视觉，这将非常有意义）。
这可能听起来毛骨悚然，但实际上并没有那么糟糕。请记住，每次调用完成的工作是 O(n)，因此我们可以通过总结树的每个单独层中所有调用完成的所有工作来确定每个级别的工作。顶层有一个大小为 n 的调用，因此完成了 O(n) 的工作。如果您总结第二层中所有调用的大小，您会发现它也适用于 n，因此该层中完成的总工作量为 O(n)。第三层的数学有点难，但所有调用的大小也可以达到 n，因此 O(n) 总工作也在该层完成。 （同样，请自行检查以确认您明白原因！）
原来这不是巧合。请注意，每个递归调用都将数组干净利落地分成两部分，并分别对每个部分进行递归，因此当我们从一层转到下一层时，子调用中数组的总大小应始终为 n。 （好吧，主要是。最终数组变得如此之小以至于递归触底，但稍后会更多）。这意味着我们在每个级别上做 O(n) 工作，所以完成的总工作将是 O(n) 乘以层数。那是什么？
好吧，与许多分而治之算法一样，请注意，在此算法中，每个子数组的大小始终比原始数组小一个常数分数。每当您看到这种模式时，您应该迅速得出结论，即在 O(log n) 步之后，数组的大小缩小到 1，我们就完成了。为什么？因为如果你重复除以一个常数，它需要 O(log n) 次迭代才能缩小到一个大小。
总的来说，这个非常粗略的分析告诉我们运行时间应该是 O(n log n)：每层 O(n) 工作和 O(log n) 层。
现在，这里有一些问题需要注意，因为递归树的形状有点奇怪。具体来说，由于分裂不平衡，树将不是完整的二叉树，收缩系数 ε 的分支在收缩系数 (1-ε) 的分支之前触底。不过，这不是问题。如果我们假装所有这些丢失的调用仍然会发生，我们最终会过度估计已完成的总工作量，因此我们的 O(n log n) 界限在最坏的情况下夸大了运行时间。事实证明它是渐近紧的。一种看待这一点的方法是，在收缩因子 ε 的分支消失之前有 O(log n) 层，并且在对应于该区域的树的部分我们知道 O(n log n) 工作已经完成.
这看起来像是家庭作业，所以我将把填补所有空白和计算所有对数底数的细节留作练习。祝你好运！
合并排序的一种变体称为 a-to-b 合并排序(A,low,high) 总是按照 a:b 的比率从索引低到高划分数组 A 的未排序段，而不是使 1:1 division.Compute 成为 a-to-b 归并排序的时间复杂度。 我试图解决并获得了这个： T(n)=aT(n/b)+O(n)。根据大定理，A)If a>b T(n)=O(n^(loga/logb)(B)If a =b T(n)=O(n^(loga/logb)*n)(C)如果a
为了使数学更简单，我们假设您有一个分数拆分，将 ε 部分的元素放在一个子调用中，其余的 (1 -ε) 另一个的分数。为简单起见，我们假设 1-ε ≥ ε 以便我们可以讨论数组的较大和较小的一半。
使用这种修改后的归并排序，每次调用仍然需要完成线性工作，再加上进行两次递归调用所需的工作，一次针对 εn 个元素，一次针对 (1-ε)n 个元素。这意味着我们有递推关系
T(n) = T(εn) + T((1-ε)n) + O(n)
那么这个递归解决了什么问题呢？好吧，我们可以通过几种不同的方式来考虑这个问题。我认为最简单的选择是想象一个递归树并计算每个级别的工作量。
假设我们有一个非常大的 n 并考虑递归树将采用什么形状。在顶层，我们有一个大小为 n 的调用。在下一层，我们有一个大小为 εn 的调用和一个大小为 (1-ε)n 的调用。在此之下，我们有一个大小为 ε2n 的调用，两个大小为 ε(1-ε)n 的调用，以及一个大小为 (1-ε)2n。 （现在是拿出 sheet 纸并将其画出来的好时机，这样您就可以看到发生了什么 - 通过视觉，这将非常有意义）。
这可能听起来毛骨悚然，但实际上并没有那么糟糕。请记住，每次调用完成的工作是 O(n)，因此我们可以通过总结树的每个单独层中所有调用完成的所有工作来确定每个级别的工作。顶层有一个大小为 n 的调用，因此完成了 O(n) 的工作。如果您总结第二层中所有调用的大小，您会发现它也适用于 n，因此该层中完成的总工作量为 O(n)。第三层的数学有点难，但所有调用的大小也可以达到 n，因此 O(n) 总工作也在该层完成。 （同样，请自行检查以确认您明白原因！）
原来这不是巧合。请注意，每个递归调用都将数组干净利落地分成两部分，并分别对每个部分进行递归，因此当我们从一层转到下一层时，子调用中数组的总大小应始终为 n。 （好吧，主要是。最终数组变得如此之小以至于递归触底，但稍后会更多）。这意味着我们在每个级别上做 O(n) 工作，所以完成的总工作将是 O(n) 乘以层数。那是什么？
好吧，与许多分而治之算法一样，请注意，在此算法中，每个子数组的大小始终比原始数组小一个常数分数。每当您看到这种模式时，您应该迅速得出结论，即在 O(log n) 步之后，数组的大小缩小到 1，我们就完成了。为什么？因为如果你重复除以一个常数，它需要 O(log n) 次迭代才能缩小到一个大小。
总的来说，这个非常粗略的分析告诉我们运行时间应该是 O(n log n)：每层 O(n) 工作和 O(log n) 层。
现在，这里有一些问题需要注意，因为递归树的形状有点奇怪。具体来说，由于分裂不平衡，树将不是完整的二叉树，收缩系数 ε 的分支在收缩系数 (1-ε) 的分支之前触底。不过，这不是问题。如果我们假装所有这些丢失的调用仍然会发生，我们最终会过度估计已完成的总工作量，因此我们的 O(n log n) 界限在最坏的情况下夸大了运行时间。事实证明它是渐近紧的。一种看待这一点的方法是，在收缩因子 ε 的分支消失之前有 O(log n) 层，并且在对应于该区域的树的部分我们知道 O(n log n) 工作已经完成.
这看起来像是家庭作业，所以我将把填补所有空白和计算所有对数底数的细节留作练习。祝你好运！