1

宿題でビッグ シータを計算するように頼まれましたが、この分野に関する講義資料は少し少なめでした。

与えられたループ

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 回実行されるため、ビッグ シータは (n log n + log n)/2 である必要があります。

私は正しいですか？

4

1 に答える 1

1

計算は正しいように見えますが、さらにいくつかの手順を続行する必要があります。

ビッグシータは、最大項よりも小さいすべてとすべての定数係数を無視します（方程式はこれを理解するのに役立つ場合があります）。

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)

定数因子を無視する理由は、方程式を見れば明らかです（kを適切に操作できます）。

最大の用語よりも小さいものをすべて無視する理由：

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-24T16:09:35.970 に答える