0

好的，所以我需要一些严肃的运行时帮助！

这个方法应该接受一个 int 值，检查它的素数，true如果这个数字确实是素数，则返回。我理解为什么循环只需要i平方，我知道最坏的情况是数字是素数（或素数的倍数）的情况。但我不明白如何量化实际运行时间。

我自己手动完成了循环，试图了解数字 ( n) 的模式或相关性以及发生了多少循环，但我真的觉得我每次都落入同一个陷阱。我需要一种新的思考方式！

我有一个提示：

“想想整数的大小”

这让我想量化一个数字中整数的字面数量，与它在 for 循环 ( floor log(n)) +1) 中的迭代次数有关。但它不工作？！我知道这显然不是平方根n。

我要求大 O 符号。

public class PrimeHunter 
{

    public static boolean isPrime(int n)
    {
        boolean answer = (n > 1) ? true : false; //runtime = linear runtime

        for (int i = 2; i * i <= n; i++) //runtime = ?????
        {   
            if (n % i == 0) //doesn't occur if it is a prime
            {
                answer = false;
                break;
            }

        }
        return answer; //runtime = linear runtime
    }
}
4

4 回答 4

1

I KNOW it isnt square root n obviously.

好吧，如果它不是平方根，那么绝对没有其他可能性。

我想过这个，除非你在这里省略了一些东西，否则它绝对必须与平方根有关。如果我错了，请纠正我。

要使循环成为 log(n)，您必须在 for 循环中执行 Math.pow(10,i)。

在您的情况下，运行时将是 O(sqrt(n)-1)。

要与 进行比较n，i您必须取 n 的平方根，但由于i从 2 开始，您必须从中减去 1。

编辑：实际上，你是对的。

上述 O 时间仅适用于素数。对于非素数，它是 n 减去 2 的最小素数正因数。

如果删除break，它将使计算运行时变得容易得多。

于 2013-10-20T03:34:29.273 回答
0

一种直观的方法是制作图表。

选择一组n值，例如 1 到 20。绘制一张图表，其中 x 轴是n值，y 轴是循环运行的最坏情况次数。你应该得到一个可视化。

一旦你有了一个可视化，它应该变得更加明显。如果没有，那么您可以在同一张图上绘制一些已知的 Big-O 符号，并查看它们的比较。例如，它接近线性值 ( O(n))、指数值 ( O(n^2)) 还是对数 ( O(log(n))) 值？如果您需要更精确的 Big-O 值，您可以从那里开始。

考虑它的第二种方法是关注这一点：

I understand why the loop only needs to go up to i squared

想想看i，不是i*i。for 循环直到i*i = n，其中i是迭代次数。求解i。

于 2013-10-20T03:39:28.087 回答
0

只有一个循环。它执行maxi - 2 + 1时间 where maxi*maxi = n。并且内部的操作是相同的（需要（受）恒定的时间量）。我觉得你想多了。

实际上，您的教授可能会遇到一个小绊脚石。模运算的时间复杂度，%。在这种情况下，内部项不是很恒定。

于 2013-10-20T04:42:31.953 回答
0 
public static boolean isPrime(int n) <----------- Runtime of floor(logn) +1

      boolean answer = (n > 1) ? true : false; <------ constant runtime

      for (int i = 2; i * i <= n; i++) <------runtime square root n


Total runtime = log(sqrtn) + 1

reduces to 10^n

F.M.L.

QED
于 2013-11-05T17:05:17.190 回答