Complessità: primo

di

Vedi pagina 206 del libro di testo

n = int(input("n = "))        # c1
i = 2                         # c2
while(n%i != 0):              # c3
    i = i+1                   # c4
if(i == n):                   # c5   
    print(n, "è primo")       # c6
else:
    print(n, "NON è primo")   # c7

T(2) = c_1+c_2+c_3+c_5+c_6 = 5
T(3) = c_1+c_2+(c_3+c_4)+c_3+c_5+c_6 = (2)+5 = 7
T(4) = c_1+c_2+c_3+c_5+c_7 = 5
T(5) = (c_3+c_4)+(c_3+c_4)+(c_3+c_4)+5 = 3*(2)+5 = 11
T(6) = c_1+c_2+c_3+c_5+c_7 = 5
T(7) = … = 5*(2)+5 = 15
…

Quindi

  • Caso ottimo per n = 2 oppure n pari
    T(n) = 5
  • Caso pessimo per n primo perché falliscono tutte le divisioni per i da 2 a n-1 e ha successo la divisione per i = n
    T(n) = 2\cdot (n-2)+5 = 2\cdot n+1

Il problema di decidere se un numero n è primo affrontato con l’algoritmo delle divisioni successive porta a una complessità in tempo lineare (l’operazione più significativa è la divisione).

2

Non è necessario fare le prove con i multipli di 2.
Dopo il 3 si passa al 5, 7, …

…

La complessità rimane lineare ma con un coefficiente moltiplicativo dimezzato.

3

Non è necessario fare le divisioni da 2 a n-1, si può fermare il while a m = \sqrt{n}.

Il problema di decidere se un numero n è primo affrontato con l’algoritmo delle divisioni successive fino alla radice quadrata di n porta a una complessità in tempo sottolineare (polinomiale con esponente 1/2).

Esistono algoritmi con prestazioni migliori… (vedi Wikipedia)