这种素性测试算法的时间复杂度？

Question

我有以下代码,它确定一个数字是否为素数:

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时间复杂度？在这种情况下,输入的大小是多少？

Answer 1

想想这个函数的最坏情况运行时,如果数字确实是素数就会发生.在这种情况下,内循环将执行尽可能多的次数.由于循环的每次迭代都会进行一定量的工作,因此完成的总工作量将为O(循环迭代次数).

那么有多少循环迭代？让我们看一下循环边界:

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

注意,这个循环将继续只要我执行² ≤ñ.因此,一旦i≥√n+ 1,循环就会终止.因此,循环最终将运行O(√n)次,因此函数的最坏情况时间复杂度为O(√n).

至于你的第二个问题 - 输入的大小是多少？ - 通常,在查看素数测试算法(或其他适用于大数的算法)时,输入的大小定义为写出输入所需的位数.在您的情况下,由于您给出了数字n,因此写出n所需的位数是Θ(log n).这意味着在这种情况下"多项式时间"将类似于O(log ^k n).您的运行时间O(√n)不被视为多项式时间,因为O(√n)= O((2 ^{log n})^1/2),它指数大于写出输入所需的位数.

希望这可以帮助!