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

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

对于顺序计算，通常在有循环时将它们相乘。

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(平方根(n) + 日志(n))

随着 sqrt 的增长速度快于 n，它压倒了 log(n) wikipedia Big O , 将其保留为最终值。

O(平方根(n))