找到以下代码的上限和下限

Question

我需要找到以下代码的最接近上限和下限。我是初学者，很抱歉我的错误。

p() 的上限为 O(log(n))，下限为 O(1)

notp() 的上限是 O(log(n))，下限是 O(1)

我认为下限是 O(1) 因为如果我有 n=4 然后我进入循环并且因为 n%i==0 我调用 p() 并且它注意到它不是质数所以 O(1) 然后因为 i=2 另一个 notp 不会被执行。那是最好的情况。

我经历循环的最坏情况是 log(n)，并执行 p 并且上限是 O(log(n)) 所以它是 O(log(n)^2) 但我是不太确定这是否好，请告诉我哪里出错了？

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

Answer 1

由于循环的终止条件为i*i <= n，因此循环最可能的迭代次数为sqrt(n)。由于在n % i == 0的条件下有一个break，这部分的最坏情况是sqrt(n) + log(n)也就是O(sqrt(n))。此外，无论第二个条件是否为真，由于 nopt() 的最坏情况是 O(log(n))，因此算法的最坏情况总共是 O(sqrt(n)).

Answer 2

对于阶数计算，一般在有循环的情况下将它们相乘。

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

那将是 O(n)，因为循环是单一案例。

嵌套循环是

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

这变成了 O( n^2 ) 因为它们是相加的。

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

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


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

那么O(x)，就是最大项。这是因为对于非常大的 n，x 的较小值无关紧要。

所以你的情况有一个循环，它是 O( sqrt( n ) )。那是因为它受限于 i *i 小于 n.

然后将调用 p() 或 notp() 之一。

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

重构您的代码....

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) ) 时间加上 O( log(n) ) 的 p / notp 函数之一

O(平方根(n) + 日志(n))

由于 sqrt 的增长速度快于 n，它压倒了 log(n) wikipedia Big O，使其成为最终值。

O(平方根(n))

找到以下代码的上限和下限

Find an upper and lower bound of following code

algorithm

complexity-theory