algorithm - 什么时候大 O 或 Omega 或 theta 可以成为集合的元素？

Question

我试图弄清楚我的算法的效率，但我有点困惑。只需要一些专家的想法来证明我的答案是正确的，或者将我引用到某个地方，这个地方正在解释关于不在渐近主题中的元素。 (资源很多，关于set的元素我没找到)

当我们说 O(n^2) 是两个循环时，这样说是对的吗:

n^2 is an element of O(n^3)

据我了解，大 O 是最坏的情况，而 omega 是最有效的情况。如果我们把它们放在图表上，所有 n^2 的情况都是 O(n^3) 的一部分，那么第一个不对吗？

n^3 is an element of omega(n^2)

关于第二个也是不正确的。因为 omega(n^2) 的一些最佳情况并不在 n^3 的所有情况下!

终于是

2^(n+1) element of theta(2^n)

我不知道如何衡量它!

Answer 1

在这种情况下，Big O、omega、theta 都是复杂性。具有这些复杂性的函数构成了您正在考虑的集合。

的确，复杂度为 O(n*n) 的函数集是复杂度为 O(n*n*n) 的函数集的子集。简单地说，这是因为 O(n*n*n) 意味着复杂度小于 c*n*n*n，因为 n 趋于无穷大，对于某个常数 c。如果一个函数的实际复杂度为 3*n*n + 7*n，那么对于 任何 c，它随着 n 趋于无穷大的复杂度显然小于 c*n*n*n。

因此，O(n*n*n) 不仅仅是“三个循环”，而是“三个循环或更少”。

Ω 是相反的。它是复杂性的下界，当 n 趋于无穷大时，c*n*n 是 n*n*n 的平凡下界。

复杂度为 Θ(n*n) 的函数集是复杂度为 O(n*n) 和 Ω(n*n) 的函数集的交集。例如。 3*n 没有复杂度 Θ(n*n) 因为它没有复杂度 Ω(n*n)，而 7*n*n*n 没有复杂度 Θ(n*n) 因为它没有复杂度为 O(n*n)。