2

我有作业问题：

  1. 求语句 x = x + 1 执行次数的 theta 表示法。（10分）。
i = n
while (i >= 1)
{
   for j = 1 to n
   {
      x = x + 1
   }
   i = i/2
}

这就是我所做的：

好的，首先让我们让它更容易。我们将首先找到增长的顺序：

while (i >= 1)
{
   x = x + 1
   i = i/2
}

具有增长顺序的O(log(n)) 实际上对数基数 2

另一个内部 for 循环将执行 n 次，因此算法应该是有序的：

O(log(n)*n)

我感到困惑的部分是我应该找到 theta 符号而不是 big-O。我知道 theta 表示法假设将函数限制在上限和下限。正确答案会是Theta(log(n)*n)？

我在这个链接中找到了答案，但我不知道你是如何得到这个答案的。为什么他们声称答案是 Theta(n) ？

4

3 回答 3

2

你现在应该证明它也是Omega(nlogn).

我不会确切地展示如何，因为这是家庭作业 - 但它与您展示的原理相同O(nlogn)。您需要证明 [非正式解释：] 该函数的渐近行为至少与nlogn. [对于大 O，您表明它最多以 ] 的速度增长nlogn。

请记住，如果一个函数同时为O(nlogn)和Omega(nlogn)，则为 Theta(nlogn) [反之亦然]

ps你的预感是真的，很容易证明它不是Omega(n)，因此它不是Theta(n)

ps 2：我认为另一个答案的作者与不同的程序混淆了：

i = n
while (i >= 1)
{
   for j = 1 to i //NOTE: i instead of N here!
   {
      x = x + 1
   }
   i = i/2
}

上面的程序确实是Theta(n)，但是和你提供的不一样。

于 2012-03-04T16:55:57.743 回答
2

以更正式的方式重新表述您的代码片段，以便可以使用 Sigma 表示法轻松表示：

for (i = n; i >= 1; i = i/2 ) {
    for j = 1; j <= n; j ++) {
        x = x + 1; // instruction of cost 'c'
    }
}

我们获得：

在此处输入图像描述

于 2014-04-23T22:23:25.533 回答
0

正如@amit提到的，我已经有了函数的上限，那就是 Big-O，它实际上是 O(n*lgn)。如果我绘制该函数的表格，我会得到类似的东西：

n   n*lng
1   0
2   2
3   4.754887502
4   8
5   11.60964047
6   15.509775
7   19.65148445
8   24
9   28.52932501
10  33.21928095

因为那是大 O，所以这意味着真正的函数将受这些值的限制。换句话说，实际值应小于表中的值。例如，当我们通过查看表格n=9知道答案应该小于或等于28.52932501

所以现在我们找不到欧米茄，这是另一个界限。我认为下界函数应该是 Omega(n) 然后我们会得到表格

n   Omega(n)
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
.......

所以这将是另一个界限。如果我们再次以点为例，n = 9那么它会给我们 9。这意味着我们的真实函数应该给我们一个大于或等于 9 的值。基于我们的 big-O 函数，我们也知道它应该小于或等于28.52932501

于 2012-03-04T17:28:29.313 回答