找到以下代码的上限和下限 [英] Find an upper and lower bound of following code

问题描述

我需要找到以下代码的最接近的上下限。

I need to find a closest upper and lower bound of following code. I am beeginer in this so sorry for my mistake.

p（）的上限为O（log（n）），下限为O（1）

Upper bound for p() is O(log(n)), and lower bound is O(1)

notp（）的上限为O（log（n）），下限为O（1）

Upper bound for notp() is O(log(n)), and lower bound is O(1)

我认为下界是O（1），因为如果我有n = 4，那么我会进入循环，由于n％i == 0，所以我叫p（），它注意到这不是素数，所以O（1） 1）然后由于i = 2，其他notp将不会执行。这是最糟糕的情况。

I think that lower bound is O(1) because if I have n=4 then I get in the loop and since n%i==0 I call p() and it notice that is not a prime number so O(1) then since i=2 the other notp would not be executed. That is bast case scenario.

最糟糕的情况是我循环执行log（n），然后执行ap，上限为O（log（n） ），所以它是O（log（n）^ 2），但我不确定这是否很好，请告诉我我在哪里出错了？

Worst case scenario that I go through loop so that log(n), and execute a p and a upper bound is O(log(n)) so it is O(log(n)^2) but I am not so sure that this is good, please tell me where I made a mistake?

int i;
for (i = 2; i*i <= n; i++) {
  if (n % i == 0) {
    p();
    break;
  }
}
if(i*i > n)
  notp();

推荐答案

对于订单计算，通常在以下情况下将它们相乘

For order calculations, you would normally multiply them together when there is a loop.

for( i = 0; i < n ; i++ ){
     DoSomething(i);
}

这将是O（n），因为循环是单个情况。

That would be O(n), as the loop is a single case.

嵌套循环应为

for( i = 0; i < n ; i++ ){ 
    for( j =0; j < n; j++ ){
       DoSomething(i,j);
    }
}

按原样变为O（n ^ 2）

That becomes O( n^2 ) as they are additive.

如果您有非嵌套循环...

If you have non-nested loops...

for( i = 0; i < n ; i++ ){
     DoSomething(i);
}


for( j = 0; j < sqrt(n) ; j++ ){
     DoSomething(j);
}

则O（x）是最大项。那是因为对于非常大的n，x的较小值无关紧要。

Then the O( x ), is the largest term. That is because for very large n, the smaller values of x don't matter.

因此，您的情况下有一个循环，即O（sqrt（n） ）。这是因为它受i * i小于n的限制。

So you have a loop in your case, which is O( sqrt( n ) ). That is because it is limited by i *i being less than n.

然后将调用p（）或notp（）中的一个。

Then either one of p() or notp() will be called.

（我认为p（）和notp（）是错误的方法）。

(I think p() and notp() are the wrong way round).

重构代码...

int i;
for (i = 2; i*i <= n; i++) {
  if (n % i == 0) {
    /* p(); */
    break;
  }
}
if(i*i > n)
  notp();
else
  p();

所以我们有O（sqrt（n））时间加上p / notp函数之一是O（log（n））

So we have the O( sqrt(n) ) time plus either of the p / notp functions which are O( log(n) )

O（sqrt（n）+ log（n））

O( sqrt(n ) + log(n) )

当sqrt的增长速度大于n时，它将压倒日志（n） Wikipedia Big O ，

As the sqrt grows faster than n, it overpowers the log(n) wikipedia Big O, leaving it as the final value.

O（sqrt（n））

O( sqrt(n) )

这篇关于找到以下代码的上限和下限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！