Ricerca sequenziale

Considera una lista di numeri e un certo valore


Presente?


Decidere se x è presente o meno all’interno della lista

La funzione restituisce

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

Complessità:  T(n)=c_1+c_2\cdot n


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à:  T(n)=c_1+c_2\cdot\frac{n}{2}


Posizione? Ricerca sequenziale


Individuare la posizione di x all’interno della lista

La funzione restituisce

  • pos=-1 se x non è presente
  • pos=i se x è presente alla posizione i (l’ultima…)

Complessità:  T(n)=c_1+c_2\cdot n


Perché aspettare?
Restituisce la prima posizione.

Complessità:  T(n)=c_1+c_2\cdot\frac{n}{2}


Il ciclo while evidenzia le operazioni sulla variabile i

Complessità:  T(n)=c_1+c_2\cdot n


Come prima, doppio return

Complessità:  T(n)=c_1+c_2\cdot\frac{n}{2}


Per interrompere il ciclo while non è necessario utilizzare l’istruzione return

Complessità:  T(n)=c_1+c_2\cdot\frac{n}{2}

Notice: This work is licensed under a BY-NC-SA. Permalink: Ricerca sequenziale

Comments are closed.