Zeitkomplexität beim Drucken von Primzahlen innerhalb eines Bereichs?

Question

Ich habe eine Antwort geschrieben Das Frage, in der es um Folgendes geht:

Wie groß ist die Zeitkomplexität für den angegebenen Code, aus dem Primzahlen gedruckt werden? start Zu end?Ist es $O(end*\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);
}

Beachten:Das ist nicht mein Code.Es ist vorbei mahesh87.

Meine Antwort darauf ist:

---

In Ihrem Fall $n$ Ist end - start.In $O$ Notation $n$ stellt die Problemgröße dar, also den Bereich dazwischen start Und end in Ihrem Fall.In $O$ Notation Sie interessiert den schlimmsten Fall, daher können wir davon ausgehen start ist immer 0.Jetzt $n$ ist nur ein Alias ​​für end.

Wie wir es definiert haben $n$, Es ist klar, dass printPrimeSeries ist nur $O(n)$ (aus 0 Zu end).Die Methode verwendet findPrimeOrNot das iteriert von 2 Zu Math.sqrt(n), welches ist $O(\sqrt{n})$.Beides zu kombinieren ist $O(n)O(\sqrt{n})$, was gerecht ist $O(n\sqrt{n})$.

Beachten Sie, dass die $O$ Die Notation sagt Ihnen etwas über das asymptotische Verhalten des Algorithmus.Zumindest in diesem Fall spielt es keine große Rolle, ob es zwei Parameter gibt.

Also ja, Ihre Annahme ist völlig richtig (ohne Rücksicht darauf, was Sie geschrieben haben). end anstatt $n$).

---

Andere Benutzer haben vorgeschlagen, dass die richtige Antwort ist $O((end - start)\sqrt{end})$.Ich denke, dass dies ein berechtigter Standpunkt ist, aber er liefert keine nützlichen Informationen in Bezug auf $O$ Notation für den gegebenen Fall.

Nun meine Frage:Wie lässt sich die zeitliche Komplexität des gegebenen Algorithmus formal korrekt beschreiben?Ist meine Argumentation gültig oder ist sie einfach falsch?

Answer 1

Sowohl „die zeitliche Komplexität ist $O( end \cdot \sqrt{end} )$" und "die Zeitkomplexität ist $O( (Start-Ende) \cdot \sqrt{end} )$" sind korrekte Aussagen (vorausgesetzt, dass arithmetische Operationen auf den beteiligten ganzen Zahlen in konstanter Zeit ausgeführt werden können).

Die zweite Obergrenze ist in manchen Fällen enger.Zum Beispiel Einstellung $start=end-10$ Das erste Obermaterial bleibt unverändert, während das zweite vereinfacht wird $O(\sqrt{end})$.

Beachten Sie auch, dass "in 𝑂 Notation 𝑛 die Problemgröße darstellt, was der Bereich zwischen Start und Ende in Ihrem Fall ist". ist falsch.Die Größe (jede angemessene Codierung) der Instanz beträgt $O(\log end)$.

Answer 2

Ihre Funktion findPrimeOrNot(n) wird ausgeführt $O(n^{1/2})$ im schlimmsten Fall.Oft ist die Ausführungszeit schneller.Beispielsweise kehrt die Funktion für gerade Zahlen n nach einer einzelnen Division zurück.Aber für Primzahlen, bei denen alle Teiler bis sqrt(n) getestet werden, beträgt die Ausführungszeit tatsächlich $ heta(n^{1/2})$.Und die Wahrscheinlichkeit, dass eine zufällige ganze Zahl x eine Primzahl ist, beträgt etwa x / log x.

Sie müssten überprüfen, wie hoch die durchschnittliche Anzahl der Unterteilungen genau ist.Mit Ihrem Algorithmus, der verbessert werden kann, beträgt die Anzahl der Unterteilungen mindestens etwa (Ende – Anfang) * Quadrat(n) / log n und höchstens etwa (Ende – Anfang) * Quadrat(n) Unterteilungen.

Wenn Sie die Primzahlen drucken möchten, werden Sie feststellen, dass das Drucken einen so großen konstanten Faktor hat, dass die Ausführungszeit für das Drucken von ungefähr (Ende - Start) / log n Primzahlen aus vernünftigen Gründen viel länger ist als die Zeit für das Drucken der Primzahlen Bereich von Primzahlen.