0

I have a question about calculating big o notation for the following code:

j = 1;
while ( j <= n ) do  
  for i = 1 to j do 
    O(1); 
  endfor; 
  j=j*2; 
endwhile

So far, I have that the loop is calculated Σi=1,..,n2i. It looks like a geometric sequence, but I'm not sure what the big O value would be. Can anyone help out?

4

5 回答 5

3

这里不是高斯的，因为它是你已经提到的几何序列。

一旦 j 达到 n，外部 while 循环将停止。

为此所需的迭代次数可以通过认为这是这里要解决log₂(n)的问题来计算。2^x = n（我们必须不断乘以 2 直到达到 n 多少次）

有趣的是，这会导致：

log₂(n)     log₂(n)
∑ 2^i    =  2       - 1 = n - 1
0

Sum from 1 to log2(n) taken over 2^i这正是2^(log2n) - 1= n - 1（重申上面给出的公式，以防您的字体集不支持所需的 unicode 字符）

使用这里的事实

k            k+1
∑ 2^i    =  2   - 1
0

所以算法应该是O(n)。

或者，您可以使用几何序列的通用公式计算总和：

Sn = a0 * (1-q^n) / (1-q)

这应该会导致与实际上相同的结果：

        log₂n
   1 - 2           1 - n
  -----------  =  ------ = n - 1
    1 - 2           -1
于 2013-03-29T01:33:50.917 回答
0

Geometric sequence is correct. Take a quick example. If n is 8, then the number of iterations of the inner loop is 1, then 2, then 4, then 8. If n were 7 you'd have 1, 2, 4, and no 8. So the number of O(1) operations is going to vary between n and 2n - 1 as you increase n. On either side of that range, the order is O(n).

于 2013-03-29T01:28:59.033 回答
0

好的！，让我们假设一些值来帮助更好地理解：

让 n 等于 4

So now:
j=1 ( <4 ) => loop runs 1 time = O(1)
j=1*2 = 2 ( <4 ) => loop runs 2 times = 2*O(1)
j=2*2 = 4 ( =4 ) => loop runs 4 times = 4*O(1)

如果 n 属于 2^x 类型，那么可以肯定地说，一系列循环运行如下所示：

O(1) + 2*O(1) + 4*O(1) + 8*O(1) + 16*O(1) + ..... + n*O(1)。= 1*(2^(x+1) - 1)*O(1)/(2-1) = (2n-1)*O(1) = O(n) 其中 n = 2^x，并且外循环运行 x+1 次。

现在如果 n 不是 2^x 类型。假设 n = 6。

So now:
j=1 ( <6 ) => loop runs 1 time = O(1)
j=1*2 = 2 ( <6 ) => loop runs 2 times = 2*O(1)
j=2*2 = 4 ( <6 ) => loop runs 4 times = 4*O(1)
j=2*4 = 8 ( >6 ) => loop exits.

很明显，外部循环只会运行 2^( floor value( log base 2(n) )) + 1 次。这个值就是有效的 n。

所以让我们把它代入公式： (2n-1) O(1) => (2 (2^(floorValue(logBase2(n))) - 1)*O(1) 约等于 O(n)

于 2013-03-29T01:37:22.810 回答
0

在这里有点聪明：你所要求的实际上是Theta. 您的代码是Theta(n)- 但也是O(n)，O(n * log_2(n))甚至O(n!)因为 Big-O 只是一个上限。Theta是精确的。

于 2013-03-29T01:40:36.267 回答
0

它应该是 0(n^2)。这与插入排序相同

void insertionsort(void){

 for(int x=1;x<n;x++){
   int temp= array[x];
   for(int y=x-1;  y>=0 && array[y]>temp ;y--){
    array[y+1]=array[y];
   }array[y+1]=temp;
 }
}

O(n) 从 1 到 n，但是对于其中的每一个，它从 y=x-1 到 0。在最坏的情况下，它总是从 y=x-1 到 0。所以这个增长了每次 x 增长。

你的情况就是这样。

于 2013-06-16T11:02:14.527 回答