Complessità del tempo di stampa numeri primi all'interno di un intervallo?

Question

Ho scritto una risposta a Questa domanda , che chiede quanto segue:

Qual è la complessità del tempo per il codice specificato che stampa i numeri primi da start a end? È $ o (fine * \ 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);
}

.

Avviso: non è il mio codice. È di mahesh87 .

La mia risposta a questo è:

---

.

Nel tuo caso $ n $ è end - start. In $ o $ notazione $ n $ rappresenta la dimensione del problema, che è l'intervallo tra start e end in il tuo caso. In $ o $ notazione Sei interessato al caso peggiore, quindi possiamo supporre che start sia sempre 0. Ora $ N $ è solo un alias per end.

Come abbiamo definito $ N $ , è ovvio che printPrimeSeries è solo $ o (n) $ (da 0 a end). Il metodo utilizza findPrimeOrNot che itera da 2 a Math.sqrt(n), che è $ O (\ SQRT {N}) $ . La combinazione di entrambi è $ o (n) o (\ sqrt {n}) $ , che è solo $ o (n \ o sqrt {n}) $ .

Si noti che la classe $ o $ notazione ti dice qualcosa sul comportamento asintotico dell'algoritmo. Non importa troppo se ci sono 2 parametri, almeno in questo caso.

Sì sì, il tuo ipotesi è completamente corretto (ignorando che hai scritto end anziché $ n $ ).

---

.

Altri utenti hanno proposto che la risposta corretta sia $ o ((fine - avvio) \ sqrt {end}) $ . Penso che questo sia un punto di vista valido, ma non fornisce alcuna informazione benefica in termini di $ o $ notazione per il caso indicato.

Ora la mia domanda: qual è il modo formalmente corretto per descrivere la complessità del tempo dell'algoritmo dato? Il mio ragionamento è valido o è semplicemente sbagliato?

Answer 1

Entrambe "la complessità del tempo è $ o (fine \ cdot \ sqrt {end}) $ " e "la complessità del tempo è $ O ((Start-End) \ CDOT \ SQRT {END}) $ " sono dichiarazioni corrette (supponendo che le operazioni aritmetiche su interi coinvolti possano essere eseguite in tempo costante).

Il secondo limite superiore è più stretto in alcuni casi.Ad esempio, impostare $ avvio= fine-10 $ la prima superiore non rimane invariata mentre il secondo semplifica in $ o (\sqrt {end}) $ .

Si noti inoltre che "in

Answer 2

La tua funzione findprimemorrormort (n) funziona in $ o (n ^ {1/2}) $ nel caso peggiore.Spesso il tempo di esecuzione è più veloce.Ad esempio per anche numeri n, la funzione ritorna dopo una singola divisione.Ma per le prime, dove tutti i divisori fino a SQRT (N) sono testati, il tempo di esecuzione è effettivamente $ \ theta (n ^ {1/2}) $ .E la possibilità che un intero casuale x è primo è di x / log x.

Dovresti controllare quale sia esattamente il numero medio di divisioni.Con il tuo algoritmo, che può essere migliorato, il numero di divisioni è almeno di circa (fine-inizio) * SQRT (N) / log n e al massimo circa (inizio finale) * SQRT (N) Divisioni.

Se si desidera stampare i primi, scoprirai che la stampa ha un fattore costante così grande che il tempo di esecuzione della stampa di stampa (fine-avvio) / log n primes è molto più grande del tempo per la stampa dei primi,per qualsiasi gamma ragionevole di PREMES.