Complessità in tempo

di

Considera gli esempi del libro di testo a pagina 198 e successive.
Lo pseudolinguaggio è tradotto in Python.

1

print("n = ")     # costo=1
n = int(input())  # costo=1
i = i+1           # costo=1

T(n) = 1+1+1 = 3

Per semplificare i calcoli associamo alle tre istruzioni un costo unitario ma in realtà hanno tempi d’esecuzione molto diversi

  1. istruzione di output (10^{-2} s)
  2. istruzione di input (1 s)
  3. addizione e assegnazione (10^{-6} s)

2

print("n = ")        # c1
n = int(input())     # c2
i = 1                # c3
somma = 0            # c4
while(i <= n):       # c5
    somma = somma+i  # c6
    i = i+1          # c7
print("La somma dei primi", n, "numeri è", somma)  # c8

T(n) = c_1 + c_2 + c_3 + c_4 + ( ... ) + c_8
= [(c_5+c_6+c_7)\cdot n+c_5]+5
= (3\cdot n+1)+5
= 3\cdot n + 6

3.1

if(y > 0):  # c1
    r = 1   # c2
    z = 2   # c3

Se l’if(...) ha successo: T_1(n) = c_1 + (c_2 + c_3) = 3
Se l’if(...) fallisce: T_2(n) = c_1 = 1
Quindi: T(n) = 3

3.2

if(y > 0):  # c1
    r = 1   # c2
else:
    z = 2   # c3
    p = 0   # c4
    r = 2   # c5

Se l’if(...) ha successo: T_1(n) = c_1 + (c_2) = 2
Se l’if(...) fallisce: T_2(n) = c_1 + (c_3+c_4+c_5) = 4
Quindi: T(n) = 4

4

def Somma(x, y):
    s = x+y                  # f1
    return s                 # f2
   
print("n = ")                # c1
n = int(input())             # c2
i = 1                        # c3
somma = 0                    # c4  
while(i <= n):               # c5
    somma = Somma(i, somma)  # c6 c7
    i = i+1                  # c8
print("La somma dei primi", n, "numeri è", somma)  # c9

T(n) = c_1+c_2+c_3+c_4+( ... )+c_9
= ([c_5+c_6+c_7+\{ ... \}+c_8]\cdot n+c_5) + 5
= ([f_1+f_2]+4)\cdot n+6
= 6\cdot n + 6

5

if(x > 0):      # c1
    if(y > 0):  # c2
        r = 1   # c3
    else: 
        r = 2   # c4
        t = 1   # c5
    z = 3       # c6

Se …: T_1(n) = c_1 = 1
Se …: T_2(n) = c_1 + (c_2 + [c_3] + c_6) = 4
Se …: T_3(n) = c_1 + (c_2 + [c_4+c_5] + c_6) = 5
Quindi: T(n) = 5

6

i = 0          # c1
while(i < n):  # c2
    i = i+1    # c3

Se i = 0..(n-1) allora il while si ripete n volte.

T(n) = c_1 + (...) = ([c2+c3]\cdot n + c_2)+1 = 2\cdot n + 2

7

Il costrutto repeat ... until ... non è presente in Python

8

L’istruzione originale for è tradotta in while per evidenziare le singole istruzioni

def SommaNumeriPari(n):
    m = 0           # c1
    i = 1           # c2
    while(i <= n):  # c3
        p = 2*i     # c4
        m = m+p     # c5
        i = i+1     # c6
    return m        # c7

T(n) = c_1 + c_2 + ( ... ) + c_7
= ([c_3+c_4+c_5+c_6]\cdot n+c_3)+3
= 4\cdot n + 4

9

Attenzione: il limite del ciclo while è 2\cdot n

i = 0             # c1
while(i < 2*n):   # c2
    i = i+1       # c3
    j = j*3+4367  # c4

T(n) = c_1 + ( ... ) = ([c_2+c_3+c_4]\cdot [2\cdot n] + c_2) + 1 = (3\cdot 2\cdot n +1)+1 = 6\cdot n + 2

10

L’istruzione originale for è tradotta in while per evidenziare le singole istruzioni.

i = 0                   # c1
while(i < n):           # c2
    j = 1               # c3
    while(j <= n):      # c4
        print("CIAO")   # c5
        j = j+1         # c6
    i = i+1             # c7

Se i = 0..(n-1) allora il while esterno cicla n volte.
Se j = 1..n allora il while interno cicla n volte.
Il messaggio CIAO verrà visualizzato n^2 volte

T(n) = c_1 + ( ...) = (c_2+c_3+[ ... ]+c_7)\cdot n+c_2) + 1
= ([ ... ]+3)\cdot n+2 = ( ... )\cdot n +3\cdot n+2
= ([c_4+c_5+c_6]\cdot n+c_4)\cdot n+3\cdot n + 2 = (3\cdot n+1)\cdot n+3\cdot n + 2
= 3\cdot n^2+n + 3\cdot n+2 = 3\cdot n^2+4\cdot n+2

11

Le istruzioni originali for sono tradotte in while per evidenziare le singole istruzioni

def Funzione(n, m):
    x = 0               # c1
    i = 1               # c2
    while(i <= n):      # c3
        j = 1           # c4
        while(j <= m):  # c5
            x = x+1     # c6
            y = x       # c7
            j = j+1     # c8
        i = i+1         # c9
    return x            # c10

Il while esterno cicla n volte.
Il while interno cicla m volte

T(n) = c_1+c_2+( ... )+c_{10}
= ([c_3+c_4+\{ ... \}+c_9]\cdot n+c_3)+3
= ([ ... ]+3)\cdot n+4
= ( ... )\cdot n+3\cdot n + 4
= ([c_5+c_6+c_7+c_8]\cdot m+c_5)\cdot n+3\cdot n + 4
= (4\cdot m+1)\cdot n+3\cdot n + 4
= 4\cdot m\cdot n +n+ 3\cdot n + 4
= 4\cdot m\cdot n + 4\cdot n + 4