Le temps de la complexité de l'impression des nombres premiers dans une plage?

Question

J'ai écrit une réponse à cette question, qui pose des questions sur les éléments suivants:

Qu'est-ce que la complexité du temps pour le code, qui imprime des nombres premiers à partir de start pour end?Est-il $O(fin*\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);
}

Avis:Ce n'est pas mon code.C'est par mahesh87.

Ma réponse est:

---

Dans votre cas $n$ est end - start.Dans $O$ la notation $n$ représente la taille du problème, qui est la distance entre start et end dans votre cas.Dans $O$ notation vous êtes intéressé dans le pire des cas, donc on peut supposer que start est toujours 0.Maintenant $n$ est juste un alias pour end.

Comme nous l'avons défini $n$, il est évident que printPrimeSeries est juste $O(n)$ (à partir de 0 pour end).La méthode utilise findPrimeOrNot qui effectue une itération à partir de 2 pour Math.sqrt(n), qui est $O(\sqrt{n})$.En combinant les deux est $O(n)O(\sqrt{n})$, qui est juste $O(n\sqrt{n})$.

Notez que l' $O$ notation vous dit quelque chose sur le comportement asymptotique de l'algorithme.Il n'importe pas trop si il y a 2 paramètres, au moins dans ce cas.

Donc oui, votre hypothèse est tout à fait correcte (en ignorant que vous avez écrit end au lieu de $n$).

---

D'autres utilisateurs ont proposé que la réponse correcte est $O((fin - début)\sqrt{fin})$.Je pense que c'est un bon point de vue, mais il ne fournit pas toutes les informations bénéfique en termes de $O$ notation pour le cas d'espèce.

Maintenant, ma question:Qu'est-ce que la façon formellement correcte pour décrire la complexité temporelle de l'algorithme donné?Est mon raisonnement valide ou est-il tout simplement faux?

Answer 1

Les deux "le temps de la complexité est $O( fin \cdot \sqrt{fin} )$"et "le temps de la complexité est $O( (début-fin) \cdot \sqrt{fin} )$"sont correctes (en supposant que les opérations arithmétiques sur les nombres entiers peuvent être effectuées en temps constant).

La deuxième limite supérieure est plus dans certains cas.Par exemple, la définition $start=fin-10$ la première supérieure reste inchangée, tandis que la seconde se simplifie à $O(\sqrt{fin})$.

Notez également que "Dans 𝑂 notation 𝑛 représente la taille du problème, qui est l'intervalle entre le début et la fin dans votre cas." est fausse.La taille de la (toute raisonnable d'encodage de) l'instance est $O(\log fin)$.

Answer 2

Votre fonction findPrimeOrNot(n) s'exécute dans $O(n^{1/2})$ dans le pire des cas.Souvent le temps d'exécution est plus rapide.Par exemple, pour le même nombre n, la fonction retourne après une seule des divisions.Mais pour les nombres premiers, où tous les diviseurs jusqu'à sqrt(n) sont testés, le temps d'exécution est en effet $ heta(n^{1/2})$.Et la probabilité qu'un entier aléatoire x est premier est sur x / log x.

Vous devez vérifier ce qu'est exactement le nombre moyen de divisions.Avec votre algorithme, qui peut être améliorée, le nombre de divisions est d'au moins environ (fin - début) * sqrt (n) / log n et au plus environ (fin - début) * sqrt (n) divisions.

Si vous souhaitez imprimer les nombres premiers, vous aurez à trouver que l'impression a un grand facteur constant que le temps d'exécution de l'impression sur (fin - début) / log n nombres premiers est beaucoup plus grand que le temps d'impression des nombres premiers, pour une gamme raisonnable de nombres premiers.