我一直在尝试找出这个问题的答案，但没有成功，也许你可以引导我一点: 我们更改合并排序，以便当您已经对数组进行排序时，它会停止并返回数组，而无需调用另外 2 个递归调用。 例如，让我们在数组上运行算法，数组中的每个数字恰好出现 n/log(n) 次，(以便数组恰好包含 log(n) 个不同的数字)现在运行时间复杂度是多少？
最佳答案
“我们更改了合并排序，以便当您已经对数组进行排序时它会停止并返回数组，而无需调用另外 2 个递归调用。”
这就是正常合并排序的工作原理。在对数组(或数组的一部分)进行排序后，它不再调用任何递归调用，它只返回排序后的数组。调用递归是为了首先对数组的部分进行排序。
也许您想说“在我们对两半进行递归排序并合并它们之前，我们检查数组是否已经排序”。这对于具有不同数字的数组毫无用处，因为数组被排序的可能性极低 (1/n!)。
你的例子更有趣，但是如果数组只有 log(n) 不同的数字，我会建议对唯一值进行排序并创建一个从值到索引的 hashmap，这是快速的仅 log(n) 值，然后您可以使用桶排序等线性时间排序。
关于java - 更改合并排序后的运行时间复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55707249/