确定最坏情况下的运行时间(素数)

Question

我需要帮助。我有一个方法可以确定int是否是素数：

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

有人能告诉我如何确定这个程序在最坏情况下的运行时间吗？然后设B等于N的二进制表示中的位数。。。就B而言，最坏的情况是什么？

谢谢！：）

Answer 1

在任何情况下，该函数的运行时间都是O（n），尽管事实上，只有当n真的是素数时，才会出现最坏的情况。

此外，如果你想检测从1到n范围内的所有素数，你的运行时将是O（n^2）。

Answer 2

素数计算器的渐近时间复杂度是O(n)。在这种情况下，没有理由将"B"纳入时间复杂性的计算中。

Answer 3

在第一个接缝处，它需要O（n），但这里有一个问题，如果n=Integer.MaxValue在某个点上等于2147483647，则会达到2147483645，然后当加2时，i将变为2147483647.下一次加，它将变为-2147483647，因此您已将其转换为负数，这可能需要一段时间。

Answer 4

函数错误地声明2不是素数。当前读取return false的第三行应该读取return (n == 2)或Java中的任何正确语法。

该算法的运行时间为O（n），每当n为素数时就会发生。通过将for循环中的测试更改为i * i <= n，可以将运行时间提高到O（sqrtn）。

Answer 5

尖刻的回应是说它以O（1）结束，因为在Java中，n在上面以2^31-1为界。因此，我可以找到一个常数K，这样时间就保证在小于该时间K的时间内完成。

然而，这个回答并没有解决你的问题的意图，也就是说，在n的"合理"范围内，时间作为n的函数是如何不同的。正如其他人已经指出的那样，你的运行时间将是O（n）。

就B而言，可能会有一些混淆，因为整数总是用32位有符号整数表示。然而，如果我们问给定的N值最大需要多少比特，我们可以注意到2^B<N<=2^（B+1），所以如果你的计算需要O（n），它必然需要O（2^B）运算。

此外，正如其他人所指出的，值2存在一个错误条件——很容易修复。此外，使用筛分方法可以很容易地改进这种计算。虽然你并没有真正询问优化，但我免费提供服务。：）请参阅：https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes寻找一种有趣的方法来解决这个问题。信不信由你，这实际上只是优化它的开始。从那里你可以做更多的事情。