我有家庭作业问题：

     找到一个THETA表示法的次数语句x = X + 1被执行。 （10分）。   

  I = N
而（ⅰ＆GT; = 1）
{
   对于j = 1到n
   {
      X = X + 1个
   }
   I = I / 2
}
 

这是我做了什么：

好吧首先让我们更容易。我们将拳头找到成长的顺序：

 ，而（I＆GT; = 1）
{
   X = X + 1个
   I = I / 2
}
 

这是有秩序的增长 O（日志（N））实际登录基地2

其他内部的循环将执行n次，因此算法应该是顺序：

O（日志（N）* N）

在那里我感到困惑的部分是，我应该找到THETA符号并不大-O。我知道，THETA符号是假设绑定在上和下限值的功能。将正确的答案是的Theta（日志（N）* N）？

我发现在这个链接的答案，但我不知道你如何得到这个问题的答案。为什么他们声称，答案是西塔（N）？

解决方案

您现在应该证明它也是欧米茄（nlogn）。

我不想表现究竟如何，既然是家庭作业 - 但它与你展示 O（nlogn）同样的原则。你需要表现出[unformally explnation：]该功能的渐近行为下，越来越多的至少快作为 nlogn 。 [为大啊，你显示它正在以最有率 nlogn 。

请记住，如果一个函数同时 O（nlogn）和欧米茄（nlogn），这是西塔（ nlogn），反之亦然]

PS 您的预感是真实的，它很容易证明它不是欧米茄（N），因此它不是的Theta（N）

P.S。 2 ：我觉得混淆不同的节目对方的回答作者：

  I = N
而（ⅰ＆GT; = 1）
{
   对于j = 1到i //注：我代替N-这里！
   {
      X = X + 1个
   }
   I = I / 2
}
 

以上程序确实的Theta（N），但它是从您提供的不同。

I have the homework question:

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

i = n
while (i >= 1)
{
   for j = 1 to n
   {
      x = x + 1
   }
   i = i/2
}

This is what I have done:

Ok first let’s make it easier. We will fist find the order of growth of:

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

that has order of growth O(log(n)) actually log base 2

the other inner for loop will execute n times therefore the algorithm should be of order:

O(log(n)*n)

The part where I get confused is that I am supposed to find theta notation NOT big-O. I know that theta notation is suppose to bound the function on the upper and lower limit. Will the correct answer be Theta(log(n)*n)?

I have found the answer in this link but I don't know how you get to that answer. Why they claim that the answer is Theta(n) ?

解决方案

You should now prove it is also Omega(nlogn).

I won't show exactly how, since it is homework - but it is with the same principles you show O(nlogn). You need to show [unformally explnation:] that the asymptotic behavior of the function, is growing at least as fast as nlogn. [for big O you show it is growing at most at the rate of nlogn].

Remember that if a function is both O(nlogn) and Omega(nlogn), it is Theta(nlogn) [and vise versa]

p.s. Your hunch is true, it is easy to show it is not Omega(n), and thus it is not Theta(n)

p.s. 2: I think the author of the other answer confused with a different program:

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

The above program is indeed Theta(n), but it is different from the one you have provided.