Complessità: somma-prodotto

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…

\displaystyle \lim_{n\to +\infty} \frac{T_1(n)}{T_2(n)} = \displaystyle \lim_{n\to +\infty} \frac{4\, n+8}{6\, n+10} = \displaystyle \frac{2}{3} < 1

T_1 è più efficiente di T_2.