在 Cormen 定理 3.1 中说
例如，插入排序的最佳情况运行时间是big-omega(n)，而插入排序的最坏情况运行时间是Big-oh(n^2)。因此插入排序的运行时间介于big-omega(n)和Bigoh(n^2)之间
现在，如果我们看一下练习 3.1-6，它会问
证明一个算法的运行时间是Big-theta(g(n))当且仅当其最坏情况的运行时间是Big-oh(g(n))并且其最佳情况的运行时间是big-omega(g(n))
There is no contradiction here. The question only states to prove that Big-Theta(g(n)) is asymptotically tightly bound by Big-O(g(n)) and Big-Omega(g(n)). If you prove the question, you only prove that a function runs in Big-Theta(g(n)) if and only if it runs between Big-O(g(n)) and Big-Omega(g(n)).
The insertion sort runs from Big-Omega(n) to Big-Oh(n^2), so the running time of insertion sort CANNOT be tightly bound to Big-Theta(n^2).
As a matter of fact, CLRS never uses Big-Theta(n^2) to tightly bound insertion sort.
我想你在这里有点困惑。让我为你澄清几点。
运行时间可能意味着两件事：程序的实际运行时间，或者像 theta 或 big-oh 这样的有界函数（所以它有助于调用这个时间复杂度，以避免混淆）。下面我们将运行时间用于程序的实际运行时间，以及表示 Big-Oh/theta 符号的时间复杂度。
要拿起 Big-Oh，请在此处阅读我的答案。
一旦你清楚了 Big-Oh，其他函数就很容易就位了。当我们说 T(n) 是 Omega(g(n)) 时，我们的意思是在某个点 k 的右侧，曲线 cg(n) 将下面的运行时间曲线。或者换句话说：
T(n)>=c.g(n) for all n>=k, and for some constant c independent of input size.
而 theta 表示法就像在说“我只是一个函数，但使用不同的常数，你可以让我从上方和下方绑定运行时间曲线”
所以当我们说 T(n) 是 theta(g(n)) 时，我们的意思是
c1.g(n)==k
现在我们知道了这些函数的含义，让我们看看 CLRS 的困惑所在。
例如，插入排序的最佳情况运行时间是 big-omega(n)，而插入排序的最坏情况运行时间是 Big-oh(n^2)。因此插入排序的运行时间介于 big-omega(n) 和 Bigoh(n^2) 之间
这里的运行时间 CLRS 是指实际运行时间 T(n)。它的措辞很糟糕，你误解了这不是你的错。事实上我会继续说他们错了。没有什么像fall in between，一个函数要么在集合 O(g(n)) 中，要么不在。所以这是一个错误。
证明一个算法的运行时间是 Big-theta(g(n)) 当且仅当其最坏情况的运行时间是 Big-oh(g(n)) 并且其最佳情况的运行时间是 big-omega(g(n))
此处 CLRS 表示运行时间函数 T(n)，他们希望您计算出时间复杂度。
没有矛盾，因为 CLRS 没有提到插入类型是 theta(N^2)。