sorting - 时间复杂度：具有唯一键的插入排序

Question

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

Answer 1

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

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

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

例如，在一般情况下，插入检查n 个元素而不是检查ⁿ / _{3 个}元素。这更好，但不是渐近的。