时间这个素性测试算法的复杂性？ [英] Time complexity of this primality testing algorithm?

问题描述

我有以下的code，它确定一个数字是否为素数：

I have the following code which determines whether a number is prime:

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的时间复杂度？什么是输入的大小在此情况

How can I determine the big-O time complexity of this function? What is the size of the input in this case?

推荐答案

想想这个函数的最坏情况下的运行时间，这恰好如果数字确实是素数。在这种情况下，内部循环将执行许多次尽可能。由于循环的每次迭代不工作的恒定量，所做的总功因此将O（循环迭代的次数）。

Think about the worst-case runtime of this function, which happens if the number is indeed prime. In that case, the inner loop will execute as many times as possible. Since each iteration of the loop does a constant amount of work, the total work done will therefore be O(number of loop iterations).

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

So how many loop iterations will there be? Let's look at the loop bounds:

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

注意，这个循环将继续，只要执行我 ² ＆乐; ñ。因此，循环将尽快结束，因为我与GE; ＆拉迪奇; N + 1。因此，循环的最终会运行O（＆拉迪奇; N）倍，所以该功能的最坏情况下的时间复杂度是O（＆拉迪奇; n）的

Notice that this loop will keep executing as long as i² ≤ n. Therefore, the loop will terminate as soon as i ≥ √n + 1. Consequently, the loop will end up running O(√n) times, so the worst-case time complexity of the function is O(√n).

你的第二个问题 - 什么是输入的大小？ - 通常，当看素性测试算法（或上大数工作的其他算法）时，输入的大小被定义为写出来的输入处所需的比特数。在你的情况，因为你给一个数n，写n个所需的比特数与西塔（log n）的。这意味着，在这种情况下，多项式时间会像O（日志 ^K N）。运行时，O（＆拉迪奇; N），不被认为是多项式时间，因为O（＆拉迪奇; N）= O（（2 ^日志N ） ^1/2 ），这是指数比写出来的输入所需的比特数多。

As to your second question - what is the size of the input? - typically, when looking at primality testing algorithms (or other algorithms that work on large numbers), the size of the input is defined to be the number of bits required to write out the input. In your case, since you're given a number n, the number of bits required to write out n is Θ(log n). This means that "polynomial time" in this case would be something like O(log^k n). Your runtime, O(√n), is not considered polynomial time because O(√n) = O((2^{log n})^1/2), which is exponentially larger than the number of bits required to write out the input.

希望这有助于！

这篇关于时间这个素性测试算法的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！