有时我看到Θ(n)带有奇怪的Θ符号,中间有一些东西,有时只有O(n).这只是打字的懒惰,因为没有人知道如何输入这个符号,或者它是否意味着不同的东西？
我真的很困惑大O,大欧米茄和大Theta符号之间的差异.
我知道大O是上界,大欧米茄是下界,但大Ө(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.
但我不明白这一点.这本书以数学的方式解释了它,但它太复杂了,当我真的不理解时,阅读起来真的很无聊.
任何人都可以使用简单但功能强大的示例来解释两者之间的区别.
我正在阅读"算法简介"第3版(Cormen和Rivest)和第69页"蛮力解决方案",他们声明n选择2 = Theta(n ^ 2).我认为它会在Theta(n!)中代替.为什么n选择2紧密绑定到n平方？谢谢!
我试图弄清楚是否f(n)=n^(logb(n))存在Theta(n^k)并因此增长多项式或Theta(k^n)因此成指数增长.
首先,我尝试简化功能:
f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n))因为1/log(b)我们得到的是不变的f(n)=n^log(n).
但是现在我被卡住了.我的猜测是f(n)指数增长呈指数增长Theta(n^log(n))甚至超指数增长,因为指数log(n)也在增长.
最近,我遇到了一个代码片段:
int i = 1;
while (N > 1)
{
N = N / i;
i = i + 1;
}
在观察时,很明显i线性地增加,并且在循环的每个运行时间中i分开N,因此我们可以说它N作为因子的反函数的函数而减小.
我们如何用theta表示法表示这一点 ,因为没有为每个自然数定义反因子N？我们是否必须使用此函数的近似上限和下限？
我想计算这个嵌套for循环的θ复杂度:
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// statement
我会说它是n ^ 3,但我不认为这是正确的,因为每个for循环不会从1变为n.我做了一些测试:
n = 5 - > 10
10 - > 120
30 - > 4060
50 - > 19600
所以它必须在n ^ 2和n ^ 3之间.我尝试了总和公式等,但我的结果太高了.虽然n ^ 2 log(n),但那也错了......
是2 ^ n =Θ(4 ^ n)？
我很确定2 ^ n不在Ω(4 ^ n)中,因此不在Θ(4 ^ n)中,但我的大学导师说它是.这让我很困惑,我找不到每个Google的明确答案.
假设我们可以证明一个用大小输入调用的算法n及时运行O(f(n)).
我想证明这个运行时限很紧.两个问题:
f(n)？我有公式a(n)= n*a(n-1)+1; a(0)= 0
如果没有主定理,我如何从中得到Omega,Theta或O表示法,或者有没有人有一个很好的网站来理解解释