algorithm - Cormen 中关于插入排序的矛盾

Question

在 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))

---

• 是不是只有我一个人看到了这里的矛盾。
• 我的意思是，如果我们遵守必须证明的问题，我们得出结论，对于渐近更紧的边界 (f(n) = Big-theta(g(n)))，我们需要对于算法的最佳情况和Big-oh(g(n))，有f(n) = big-omega(g(n))> 在其最坏的情况下
• 但在插入排序的情况下，最佳情况时间复杂度为big-omega(n)，最坏情况时间复杂度为大哦(n^2)

Answer 1

我觉得你在这里有点困惑。让我为你澄清几点。

运行时间可能意味着两件事:程序的实际运行时间，或者像 theta 或 big-oh 这样的有界函数(所以称之为时间复杂度，以避免混淆)。以下我们将使用运行时间来表示程序的实际运行时间，并使用时间复杂度来表示Big-Oh/theta符号。

要拿起 Big-Oh，请阅读我的回答 here .

一旦你清楚了 Big-Oh，其他函数就很容易就位了。当我们说 T(n) 是 Omega(g(n)) 时，我们的意思是在某个点 k 的右边，曲线 c.g(n ) 从下面开始限制运行时间曲线。或者换句话说:

T(n)>=c.g(n) for all n>=k, and for some constant c independent of input size.

而 theta 表示法就像在说“我只是一个函数，但使用不同的常量你可以让我从上方和下方绑定(bind)运行时间曲线”

所以当我们说 T(n) 是 theta(g(n)) 时，我们的意思是

c1.g(n)==k

现在我们知道了这些函数的含义，让我们看看 CLRS 在哪里搞混了。

For example, the best case running time of insertion sort is big-omega(n), whereas worst case running time of Insertion sort is Big-oh(n^2). The running time of insertion sort therefore falls between big-omega(n) and Bigoh(n^2)

这里所说的运行时间 CLRS 表示实际运行时间 T(n)。它措辞不佳，你误解了这不是你的错。事实上我会继续说他们错了。没有什么比 落在两者之间，函数要么在集合 O(g(n)) 中，要么不在。所以这是一个错误。

Prove that the running time of an algorithm is Big-theta(g(n)) iff its worst case running time is Big-oh(g(n)) and its best case running time is big-omega(g(n))

这里的 CLRS 意思是运行时间函数 T(n)，他们要你算出时间复杂度。