1

我有作业问题：

令 T(n) 表示语句 x = x + 1 在算法中执行的次数

example (n)
{
    if (n == 1)
    {
       return
    }
    for i = 1 to n
    {
       x = x + 1
    }
    example (n/2)
}

求 x = x + 1 执行次数的 theta 表示法。（10分）。

这是我所做的：

我们完成了以下工作量： - 基本情况检查的恒定工作量 - O(n) 工作来计算数字 - 递归调用一半大小的东西所需的工作

我们可以将其表示为递归关系： T(1) = 1 T(n) = n + T(n/2)

让我们看看这是什么样子。我们可以通过注意到

T(n)=n+T(n/2)
=n+(n/2+T(n/4))
=n+n/2+T(n/4)
=n+n/2+(n/4+T(n/8))
=n+n/2+n/4+T(n/8)

我们可以在这里开始看到一种模式。如果我们将 T(n/2) 位扩展 k 次，我们得到： T(n)=n+n/2+n/4+⋯+n/2^k +T(n/2^k )

最终，当这种情况发生时停止n/2^k =1 ，我们有： T(n)=n+n/2+n/4+n/8+⋯+1

这意味着什么？有趣的是，这个总和等于 2n+1，因为总和n+ n/2 + n/4 + n/8 +…. = 2n. 因此第一个函数是O(n)

由于@templatetypedef回答了这个问题，我得到了答案

知道我对 theta 表示法感到困惑。答案会一样吗？我知道 theta 表示法应该将函数与下限和上限绑定。这意味着我需要发挥作用？

4

1 回答 1

1

是的，答案是一样的！

您可以轻松地使用相同的工具来证明T(n) = Omega(n)。

证明T(n)既是O(n)[上渐近界]又是Omega(n)[渐近下界]后，你知道它也是Theta(n)[紧渐近界]

在您的示例中，很容易证明这一点T(n) >= n- 因为这是家庭作业，所以由您来理解为什么。

于 2012-03-04T17:12:36.157 回答