Qual è la complessità di trovare e controllare i numeri primi?

Question

Qual è la complessità di trovare e controllare i numeri primi?

#1 da (2 voti)
#2 da (1 voti)
#3 da (0 voti)

2

Sto cercando di capire la complessità di queste due funzioni che ho scritto ma non ho potuto capire.def

In primo luogo, ho pensato che fosse supposto essere O(N) . Ma non è chiaro quante volte il ciclo si avvia perché non ho idea di quanti numeri primi possano essere trovati.

def self.find_primes(n)
    primes = []
    total = 0
    i = 2

    while total < n do
      if is_prime i
        primes.push i
        total += 1
      end

      i += 1
    end

    primes
end

Nella seconda funzione, si suppone che sia O(N/2) .

  def self.is_prime n
    (2..n/2).none?{|i| n % i == 0}
  end

algorithms big-o ruby

posta aravvn 01.07.2018 - 03:33

fonte

3 risposte

Leggi altre domande sui tag algorithms big-o ruby

Comunicazione dell'operazione prevista della logica di business dell'API per gli sviluppatori e gli uomini d'affari Esistono standard per la gestione dei tergicristalli nelle applicazioni?

score 2 · Answer 1

La stima del numero di iterazioni nella prima funzione è tutt'altro che banale. Fortunatamente, alcuni ragazzi intelligenti hanno già fatto il duro lavoro per noi diversi anni fa.

In realtà è la dimensione prevista dell'n ° primo, che è l'inverso del cosiddetto conteggio perfetto funzione . L'ultima funzione è nota approssimativamente x/ln(x) , e per il comportamento asintotico del suo inverso, guarda in questa domanda su mathoverflow. Dalla risposta accettata vediamo che la risposta è approssimativamente

   n * ln(n) + n*ln(ln(n)) − n

Si noti inoltre che la complessità big-O della prima funzione non è questa formula, ma il prodotto di questa è moltiplicato per la complessità del secondo.

Per la tua seconda funzione, nota che O (N / 2) = O (N). Inoltre, non è necessario testare tutti i valori fino a n / 2 per verificare se n è primo. La radice quadrata di n è sufficiente per questo, quindi se la si implementa in questo modo, si finisce con O (sqrt (N)).

score 1 · Answer 2

Non riesci a trovare la complessità temporale del tuo codice se non sai come implementare nessuno? lavori. Nel peggiore dei casi, quando n è un numero primo, è necessario testare tutti i valori, che sarebbero circa n / 2 operazioni.

Ma solo? potrebbe testare comunque tutti i casi n / 2. O solo? potrebbe iniziare con il valore più grande nell'intervallo, nel qual caso il numero medio di passaggi sarà vicino a n / 2.

score 0 · Answer 3

Prima di tutto, quando eseguiamo l'analisi della complessità, di solito consideriamo il numero di bit come la dimensione di un numero, non la sua grandezza. Quando aggiungiamo un singolo bit a una variabile, il numero di valori possibili raddoppia, quindi questo nitpick rende il tuo algoritmo esponenziale!

Ma okay, se prendiamo la grandezza come la dimensione di un numero, allora l'analisi della seconda funzione sembra essere corretta (facendo alcune ipotesi sull'implementazione di nessuno?). Di solito, i fattori costanti vengono ignorati, quindi dovremmo chiamarlo O (N).

Per la prima funzione, O (N) è una buona ipotesi, tranne che chiama la seconda, quindi devi moltiplicarla in: O (N * N). Se vuoi un'analisi più precisa, potresti effettivamente provare a contare il numero di numeri primi, ma non è necessario: è un limite superiore.