任何人都可以解释Big O与Big Omega对比Big Theta吗？

Question

可能重复:
大Theta表示法 - 大Theta代表什么？

我认为,理论上我理解它,但我抓到的麻烦就是三者的应用.

在学校,我们总是使用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),你需要一个真正的新想法,例如Merge Sort或Heap Sort中引入的.

另一方面,如果你有一个算法在5n秒内运行,而另一个算法在1000n秒内运行(例如,长时间打哈欠和n = 3的启动中断之间的差异),当你到达时n = 1000000000000,规模差异似乎不太重要.但是,如果你的算法需要O(log n),你必须等待log(1000000000000)= 12秒,也许等于一些常数,而不是几乎317,098年,无论常数有多大是,是一个完全不同的规模.

我希望这会让事情变得更加清晰.祝你学习顺利!