時間複雜度：使用唯一鍵的插入排序

我有一個隨機排列的數組，其中只有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

回答