Ujj*_*mik 3 sorting algorithm mergesort time-complexity
合并排序的一种变体称为 a-b 合并排序(A,low,high)，它始终按照 a:b 的比例将数组 A 的未排序段从索引 low 到 high 划分，而不是进行 1:1 除法。计算a-b 归并排序的时间复杂度。我试图解决并得到这个： T(n)=aT(n/b)+O(n)。根据主定理，A)If a>b T(n)=O(n^(loga/logb)( B)如果a=b T(n)=O(n^(loga/logb)*n)(C)如果a<b T(n)=O(n^(loga/logb)这个解正确吗？
为了使数学更容易，我们不考虑分割的 a:b 比率，而是假设您有一个分数分割，将元素的 ε 分数放入一个子调用中，将剩余的 (1-ε) 分数放入另一个子调用中。为简单起见，我们假设 1-ε ≥ ε，以便我们可以讨论数组的较大和较小的一半。
使用这种修改后的合并排序，每次调用仍然需要完成线性工作，再加上执行两次递归调用所需的工作，一次针对 εn 元素，一次针对 (1-ε)n 元素。这意味着我们有递推关系
T(n) = T(εn) + T((1-ε)n) + O(n)
那么这个重复是为了解决什么问题呢？嗯，我们可以通过几种不同的方式来思考这个问题。我认为最简单的选择是想象一个递归树并计算每个级别的工作量。
想象一下我们有一个非常大的 n 并考虑递归树将采取什么形状。在顶层，我们有一个大小为 n 的调用。在下面的级别上，我们有一个大小为 εn 的调用和一个大小为 (1-ε)n 的调用。下面我们有一个大小为 ε 2 n 的调用，两个大小为 ε(1-ε)n 的调用，以及一个大小为 (1-ε) 2 n 的调用。（这将是拿出一张纸并将其画出来的好时机，这样您就可以看到正在发生的事情 - 通过视觉，这将很有意义）。
这听起来可能有点毛茸茸和可怕，但实际上并没有那么糟糕。请记住，每个调用完成的工作是 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) 工作已完成。
这看起来像家庭作业，所以我将把填充所有空白和计算所有对数的底的细节作为练习。祝你好运！