我试图弄清楚我的算法的效率,但我有点困惑。 只需要一些专家的想法来证明我的答案是正确的,或者将我引用到某个地方,这个地方正在解释关于不在渐近主题中的元素。 (资源很多,关于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)
我不知道如何衡量它!
最佳答案
在这种情况下,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)。
关于algorithm - 什么时候大 O 或 Omega 或 theta 可以成为集合的元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18354504/