在科曼定理3.1中说
例如，插入排序的最佳运行时间是big omega（n），而插入排序的最坏运行时间是big oh（n^2）。
因此插入排序的运行时间介于大Ω（n）和大Ω（n^2）之间。
现在如果我们看练习3.1-6，它会问
证明了一个算法的运行时间是大θ（g（n））如果它的最坏运行时间是大oh（g（n））并且它的最佳运行时间是大ω（g（n））的话
我是唯一一个看到矛盾的人吗。
我的意思是，如果我们遵守必须证明的问题，我们的结论是，对于渐近紧界（f（n）=大θ（g（n）），我们需要f（n）=大ω（g（n））作为算法的最佳情况，大oh（g（n））作为算法的最坏情况。
但在插入排序最佳的情况下，时间复杂度是大ω（n），最坏情况下的时间复杂度是大OH（n ^ 2）。
最佳答案
我觉得你在这里有点困惑。让我为你澄清几点。
运行时间可能意味着两件事：程序的实际运行时间，或者像θ或大OH这样的有界函数（因此它有助于调用这个时间复杂度，以避免混淆）。Hereafter我们将使用运行时间来运行程序的实际运行时间，以及时间复杂度来表示大的OH/θ表示法。
要拿起大哦读我的答案here。
一旦你用big-oh弄清楚了，其他函数就很容易就位。当我们说t（n）是ω（g（n））时，我们是指在某个点k的右边，曲线c.g（n）从下面开始限定运行时间曲线。或者换句话说：
T(n)>=c.g(n) for all n>=k, and for some constant c independent of input size.
θ表示法就像是说“我只是一个函数，但是使用不同的常数，你可以让我从上面和下面，来限制运行时间曲线”
所以当我们说T（n）是θ（g（n））时，我们的意思是
c1.g（n）==k
现在我们知道这些函数的含义了，让我们看看clr在哪里陷入了混乱。
例如，插入排序的最佳运行时间是big omega（n），而插入排序的最坏运行时间是big oh（n^2）。因此插入排序的运行时间介于大Ω（n）和大Ω（n^2）之间。
这里的运行时间CLRS是指实际的运行时间T（n）。它的措辞很糟糕，你误会并不是你的错。事实上，我会继续说它们错了。没有什么能比介于两者之间，一个函数要么在集合O（g（n））中，要么不在集合O（g（n））中。所以这是一个错误。
证明了一个算法的运行时间是大θ（g（n））如果它的最坏运行时间是大oh（g（n））并且它的最佳运行时间是大ω（g（n））的话
这里的CLSR意味着运行时间函数T（n），它们希望您计算出时间复杂度。
关于algorithm - Cormen中关于插入排序的矛盾，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17457999/