这个素数测试算法的时间复杂度？

我有下面的代码，它确定一个数是否是素数：这个素数测试算法的时间复杂度？

public static boolean isPrime(int n){ 
    boolean answer = (n>1)? true: false; 

    for(int i = 2; i*i <= n; ++i) 
    { 
     System.out.printf("%d\n", i); 
     if(n%i == 0) 
     { 
      answer = false; 
      break; 
     } 
    } 
    return answer;  
}

我怎么能确定这个功能的大O的时间复杂度？这种情况下输入的大小是多少？

来源

2013-10-20 user2900638

想想这个函数的最坏情况运行时间，如果这个数字确实是质数，就会发生这种情况。在这种情况下，内部循环将尽可能多地执行。由于循环的每次迭代都会执行一定量的工作，因此完成的总工作量将为O（循环迭代次数）。

那么会有多少循环迭代？让我们来看看循环边界：

for(int i = 2; i*i <= n; ++i)

注意，这个循环将继续执行，只要我 ≤ñ。因此，循环将立即终止，因此，循环将最终运行O（√ n）次，因此该函数的最坏情况时间复杂度为O（√n）。

至于你的第二个问题 - 输入的大小是多少？ - 通常，当查看素数测试算法（或其他大数量的算法）时，输入的大小被定义为写出输入所需的位数。在你的情况下，由于你的编号为n，写出n所需的位数是Θ（log n）。这意味着在这种情况下“多项式时间”可能类似于O（log ^k n）。运行时，O（√ n）时，不被认为是多项式时间，因为O（√ N）= O（（2- ^{为log N}）^1/2），这是按指数比比特的写出来所要求的数量较大输入。

希望这会有所帮助！

来源

2013-10-20 21:32:42 templatetypedef

这个素数测试算法的时间复杂度？

回答

相关问题