Complessità del tempo di stampa numeri primi all'interno di un intervallo?
-
29-09-2020 - |
Domanda
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?
Soluzione
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
Altri suggerimenti
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.