求以下代码的上限和下限

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

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();

对于阶数计算，当存在循环时，通常会将它们相乘。

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

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

由于 sqrt 的增长速度快于 n，因此它压倒了 log(n)维基百科大O https://en.wikipedia.org/wiki/Big_O_notation，将其保留为最终值。

O( 开方(n) )