1

我有以下代码确定数字是否为素数：

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

4

1 回答 1

5

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

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

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

请注意，只要 i 2 ≤ n，此循环就会一直执行。因此，循环将在 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 )，它比写出输入所需的位数大得多。

希望这可以帮助！

于 2013-10-20T21:32:42.540 回答