Ricerca, ordinamento e complessità: come capire se il tuo codice è veloce o lento, e perché.
Un algoritmo è semplicemente una sequenza di passaggi precisi per risolvere un problema, un po' come una ricetta di cucina. Hai già scritto algoritmi senza saperlo: ogni funzione che hai creato è un piccolo algoritmo. Ora impariamo a valutarne l'efficienza.
Se devi cercare un nome in un elenco di 10 persone, qualsiasi metodo va bene. Ma se l'elenco ha 10 milioni di persone, la scelta dell'algoritmo fa la differenza tra un risultato istantaneo e uno che richiede minuti. La "complessità" misura come il tempo di esecuzione cresce all'aumentare dei dati.
| Notazione | Nome | Esempio |
|---|---|---|
| O(1) | Tempo costante | Accedere a un elemento di lista per indice |
| O(log n) | Logaritmico | Ricerca binaria |
| O(n) | Lineare | Ricerca lineare, scorrere una lista una volta |
| O(n²) | Quadratico | Bubble sort, cicli annidati sulla stessa lista |
Controlla ogni elemento uno per uno, dall'inizio alla fine, finché non trova quello cercato. Funziona su qualsiasi lista, anche non ordinata, ma può essere lenta su grandi quantità di dati.
Su una lista già ordinata, dimezza ripetutamente l'area di ricerca: guarda l'elemento centrale, decide se il target è a sinistra o a destra, e ripete. Molto più veloce della ricerca lineare su grandi liste.
Un algoritmo di ordinamento semplice: confronta coppie di elementi adiacenti e li scambia se sono nell'ordine sbagliato, ripetendo finché la lista non è ordinata. Semplice da capire ma inefficiente su grandi liste.
Un modo standard per descrivere come cresce il tempo di esecuzione di un algoritmo all'aumentare della quantità di dati (n). Non misura il tempo esatto, ma la "tendenza di crescita".
Un algoritmo può dare il risultato corretto ma essere impraticabile su grandi quantità di dati. Capire la complessità aiuta a scegliere l'approccio giusto prima che diventi un problema reale.
Spunta ogni passaggio man mano che lo completi: sbloccherai l'attestato di questa guida al termine.
Esempio per il punto 1
def ricerca_lineare(lista, target): for i, valore in enumerate(lista): if valore == target: return i return -1 print(ricerca_lineare([5,2,9,1], 9)) # 2
Esempio per il punto 2
def ricerca_binaria(lista_ordinata, target): inizio, fine = 0, len(lista_ordinata) - 1 while inizio <= fine: centro = (inizio + fine) // 2 if lista_ordinata[centro] == target: return centro elif lista_ordinata[centro] < target: inizio = centro + 1 else: fine = centro - 1 return -1
Esempio per il punto 3
def bubble_sort(lista): n = len(lista) for i in range(n): for j in range(n - i - 1): if lista[j] > lista[j+1]: lista[j], lista[j+1] = lista[j+1], lista[j] return lista
Esempio per il punto 4
import time inizio = time.time() ricerca_lineare(list(range(100000)), 99999) print(time.time() - inizio) # secondi impiegati
Tocca ogni termine per vederne la definizione.
Crea una lista di 20 nomi. Scrivi una funzione di ricerca lineare che restituisca la posizione di un nome cercato, o -1 se non trovato. Testala con un nome presente e uno assente.
Prendi una lista di 15 numeri disordinati. Ordinala con il tuo bubble sort, poi cerca un numero specifico usando la ricerca binaria sulla lista ora ordinata.
Questo codice non trova un elemento che pure è presente nella lista: la ricerca binaria viene applicata a una lista non ordinata. Spiega perché la ricerca binaria richiede una lista ordinata per funzionare correttamente.
Completa tutti i 5 passaggi della checklist per sbloccare il tuo attestato in PDF.