打印一定范围内的素数的时间复杂度？

Question

我已经写了一个答案 这 问题，询问以下内容：

打印素数的给定代码的时间复杂度是多少 start 到 end？是吗 $O(结束*\sqrt{n})$?

/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

注意：那不是我的代码。这是由 马赫什87.

我对此的回答是：

---

在你的情况下 $n$ 是 end - start. 。在 $O$ 符号 $n$ 代表问题的大小，范围是 start 和 end 在你的情况下。在 $O$ 您对最坏情况感兴趣，因此我们可以假设 start 总是 0. 。现在 $n$ 只是一个别名 end.

正如我们所定义的 $n$, ，显然 printPrimeSeries 只是 $O(n)$ （从 0 到 end）。该方法使用 findPrimeOrNot 迭代自 2 到 Math.sqrt(n), ，即 $O(\sqrt{n})$. 。将两者结合起来就是 $O(n)O(\sqrt{n})$, ，这只是 $O(n\sqrt{n})$.

请注意， $O$ 符号告诉您有关算法渐近行为的一些信息。如果有 2 个参数也没关系，至少在本例中是这样。

所以是的，你的假设是完全正确的（忽略你写的 end 代替 $n$).

---

其他用户提出正确答案是 $O((结束 - 开始)\sqrt{结束})$. 。我认为这是一个有效的观点，但它没有提供任何有益的信息 $O$ 给定情况的符号。

现在我的问题是：描述给定算法的时间复杂度的正式正确方法是什么？我的推理是有效的还是完全错误的？

Answer 1

两者“时间复杂度都是 $O( 结束 \cdot \sqrt{end} )$” 和 “时间复杂度是 $O( (开始-结束) \cdot \sqrt{end} )$” 是正确的陈述（假设所涉及的整数的算术运算可以在常数时间内执行）。

在某些情况下，第二个上限更严格。例如，设置 $开始=结束-10$ 第一个上层保持不变，而第二个上层简化为 $O(\sqrt{结束})$.

另请注意，“在𝑂表示𝑛表示问题大小，这是您的情况下开始和结束之间的范围。”是错误的。实例的大小（任何合理的编码）是 $O(\日志结束)$.

Answer 2

您的函数 findPrimeOrNot(n) 运行于 $O(n^{1/2})$ 在最坏的情况下。通常执行时间会更快。例如，对于偶数 n，函数在一次除法后返回。但对于素数，测试 sqrt(n) 之前的所有除数，执行时间确实是 $\θ(n^{1/2})$. 。随机整数 x 为素数的概率约为 x / log x。

您必须检查平均划分数到底是多少。使用您可以改进的算法，划分数量至少约为 (end - start) * sqrt (n) / log n ，最多约为 (end - start) * sqrt (n) 划分。

如果你想打印素数，你会发现打印有一个如此大的常数因子，以至于打印约 (end - start) / log n 个素数的执行时间远远大于打印素数的时间，对于任何合理的情况素数范围。