为 Java 中的程序计算 Big-O

Question

我只想问一下这个程序的Big-O是什么。我认为是 n/2，但我不确定。

public static boolean isPrime(int k) {
    if (k <= 1)
        return false;
    else if (k > 2 && k%2 == 0)
        return false;
    else 
    {
        for(int i = 3;i<=k/2;i+=2)
            if (k % i == 0)
                return false;
    }
    return true;
}

Answer 1

复杂度为O(k)，即线性时间。

采取最坏情况执行，其中 k 是 素数。然后你的算法将执行所有行，直到 return true;.

特别是你完全执行了 for 循环，它产生了 (k / 4) - 3 次迭代：

for (int i = 3; i <= k/2; i += 2)

所以你得到 O((k / 4) - 3) 即 O(k).