sorting - 时间复杂度: Insertion sort with unique key

Question

我有一个由 30 个元素组成的随机排序数组，只有 3 个不同的键(TRUE、FALSE 和 NULL)，我想要对其进行排序使用插入排序。时间复杂度是多少？假设最坏情况是 O(n²) 还是假设最好情况是 O(n)，因为只有 3 个不同的键？

Answer 1

n 指的是数组的大小，而不是数组的可能元素。因此，复杂度是相同的:

• 最坏情况:O(n²)
• 最佳情况:O(n)
• 平均情况:O(n²)

拥有 3 个不同的元素将减少“插入”阶段必须检查的元素数量，但只会减少一个常数因子。这不会改变渐近运行时。

例如，在平均情况下，它不会检查 n 个元素，而是检查 ⁿ/₃ 元素。这更好，但不是渐近的。