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