big-o - 谁能解释一下 Big O、Big Omega 和 Big Theta？

Question

这个问题已经有答案了:

已关闭 10 年前。

Possible Duplicate:
Big Theta Notation - what exactly does big Theta represent?

我想，理论上我理解它，但我很难理解这三者的应用。

在学校里，我们总是用 Big O 来表示算法的复杂度。例如，冒泡排序的时间复杂度为 O(n^2)。

现在，在阅读了更多理论后，我发现 Big Oh 并不是唯一的衡量标准，至少还有其他两个有趣的衡量标准。

但这是我的问题:

Big O 是上限，Big Omega 是下限，Big Theta 是两者的混合。但这在概念上意味着什么呢？我理解图表上的含义；我见过一百万个这样的例子。但这对于算法复杂度意味着什么？ “上限”或“下限”如何与之混合？

我想我只是没有得到它的应用程序。我知道，如果乘以某个常数 c，如果某个值 n_0 f(x) 大于 g(x)，则 f(x) 被视为 O(g(x))。但这实际上意味着什么呢？为什么我们要将 f(x) 乘以某个值 c？天哪，我认为使用 Big O 表示法倍数并不重要。

Answer 1

大 O 表示法及其相关的大 Theta、大 Omega、小 o 和小 omega 是表达函数在极限点(例如，当接近无穷大时，但也当接近 0 时等)，无需对函数进行太多说明。它们通常用于描述算法的运行空间和时间，但也可以在有关渐近行为的其他数学领域中看到。

半直观的定义如下:

如果“从某个点开始”，g(x) 低于 c*f(x)，则函数 g(x) 被称为 O(f(x))，其中 c 是某个常数。

其他定义类似，Theta 要求 g(x) 位于 f(x) 的两个常数倍之间，Omega 要求 g(x)>c*f(x)，小版本要求这是真的对于所有这些常数。

但是为什么说一个算法的运行时间为 O(n^2) 很有趣？

这很有趣，主要是因为，在理论计算机科学中，我们最感兴趣的是算法对于大输入的行为方式。这是事实，因为在小输入上，算法运行时间可能会因实现、编译、硬件和其他在理论上分析算法时并不真正有趣的因素而有很大差异。

但是，增长率通常取决于算法的性质，为了改进算法，您需要对要解决的问题有更深入的了解。例如，在排序算法中，您可以获得一个简单的算法(冒泡排序)来以 O(n^2) 运行，但要将其改进为 O(n log n)，您需要一个真正的新想法，例如归并排序或堆排序中引入的排序。

另一方面，如果您有一个算法在 5n 秒内运行，而另一个算法在 1000n 秒内运行(例如，长哈欠和 n=3 时的启动中断之间的差异)，则当当你得到 n=1000000000000 时，规模上的差异似乎不那么重要了。但是，如果你有一个需要 O(log n) 的算法，那么你必须等待 log(1000000000000)=12 秒，也许乘以某个常数，而不是几乎 317,098 年，无论这个常数有多大是，是完全不同的尺度。

我希望这能让事情变得更清楚一些。祝你学业有成!