Suh*_*pta 39 algorithm big-o big-theta
在试图理解Theta和O符号之间的区别时,我遇到了以下声明:
The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
但我不明白这一点.这本书以数学的方式解释了它,但它太复杂了,当我真的不理解时,阅读起来真的很无聊.
任何人都可以使用简单但功能强大的示例来解释两者之间的区别.
ami*_*mit 45
Big O只给出上渐近界,而大The也给出了下界.
一切,这是Theta(f(n))也O(f(n)),而不是周围的其他方法.
T(n)据说是Theta(f(n)),如果它是O(f(n)) 和 Omega(f(n))
出于这个原因,big-Theta比大O符号更具信息性,所以如果我们可以说一些大-Theta,它通常是首选.然而,证明某些东西是大的Theta比证明它是大O更难.
对于例如,归并排序是既O(n*log(n))和Theta(n*log(n)),但它也为O(n 2),由于n 2是渐近比"大".但是,它不是Theta(n 2),因为算法不是Omega(n 2).
Omega(n)是渐近下界.如果T(n)是Omega(f(n)),则意味着从某个n0,有一个恒定的C1,使得T(n) >= C1 * f(n).而大O说有C2这样的常数T(n) <= C2 * f(n)).
所有三个(Omega,O,Theta)只给出渐近信息("大输入"):
注意,这个符号是不相关的算法最好,最差,平均情况分析.这些中的每一个都可以应用于每个分析.
我将引用Knuth的TAOCP第1卷 - 第110页(我有印度版).我建议阅读第107-110页(1.2.11节渐近表示)
人们经常通过假设它给出一个确切的增长顺序来混淆O符号; 他们使用它就好像它指定了下限和上限.例如,算法可能被称为低效,因为其运行时间为O(n ^ 2).但O(n ^ 2)的运行时间并不一定意味着运行时间也不是O(n)
在页107,
1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = O(n ^ 4)和
1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = O(n ^ 3)和
1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 =(1/3)n ^ 3 + O(n ^ 2)
Big-Oh用于近似值.它允许你用等号=符号替换〜.在上面的例子中,对于非常大的n,我们可以确定数量将保持低于n ^ 4和n ^ 3和(1/3)n ^ 3 + n ^ 2 [并且不仅仅是n ^ 2]
Big Omega用于下限 - 具有Omega(n ^ 2)的算法将不如具有大N的O(N logN)的算法有效.但是,我们不知道N的值是什么(在这个意义上我们知道大约)
Big Theta用于确定增长顺序,包括下限和上限.
我将用一个例子来说明其中的区别。
\n\n令函数 f(n) 定义为
\n\nif n is odd f(n) = n^3\nif n is even f(n) = n^2\n来自 CLRS
\n\n\n\n\n如果存在正数常量 c1 和 c2，则函数 f(n) 属于集合 \xce\x98(g(n))，使得它可以“夹在”c1g(n)\n 和 c2g(n) 之间，对于足够大的 n。
\n
和
\n\n\n\n\nO(g(n)) = {f(n)：存在正常数 c 和 n0，使得 0 \xe2\x89\xa4\nf(n) \xe2\x89\xa4 cg(n) 对于所有 n \xe2 \x89\xa5 n0}。
\n
和
\n\n\n\n\n\xce\xa9(g(n)) = {f(n)：存在正常数 c 和 n0，使得 0 \xe2\x89\xa4\n cg(n) \xe2\x89\xa4 f(n) 对于所有 n \xe2\x89\xa5 n0}。
\n
f(n) 的上限为 n^3。所以我们的函数 f(n) 显然是 O(n^3)。
\n\n但它是\xce\x98(n^3)吗？
\n\n为了使 f(n) 位于 \xce\x98(n^3) 中，它必须夹在两个函数之间，一个函数形成下界，另一个函数形成上限，这两个函数都以 n^3 增长。虽然上限是显而易见的，但下限不可能是 n^3。下界实际上是 n^2；f(n) 是 \xce\xa9(n^2)
\n\n来自 CLRS
\n\n\n\n\n对于任意两个函数 f(n) 和 g(n)，我们有 f(n) = \xce\x98(g(n)) 当且仅当 f(n) = O(g(n)) 且f(n) = \xce\xa9(g(n))。
\n
因此 f(n) 不在 \xce\x98(n^3) 中，而在 O(n^3) 和 \xce\xa9(n^2) 中
\n这是我的尝试:
函数,f(n)是O(n),当且仅当存在一个常数,c,使得f(n) <= c*g(n).
使用这个定义,我们可以说功能f(2^(n+1))是O(2^n)？
换句话说,一个常数是否'c'存在2^(n+1) <= c*(2^n)？注意第二个函数(2^n)是上述问题中Big O之后的函数.起初这让我很困惑.
那么,然后使用你的基本代数技巧来简化这个等式. 2^(n+1)分解为2 * 2^n.这样做,我们留下:
2 * 2^n <= c(2^n)
现在很简单,这个等式适用于任何值的c地方c >= 2.所以,是的,我们可以说,f(2^(n+1))是O(2^n).
Big Omega以相同的方式工作,除了它评估f(n) > = c*g(n)一些常量'c'.
因此,以相同的方式简化上述功能,我们留下(注意> = now):
2 * 2^n >= c(2^n)
因此,该等式适用于该范围0 <= c <= 2.所以,我们可以说那f(2^(n+1))是大欧米茄的(2^n).
现在,由于那些人持有,我们可以说功能是Big Theta(2^n).如果其中一个不能用于常数'c',那么它不是大Theta.
上面的例子来自Skiena的算法设计手册,这是一本很棒的书.
希望有所帮助.这真的是一个简化的难题.不要因为什么而挂断'c',只需将其分解为更简单的术语并使用你的基本代数技巧.
如果运行时间以big-O表示法表示，则您将知道运行时间不会比给定的表达式慢。它表示最坏的情况。
但是使用Theta表示法，您还知道它不会更快。也就是说，不存在算法重新调谐更快的最佳情况。
这样可以更准确地限制预期的运行时间。但是，对于大多数目的而言，忽略下界更容易（执行速度更快的可能性），而您通常只关心最坏的情况。