在某些条件下查找归并排序的时间复杂度

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)))如果它是一个数组并且你使用二进制搜索。

总而言之，在特殊情况下可以有效地降低复杂性，但在一般情况下却很棘手。