我正在学习CLRS的第3章，它是关于运行时间的，我想学习一些例子由于我没有参加算法课程，我需要求助于www。
1）n^2=大Ω（n^3）
我认为这句话是错误的：如果最佳运行时间是n^3，那么算法不能是n^2即使是最好的情况也比这慢。
2）n+对数n=大θ（n）
我认为这句话是对的，我们可以忽略log n的下项，这给了我们一个最坏的运行时间big-oh（n）。以及大欧米茄（n）的最佳运行时间。不过，我不太确定。希望能有更多的澄清。
3）n^2 log n=大Oh（n^2）
我认为this.statement是错误的：最坏的运行时间应该是n^2 logn。
4）n对数n=大oh（n sqrt（n））
可能是真的，因为n logn5）n^2-3n-18=大θ（n^2）
真的不知道…
6）如果f（n）=O（g（n））和g（n）=O（h（n）），则f（n）=O（h（n））。
由可传递属性持有。
我希望有人能详细解释一下我的答案，可能是错误的：）
最佳答案
你是对的，但原因不是。记住，ω（n^3）不直接与算法有关，而是与函数有关。
之所以你是正确的，是因为：对于每个常数c,N，都有一些n>N，因此n^2 < c * n^3不在n^2中
你是对的。Omega(n^3)（对于足够大的n），因此n < n + logn < 2*n同时是n + logn和O(n)
你是对的，但是再一次，不要在这里使用“最坏的情况”。解释和证明指南将类似于1。
这是正确的，因为Omega(n)是渐近小于log(n)的，其余的如下。
与1相同的原则同样的方法也是如此。
对的。
作为一个旁注：sqrt(n)并不意味着“Omega(n)的最佳运行时间”，这意味着表示复杂度的函数（可以是最坏情况复杂度、最佳情况复杂度或平均情况复杂度……）保持为n的条件。
例如-快速排序：
在最坏情况下，它是Omega(n)
而在平均案例分析下，它是Theta(n^2)
关于algorithm - 证明或反对关于运行时间的陈述，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13551283/