algorithm - 找到以下递归方法的 theta 符号

Question

我有作业题:

Let T(n) denote the number of times the statement x = x + 1 is executed in the algorithm

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

Find the theta notation for the number of times x = x + 1 is executed. (10 points).

这是我所做的:

我们完成了以下工作量: - 基本情况检查的恒定工作量 - 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)

感谢 this question，我得到了答案由 @templatetypedef 回答

---

知道我对 theta 符号感到困惑。答案会一样吗？我知道 theta 符号应该用下限和上限来约束函数。那意味着我需要功能？

Answer 1

是的，答案是一样的!

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

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

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