Pagina 210 del libro di testo
Calcolare la somma e il prodotto dei numeri naturali da 1 a n
1
print("Inserisci un numero") # c1
n = int(input()) # c2
somma = 0 # c3
prodotto = 1 # c4
i = 1 # c5
while(i <= n): # c6
somma = somma+i # c7
prodotto = prodotto*i # c8
i = i+1 # c9
print("Somma =", somma ) # c10
print("Prodotto =", prodotto) # c11
T1(n) = c1+c2+c3+c4+c5+ [ … ] +c6+c10+c11
= c1+c2+c3+c4+c5
+[c6+c7+c8+c9]*n
+c6+c10+c11
= 4n+8
2
print("Inserisci un numero") # c1
n = int(input()) # c2
somma = 0 # c3
i = 1 # c4
while(i <= n): # c5
somma = somma+i # c6
i = i+1 # c7
prodotto = 1 # c8
j = 1 # c9
while(j <= n): # c10
prodotto = prodotto*j # c11
j = j+1 # c12
print("Somma =", somma ) # c13
print("Prodotto =", prodotto) # c14
T2(n) = c1+c2+c3+c4+ [ … ] + c5+c8+c9+ [ … ] +c10+c13+c14
= c1+c2+c3+c4
+[c5+c6+c7]*n
+c5+c8+c9
+[c10+c11+c12]*n
+c10+c13+c14
= 6n+10
Confronto
I due algoritmi appartengono alla stessa classe di complessità (lineare) ma…
=
=
< 1
è più efficiente di
.