计算函数的大θ值

我被要求计算一个家庭作业的大θ，但这个领域的讲义材料有点稀疏。计算函数的大θ值

鉴于我已经制定了一个执行图表环路

for (x = 1; x <= n; x *= 2){ 
    for(y = 1; y <= n; y += 2) 
    t++;

为

x  y 
1  1, 3, 5, 7 ... n-2, n 
2  1, 3, 5, 7 ... n-2, n 
4  1, 3, 5, 7 ... n-2, n 
8  1, 3, 5, 7 ... n-2, n 
log n (n+1)/2

它那的投掷我从内环路增量器。它执行（n + 1）/ 2次，所以大的theta必须是（n log n + log n）/ 2。

我正确吗？

来源

2013-01-24 Jason

您的计算显示正确，但您需要继续执行几个步骤。

Big theta忽略了小于最大项的所有项，并且所有常数因子（the equation可能有助于理解此项）。

Theta((n log n + log n)/2) 
= Theta(1/2 n log n + 1/2 log n) 
= Theta(1/2 n log n) 
= Theta(n log n)

为什么它忽略常数因子是看公式明显的（你可以操纵ķ适当）。

为什么它忽略一切相比，最大的项小：

Assume g(x) <= f(x) (from any x onward, since the Theta equation only needs to hold from any n onward) 
f(x) <= f(x) + g(x) <= 2.f(x) 
Thus Theta(f(x) + g(x)) = Theta(2.f(x)) = Theta(f(x))

来源

2013-01-24 16:09:35 Dukeling

计算函数的大θ值

回答

相关问题