計算函數的大θ值

我被要求計算一個家庭作業的大θ，但這個領域的講義材料有點稀疏。計算函數的大θ值

鑑於我已經制定了一個執行圖表環路

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

計算函數的大θ值

回答

相關問題