不平衡分区会影响归并排序的复杂度吗
does imbalance partition affect complexity of merge sort
我知道归并排序的复杂度在所有情况下都是 (n logn) 但是，如果切割或分区不平衡，比如一边是 4，另一边是 5，怎么办，
例如。 9 个元素的数组会在 4 个索引处进行切割，这种不平衡也会导致复杂性从 n logn 发生变化...
它是否从 n log 变为任何其他形式，如快速排序，最好的情况是 n logn，但不平衡枢轴导致从 n logn 变为 n2
好吧，合并排序的时间复杂度为 Θ(n . log n) all cases。
这将包括所讨论的大小 'n' 为奇数的情况。
这是因为当您考虑大 O 表示法中的时间复杂度时，您总是会删除最终计算复杂度时可能出现的低阶项。如果 'n' 是奇数，您只需考虑一些额外的低阶项，但它们不会影响复杂性。如需进一步说明，请参阅以下示例。
例如
'n'是项数，'c'分合的常数时间
在计算归并排序的复杂度时，我们得到：
cn(log n + 1)。 （这里'log n + 1'给出树的层数）
然而，在 Big-Oh 中表示时，低阶项 '+1' 和常量 c 被丢弃，因此我们得到 Θ(n . log n)。
类似地，在 'n' 为奇数的情况下，您会在最终的复杂性中得到一些额外的低阶项，但它们无关紧要，因为它们会被丢弃。复杂性并没有像你怀疑的那样增加。希望它是清楚的。
如果不是，请参阅此 link 以获得更好的理解：https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort
我知道归并排序的复杂度在所有情况下都是 (n logn) 但是，如果切割或分区不平衡，比如一边是 4，另一边是 5，怎么办，
例如。 9 个元素的数组会在 4 个索引处进行切割，这种不平衡也会导致复杂性从 n logn 发生变化...
它是否从 n log 变为任何其他形式，如快速排序，最好的情况是 n logn，但不平衡枢轴导致从 n logn 变为 n2
好吧，合并排序的时间复杂度为 Θ(n . log n) all cases。 这将包括所讨论的大小 'n' 为奇数的情况。
这是因为当您考虑大 O 表示法中的时间复杂度时，您总是会删除最终计算复杂度时可能出现的低阶项。如果 'n' 是奇数，您只需考虑一些额外的低阶项，但它们不会影响复杂性。如需进一步说明，请参阅以下示例。
例如 'n'是项数，'c'分合的常数时间
在计算归并排序的复杂度时，我们得到：
cn(log n + 1)。 （这里'log n + 1'给出树的层数）
然而，在 Big-Oh 中表示时，低阶项 '+1' 和常量 c 被丢弃，因此我们得到 Θ(n . log n)。
类似地，在 'n' 为奇数的情况下，您会在最终的复杂性中得到一些额外的低阶项，但它们无关紧要，因为它们会被丢弃。复杂性并没有像你怀疑的那样增加。希望它是清楚的。
如果不是，请参阅此 link 以获得更好的理解：https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort