混乱

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）