Complessità: somma-prodotto

di

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) = c_1+c_2+c_3+c_4+c_5+ ( ... )+c_{10}+c_{11}
= ([c_6+c_7+c_8+c_9]\cdot n+c_6)+7
= (4\cdot n+1)+7
= 4\cdot n+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) = c_1+c_2+c_3+c_4+( ... )+c_8+c_9+( ... )+c_{13}+c_{14}
= ([c_5+c_6+c_7]\cdot n+c_5)+([c_{10}+c_{11}+c_{12}]\cdot n+c_{10})+8
= (3\cdot n+1)+(3\cdot n+1)+8
= 6\cdot n+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.