为什么这个关于快速排序的最坏情况运行时的引用使用 Ω 表示法？
Why does this quote about quicksort's worst-case runtime use Ω notation?
我刚刚阅读了算法导论中的这段摘录：
Quick sort takes Ω(n2) time when partition is unbalanced
如何解释这个 Ω(n2)？为什么是Ω？我们可以在这里也使用大 O 符号吗？
它实际上是 Theta(n^2) 所以它也是 Omega(n^2)，但是声明 "Quick sort is O(n^2) when partition is unbalanced" 不是很有用 - 因为 O(nlogn) 是 O(n^2)。换句话说，所有 O(nlogn) 的东西（比如快速排序的平均情况）也是 O(n^2).
big O 给出了上限，但在这里，我们想显示下限——在最坏的情况下，我们不能比 n^2 好，而不是我们不能比它差，因此我们没有使用 O(n^2)。
因此，即使是快速排序的最佳情况也是 O(n^2)（但不是 Omega(n^2)）——因此说快速排序是 O(n^2) 并不是很有用。
您可能习惯使用的大 O 表示法用于描述上限。如果我们说一个算法的运行时间为 O(n2)，我们的意思是算法的运行时间最多一些二次函数。您可以将 O 表示法视为 "less than or equal to" 符号。
Big-Ω 表示法类似于 big-O 表示法，但用于描述 下限 。如果我们说一个算法有运行时间 Ω(n2)，我们的意思是算法的运行时间是 至少 一些二次函数。您可以将 Ω 表示法视为 "greater than or equal to" 符号。
当我们谈论算法的最坏情况运行时时，大 O 表示法通常是不合适的。假设我声称算法的最坏情况运行时间是 O(n2)。我的意思是，该算法的运行时间最多 某个二次函数。也就是说，最坏情况下的运行时间可能比这低很多。打个比方，假设我声称自己 最多 10,000 岁。这真的没什么好说的-我肯定最多10,000岁，但实际上我比那年轻得多。
另一方面，假设我声称算法的最坏情况运行时间是 Ω(n2)。现在我说算法的最坏情况运行时间是 至少 一些二次函数。这实际上说明了一些事情 - 回到我们之前的类比，如果我告诉你一些岩石至少有 10 亿年的历史，那实际上告诉你一些事情 - 它非常古老！它类似于最坏情况下的运行时间是 Ω(n2) - 我告诉你它是 至少 二次方，排除任何更小的.
希望对您有所帮助！
我刚刚阅读了算法导论中的这段摘录：
Quick sort takes Ω(n2) time when partition is unbalanced
如何解释这个 Ω(n2)？为什么是Ω？我们可以在这里也使用大 O 符号吗？
它实际上是 Theta(n^2) 所以它也是 Omega(n^2)，但是声明 "Quick sort is O(n^2) when partition is unbalanced" 不是很有用 - 因为 O(nlogn) 是 O(n^2)。换句话说，所有 O(nlogn) 的东西（比如快速排序的平均情况）也是 O(n^2).
big O 给出了上限，但在这里，我们想显示下限——在最坏的情况下，我们不能比 n^2 好，而不是我们不能比它差，因此我们没有使用 O(n^2)。
因此，即使是快速排序的最佳情况也是 O(n^2)（但不是 Omega(n^2)）——因此说快速排序是 O(n^2) 并不是很有用。
您可能习惯使用的大 O 表示法用于描述上限。如果我们说一个算法的运行时间为 O(n2)，我们的意思是算法的运行时间最多一些二次函数。您可以将 O 表示法视为 "less than or equal to" 符号。
Big-Ω 表示法类似于 big-O 表示法，但用于描述 下限 。如果我们说一个算法有运行时间 Ω(n2)，我们的意思是算法的运行时间是 至少 一些二次函数。您可以将 Ω 表示法视为 "greater than or equal to" 符号。
当我们谈论算法的最坏情况运行时时，大 O 表示法通常是不合适的。假设我声称算法的最坏情况运行时间是 O(n2)。我的意思是，该算法的运行时间最多 某个二次函数。也就是说，最坏情况下的运行时间可能比这低很多。打个比方，假设我声称自己 最多 10,000 岁。这真的没什么好说的-我肯定最多10,000岁，但实际上我比那年轻得多。
另一方面，假设我声称算法的最坏情况运行时间是 Ω(n2)。现在我说算法的最坏情况运行时间是 至少 一些二次函数。这实际上说明了一些事情 - 回到我们之前的类比，如果我告诉你一些岩石至少有 10 亿年的历史，那实际上告诉你一些事情 - 它非常古老！它类似于最坏情况下的运行时间是 Ω(n2) - 我告诉你它是 至少 二次方，排除任何更小的.
希望对您有所帮助！