Modulo Operatore Runtime

Question

Modulo Operatore Runtime

Naviga le tue risposte

#1 da (2 voti)

0

Sto leggendo un foglio di revisione per una classe e l'istruttore ha detto questo all'operatore modulo:

Ricorda che il modulo (%) ha un runtime di O ((logn) ^ 2).

Ha continuato a visualizzare questo codice:

// Presuppone n > 1

public boolean isPrime2 (int n) {
    int sqrtN = (int) Math. sqrt (n) ;
    for(int i = 2; i < sqrtN + 1; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Ha detto di questo codice:

O (n) = sqrt (n) x n ^ 2. Come puoi vedere, questo metodo per verificare se un numero è primo, itera da 2 a sqrt (n). Poiché eseguiamo il ciclo su un'operazione quadratica di sqrt (n) volte, il runtime è O (sqrt (n)).

Due cose che non capisco. Uno, perché l'interno del ciclo for ora è un'operazione n ^ 2 piuttosto che un'operazione (logn) ^ 2. Due, anche se è solo un'operazione n ^ 2, il tempo di esecuzione totale non dovrebbe essere O (n)?

runtime

posta rakrakrakrak 25.07.2014 - 09:34

fonte

1 risposta

Leggi altre domande sui tag runtime

Quale diagramma sarebbe il migliore per descrivere la situazione Quando utilizzare i pacchetti o i repository in Laravel?

score 2 · Accepted Answer

Suppongo che il foglio di recensione che stai leggendo sia difettoso:

Modulo / resto è un'operazione O(1) (è essenzialmente solo una variazione sulla divisione, che richiede un tempo costante su numeri fissi ).
Pertanto, l'interno del ciclo è un'operazione O(1) ,
che rende la complessità totale O(√n) .

Tuttavia, supponiamo per un momento che % denoti un operatore di sprechi con complessità O(log(n)²) . In tal caso, ci ritroveremmo con una complessità O(√n · log(n)²) . L'espressione √n · log(n)² non può essere semplificata. Tuttavia, la classe di complessità O(√n · n²) include O(√n · log(n)²) :

   O(√n · n²) includes O(√n · log(n)²)
⇔    √n · n²      >      √n · log(n)²
⇔         n²      >           log(n)²   assuming n ≠ 0
⇔         n       >           log(n)    assuming n > 0
which is true for n > 1

Delle tre condizioni n ≠ 0 , n > 0 , n > 1 l'ultimo è il più strong ed è garantito da un commento nel codice. Sarebbe quindi corretto dire che il codice ha una complessità di O(√n · n²) , sebbene sia anche vero che ha una complessità di O(√n · log(n)²) , che è una dichiarazione più strong.

Nota che l'espressione √n · n² può essere semplificata, ma non a n :

   √n · n²
=  n^1/2 · n²
=  n^{1/2 + 2}
=  n^5/2
=  √(n⁵)