Complessità: potenza

Pagina 204 del libro di testo

print("Valore di n")  # c1
n = int(input())      # c2
x = n                 # c3
i = 1                 # c4
while(i < 5):         # c5
    x = x*n           # c6
    i = i+1           # c7
print(x)              # c8

T = c1+c2+c3+c4+[…]+c8
= c1+c2+c3+c4+[c5+c6+c7]*4+c5+c8
= 3*4 + 6
= 18

print("Base")       # c1
x = float(input())  # c2
print("Esponente")  # c3
n = int(input())    # c4
q = 1               # c5
i = 1               # c6
while(i > 0):       # c7
    q = q*x         # c8
    i = i-1         # c9
print(q)            # c10

T = c1+c2+c3+c4+c5+c6+[…]+c10
= [c7+c8+c9]*n+c7+7
= 3*n +1+7
= $3 n + 8$

print("Base")        # c1
x = float(input())   # c2
print("Esponente")   # c3
n = int(input())     # c4
q = 1                # c5
i = n                # c6
while(i > 1):        # c7
    if(i % 2 == 0):  # c8
        x = x*x      # c9
        i = i // 2   # c10
    else: 
        q = q*x      # c11
        i = i-1      # c12
q = q*x              # c13
print(q)             # c14

n potenza di 2

T(2) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7] +c13+c14 = t2+9 = 13

T(4) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7] +c13+c14 = 2*t2+9 = 17

T(8) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7] +c13+c14 = 3*t2+9 = 21

T(n) = $4 \log_2 n + 9$

n non è potenza di 2

T(1) = c1+c2+c3+c4+c5+c6 +[c7] +c13+c14 = 9

T(3) = c1+c2+c3+c4+c5+c6 +[c7+c8+c11+c12] +[c7+c8+c9+c10] +[c7] +c13+c14 = t1+t2+9 = 17

T(5) = c1+c2+c3+c4+c5+c6 +[c7+c8+c11+c12] +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7] +c13+c14 = t1+2*t2+9 = 21

T(6) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7+c8+c11+c12] +[c7+c8+c9+c10] +[c7] +c13+c14 = t1+2*t2+9 = 21

T(7) = c1+c2+c3+c4+c5+c6 +[c7+c8+c11+c12] +[c7+c8+c9+c10] +[c7+c8+c11+c12] +[c7+c8+c9+c10] +[c7] +c13+c14 = 2*t1+2*t2+9 = 25

$T(n) \le 4 \log_2 {(n-1)} + 4 \log_2 {n} + 9$ $\le 8 \log_2 {n} + 9$

Quindi: $T(n) = c_1 \log_2 {n} + c_2$

Calcolare la potenza con l’algoritmo classico porta a una complessità in tempo lineare, $T(n) = 3n + 8$ , che può essere leggermente migliorata sapendo che n è positivo.

Con l’algoritmo “furbo” si ottiene una complessità in tempo logaritmica: $T(n) = c_1 \log_2 {n} + c_2$