Presente?

Fissa una lista di numeri e un certo valore

LISTA = [1,8,0,1,1,9,2,8]
KEY   = 9

Il valore è presente o meno all’interno della lista?

Soluzione 1

def presente(lista, k): 
    n=len(lista) 
    risp=False 
    for i in range(n): 
        if(lista[i] == k): 
            risp=True 
    return risp


LISTA    = [1,8,0,1,1,9,2,8] 
KEY      = 9
risposta = presente(LISTA, KEY) # True

La funzione restituisce risp

  • risp=False se k non è presente
  • risp=True se k è presente

Soluzione 2

def presente(lista, k): 
    n=len(lista) 
    for i in range(n): 
        if(lista[i] == k): 
            return True 
    return False

Osserva

  1. Perché aspettare la fine del ciclo for per restituire la risposta affermativa?
  2. La variabile risp non è più necessaria.
  3. L’istruzione return aggiuntiva peggiora la leggibilità del codice.

Complessità degli algoritmi

  1. Sempre, T(n)=c_1+c_2\cdot n
  2. Mediamente, T(n)=c_1+c_2\cdot\frac{n}{2}