混亂

Question

有人問我這樣一個問題：

以下哪種排序算法有最壞情況下運行Ω（N2）的時間 - 冒泡排序，堆排序，插入排序，合併排序，快速排序（具有良好的中位數發現），選擇排序。

有人可以解釋什麼需要做？

Answer 1

簡而言之，分析的類型和符號是單獨的術語。對於任何分析（包括：最好的情況，最壞的情況，平均情況），你都可以應用大O，小O，大O Omga，小Omega，大θ等等（如波浪符號）。

你有類型的分析。這使您複雜的功能，例如像對合並排序的最差情況：

T(n) = 2T(n/2) + CONST*n + SOME_CONSTANT 

然後，您可以分析這個T(n)並得出一些結論。漸近符號是一組函數，或具有共同漸近行爲的「函數族」。對於上述的例子，可以斷定：

• 這個函數在西塔（nlogn）
• 該功能是在O（nlogn）
• 該功能是在歐米加（1）
• 此功能在O（n^3）