java - isPrime 算法的渐近运行时间根据输入大小 n

Question

我在下面有一个 isPrime 函数:

public static boolean isPrime(int n) {
    if(n == 1) return false;
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0) return false;
    }
    return true;
}

我的问题是:

1. 这个算法的渐近运行时间是多少大小 ||n||输入？
2. 解释为什么在“1”是输入大小的指数。

这里我不明白的是为什么这个算法是指数的。

Note: This question was asked in an algorithm exam.

Answer 1

首先，我们可以看到该算法在单个语句(if 语句)上循环最多 sqrt(n) 次。所以它的运行时间与n的值的平方根成正比。

现在，问题询问运行时间相对于输入的大小，而不是输入的值。输入大小是用于存储输入的存储量。在这种情况下，输入只是一个数字 n。

一个数字 n，当以二进制表示时(当它以任何其他基数表示时，这个论点仍然成立)，有 log n 位，所以循环 sqrt(n) 时间是输入大小的指数，因为输入大小是 log n 并且 sqrt(n) = exp(C * log n) 与 C = 0.5。

因此我们得到的算法是输入大小的指数。