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

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

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