时间复杂度：使用唯一键的插入排序

我有一个随机排列的数组，其中只有3个不同的键（TRUE，FALSE和NULL），我想使用插入排序进行排序。时间复杂度是多少？假设是最坏情况还是O（n），假设是最好的情况，因为只有3个不同的密钥，它会是O（n ）吗？时间复杂度：使用唯一键的插入排序

2012-04-16 Neel

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

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

例如，在平均情况下的，而不是插入检查Ñ元件，它将检查^Ñ/元件。这比较好，但不是渐近的。

2012-04-17 00:00:14 Oleksi

值得注意的是，平均情况也是O（n^2）。 – Aidanc 2012-04-17 00:04:22

已更新，以反映此情况。 :) – Oleksi 2012-04-17 00:05:02

由于它是随机有序数组，时间复杂度应该是其最坏情况下的复杂度。但假设只有3个不同的密钥，并且顺序对于相同的密钥无关紧要，时间复杂度是否会改变？ – Neel 2012-04-17 00:06:03

回答