asymptotic-complexity - 计算函数的大θ

Question

我被要求计算家庭作业的大 theta，但是这方面的讲座材料有点稀疏。

鉴于循环

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。

我对么？

Answer 1

您的计算似乎正确，但您需要继续执行更多步骤。

Big theta 忽略所有小于最大项和所有常数因子的内容（该等式可能有助于理解这一点）。

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))