java - 求某些条件下归并排序的时间复杂度

Question

给定更改的合并排序算法，如果数组已经排序，算法将返回数组，而不是进行 2 次以上的递归调用。假设我们在一个数组上运行新算法，其中每个值恰好出现 n/log(n) 次。 (为此，数组包含 log(n) 个不同的值)。

该算法的时间复杂度是多少？

Answer 1

如果您怀疑数组中的不同值很少，那么扫描数组以提取这些值、对它们进行排序并进行计数将比对数组执行完全合并排序花费更少的时间:

• 如果您使用哈希表，选择值将花费 O(N) 时间，生成大小为 log(N) 的样本数组。
• 对此样本数组进行排序应花费O(log(N).log(log(N))，与扫描阶段相比可以忽略不计。
• 枚举样本数组以生成原始数组的副本也具有线性时间复杂度O(N)。

因此时间复杂度可以降低到O(N)。

但请注意:

• 使用哈希表来构造示例数组可能不可行。相反，如果您构造一个排序列表，则由于每个元素都会线性查找示例数组，因此复杂性会跳回 O(N.log(N))。
• 如果原始数组的元素具有相同的键但内容不同，则生成元素的副本可能不够。在这种情况下，您将扫描原始数组并在示例数组中查找元素的键，以确定将元素存储在结果数组中的位置，同样是 O(N.log(N)) 时间复杂度如果示例数组是一个列表，则 O(N.log(log(N))) 如果它是一个数组并且您使用二分搜索。

综上所述，在特殊情况下可以有效降低复杂度，但在一般情况下却很棘手。