¿Complejidad temporal de imprimir números primos dentro de un rango?

Question

He escrito una respuesta a este pregunta, que pregunta sobre lo siguiente:

¿Cuál es la complejidad temporal del código dado que imprime números primos desde start a end?Lo es $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);
}

Aviso:Ese no es mi código.es por mahesh87.

Mi respuesta a eso es:

---

En tu caso $n$ es end - start.En $O$ notación $n$ representa el tamaño del problema, que es el rango entre start y end en tu caso.En $O$ notación que le interesa en el peor de los casos, por lo tanto podemos suponer que start es siempre 0.Ahora $n$ es solo un alias para end.

Como hemos definido $n$, es obvio que printPrimeSeries es solo $O(n)$ (de 0 a end).El método utiliza findPrimeOrNot que itera desde 2 a Math.sqrt(n), cual es $O(\sqrt{n})$.Combinar ambos es $O(n)O(\sqrt{n})$, que es simplemente $O(n\sqrt{n})$.

Note que el $O$ La notación le dice algo sobre el comportamiento asintótico del algoritmo.No importa demasiado si hay 2 parámetros, al menos en este caso.

Entonces sí, tu suposición es completamente correcta (ignorando que has escrito end en lugar de $n$).

---

Otros usuarios han propuesto que la respuesta correcta es $O((fin - inicio)\sqrt{fin})$.Creo que este es un punto de vista válido pero no proporciona ninguna información beneficiosa en términos de $O$ notación para el caso dado.

Ahora mi pregunta:¿Cuál es la forma formalmente correcta de describir la complejidad temporal del algoritmo dado?¿Mi razonamiento es válido o simplemente es incorrecto?

Answer 1

Tanto "la complejidad del tiempo es $O( final \cdot \sqrt{end} )$" y "la complejidad del tiempo es $O( (inicio-fin) \cdot \sqrt{end} )$"son afirmaciones correctas (suponiendo que las operaciones aritméticas con los números enteros involucrados se puedan realizar en tiempo constante).

El segundo límite superior es más estricto en algunos casos.Por ejemplo, estableciendo $inicio=fin-10$ la primera parte superior permanece sin cambios mientras que la segunda se simplifica para $O(\sqrt{end})$.

Observe también que "en 𝑂 𝑂 notación 𝑛 representa el tamaño del problema, que es el rango entre el inicio y el final en su caso". Es falso.El tamaño de (cualquier codificación razonable de) la instancia es $O(\final de registro)$.

Answer 2

Su función findPrimeOrNot(n) se ejecuta en $O(n^{1/2})$ En el peor de los casos.A menudo el tiempo de ejecución es más rápido.Por ejemplo, para números pares n, la función regresa después de una sola división.Pero para los números primos, donde se prueban todos los divisores hasta sqrt(n), el tiempo de ejecución es de hecho $ heta(n^{1/2})$.Y la probabilidad de que un número entero aleatorio x sea primo es aproximadamente x / log x.

Tendrías que comprobar cuál es exactamente el número medio de divisiones.Con su algoritmo, que se puede mejorar, el número de divisiones es al menos de aproximadamente (fin - inicio) * sqrt (n) / log n y como máximo de aproximadamente (fin - inicio) * sqrt (n) divisiones.

Si desea imprimir los números primos, encontrará que la impresión tiene un factor constante tan grande que el tiempo de ejecución de la impresión about (fin - inicio) / log n números primos es mucho mayor que el tiempo para imprimir los números primos, para cualquier precio razonable. rango de números primos.