Qual è la complessità temporale dell'algoritmo per verificare se un numero è primo?
Questo è l'algoritmo:
bool isPrime (int number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int i=3; (i*i) <= number; i+=2) {
if (number % i == 0 ) return false;
}
return true;
}
O (sqrt (n)) nella grandezza del numero, ma solo fino a quando usi int
Si noti che le complessità per gli algoritmi relativi ai numeri primi sono spesso discussi con n come la lunghezza (in bit) del numero - e che non si può assumere cose come comparare, aggiungere, modulare o moltiplicare per essere O (1), perché con numeri di precisione arbitrari queste operazioni diventano più costose con le dimensioni del numero.
Il miglior algoritmo attualmente conosciuto viene eseguito in O ((log n) ^ 6)
Il caso peggiore - quando il numero è primo - è abbastanza ovvio O (sqrt (n)) Il caso migliore si verifica quando il numero può essere diviso per 2,3,5,7,9. In questi casi termineremo il ciclo molto presto in un numero finito di passaggi - O (1)
Ora consente di calcolare il caso medio per l'algo:
Nell'intervallo [0, n] ci sono i numeri primi aprox n / ln (n).
L'algo raggiunge il primo con probabilità di P1 = 1 / ln (n)
Gli altri numeri con probabilità di P2 = 1-ln (n)
Il caso medio è O (sqrt (n)) * 1 / ln (n) + O (1) * (1-ln (n)) Ci liberiamo di una parte più piccola
=O(sqrt(n))/ln(n)
sposta ln (n) all'interno di O ()
=O(sqrt(n)/ln(n))
base del logaritmo non ha importanza per la notazione O grande
= O(sqrt(n)/log(n))
Il tempo massimo di esecuzione di questo algoritmo è O (sqrt (n)), che sarà raggiunto se n è primo o il prodotto di due grandi numeri primi.
Il tempo medio di esecuzione è complicato; Direi qualcosa come O (sqrt (n) / log n), perché non ci sono molti numeri con solo grandi fattori primi.
Leggi altre domande sui tag numbers algorithms complexity