Infognati - Algoritmi e Strutture Dati

Definizione di Algoritmo

Un Algoritmo è una sequenza finita e ordinata di passi elementari che porta alla risoluzione di un problema in un tempo finito. Non è semplicemente "codice", ma una strategia logica per trasformare un Input in un Output corretto.

Per essere valido, un algoritmo deve possedere alcune proprietà fondamentali: deve essere non ambiguo (ogni passo deve essere chiaro), eseguibile (i passi devono essere realizzabili da un calcolatore) e finito (deve terminare prima o poi).

Problemi, Istanze e Correttezza

È cruciale distinguere tra un problema e le sue varianti:

Problema: Una funzione che associa ogni input al relativo output corretto (es. "Ordinare una lista di numeri").
Istanza: Un caso specifico di input per quel problema (es. la lista specifica [5, 2, 9, 1]).

Algoritmo Corretto: Un algoritmo si dice corretto se, per ogni istanza del problema, termina producendo l'output desiderato. Se l'algoritmo fallisce anche solo su una singola istanza, viene considerato errato.

Il Modello di Calcolo: Macchina RAM

Per misurare quanto è "veloce" un algoritmo senza dipendere dal tipo di computer usato, utilizziamo un modello teorico chiamato Macchina RAM (Random Access Machine).

In questo modello, ipotizziamo di avere un processore che esegue istruzioni in sequenza e una memoria di dimensione infinita dove ogni cella è accessibile in tempo costante. Le operazioni elementari (somma, confronto, assegnamento) hanno un Costo Uniforme, ovvero ogni operazione richiede 1 unità di tempo.

Perché studiare l'efficienza? Un algoritmo inefficiente può impiegare secoli per elaborare pochi dati, mentre uno efficiente può gestire milioni di record in pochi secondi. La risorsa più preziosa non è più la memoria, ma il Tempo di Calcolo.

Analisi della Complessità Asintotica

Quando analizziamo un algoritmo, non ci interessa il tempo esatto misurato in secondi, poiché questo dipenderebbe dalla potenza del computer utilizzato. Ci focalizziamo invece su come il tempo di esecuzione cresce al crescere della dimensione dell'input n. Questo studio prende il nome di Analisi Asintotica.

Esistono tre simboli matematici fondamentali utilizzati per definire i limiti di questa crescita:

O-grande (O): Rappresenta un limite superiore. Indica che l'algoritmo non supererà mai una certa soglia di tempo. È il parametro fondamentale per descrivere il caso peggiore.

Omega (Ω): Rappresenta un limite inferiore. Indica che l'algoritmo richiederà almeno un certo tempo per essere eseguito (caso migliore).

Theta (Θ): Definisce un ordine di grandezza esatto. Si usa quando l'algoritmo si comporta sempre nello stesso modo, "stretto" tra il limite superiore e quello inferiore.

Approfondimento sull'Analisi dei Casi

L'analisi delle prestazioni non è un valore statico, ma una funzione che varia in base alla disposizione dei dati in ingresso. Comprendere queste distinzioni permette di selezionare l'algoritmo più idoneo per lo scenario d'uso specifico, bilanciando affidabilità e velocità.

1. Caso Peggiore (Worst Case - O)

Rappresenta il limite superiore (upper bound) garantito. In ingegneria del software, è la metrica più critica: assicura che il sistema non superi mai tempi di risposta inaccettabili, anche nelle condizioni più sfavorevoli. È fondamentale per i sistemi real-time o mission-critical.

Esempio: Nella ricerca sequenziale, il caso peggiore si verifica quando l'elemento è l'ultimo della lista o del tutto assente, costringendo l'algoritmo a compiere esattamente n confronti.

2. Caso Migliore (Best Case - Ω)

Rappresenta il limite inferiore (lower bound). Sebbene raramente usato per la pianificazione delle risorse, è essenziale per valutare gli algoritmi adattivi, ovvero quelli progettati per trarre vantaggio da input parzialmente strutturati o pre-ordinati.

Esempio: Il Bubble Sort ottimizzato può terminare in tempo lineare O(n) se riceve una lista già ordinata, rilevando l'assenza di scambi al primo passaggio.

3. Caso Medio (Average Case - Θ)

È la media pesata del tempo di esecuzione su tutte le possibili istanze di input. Richiede un'analisi probabilistica complessa, ma descrive ciò che l'utente sperimenta nella maggior parte delle interazioni reali.

Esempio: Il Quick Sort ha un caso peggiore degradato di O(n²), ma il suo caso medio è un efficientissimo O(n log n), rendendolo nella pratica più veloce di molti algoritmi con caso peggiore migliore.

Perché non basta il Caso Peggiore?

La scelta dell'algoritmo dipende dal contesto applicativo. In un software di controllo di un reattore nucleare, si progetta esclusivamente sul Caso Peggiore per evitare catastrofi. In un motore di ricerca web, si ottimizza per il Caso Medio, accettando che una ricerca su un miliardo possa essere leggermente più lenta in favore di una velocità media superiore per tutti gli altri utenti.

Complessità Spaziale e In-Place

Oltre al tempo, l'analisi asintotica valuta la Complessità Spaziale, ovvero la quantità di memoria extra (stack e heap) necessaria all'algoritmo per giungere alla soluzione.

Algoritmi In-place: Sono quelli che operano direttamente sui dati di input, richiedendo una quantità di memoria aggiuntiva costante, ovvero O(1). Sono ideali per sistemi con risorse limitate (es. sistemi embedded).
Trade-off Tempo-Spazio: Spesso è possibile velocizzare un algoritmo utilizzando più memoria (es. tabelle di hash o tecniche di Memoization nella Programmazione Dinamica).

Gerarchia delle Funzioni di Costo

Gli algoritmi vengono raggruppati in classi di efficienza. Ecco le più comuni, presentate in una struttura adatta a ogni dispositivo:

Notazione	Nome	Descrizione ed Esempio
O(1)	Costante	Il tempo non dipende da n (es: accesso a un elemento di un array).
O(log n)	Logaritmica	Tipica di algoritmi che dimezzano il problema (es: ricerca binaria).
O(n)	Lineare	Il tempo cresce proporzionalmente all'input (es: ricerca sequenziale).
O(n log n)	Pseudo-lineare	Ottimo compromesso per l'ordinamento (es: Merge Sort).
O(n²)	Quadratica	Efficienza ridotta, comune nei cicli annidati (es: Bubble Sort).
O(2ⁿ)	Esponenziale	Pessima efficienza, tempi proibitivi per n grandi.

💡 Consiglio per lo studio: Quando analizzi un algoritmo, cerca di capire in quale riga della tabella si posiziona. Passare da O(n²) a O(n log n) può fare la differenza tra un programma che gira in ore e uno che gira in millisecondi!

Analisi Pratica: Calcolare la Complessità nel Codice

Determinare la complessità asintotica di un frammento di codice non richiede calcoli infinitesimali, ma la capacità di identificare i "colli di bottiglia" strutturali. La regola aurea è il Principio del Termine Dominante: in una sequenza di operazioni, la complessità totale è data dall'operazione più lenta, poiché al crescere di n le altre diventano trascurabili.

1. Istruzioni Atomiche (Costo Costante)

Tutte le operazioni che non dipendono dalla dimensione dell'input hanno costo O(1). Questo include assegnamenti (x = 10), operazioni aritmetiche elementari (+, -, *, /), accesso a una cella di un array tramite indice e valutazione di condizioni booleane.

2. Regola della Somma (Sequenze)

Per istruzioni eseguite una dopo l'altra, si sommano i costi: O(f(n)) + O(g(n)) = O(max(f(n), g(n))).
Esempio: Un ciclo O(n) seguito da un ciclo O(n²) produce una complessità complessiva O(n²).

3. Regola del Prodotto (Iterazioni e Cicli)

Se un'istruzione viene ripetuta all'interno di un ciclo, il costo è il prodotto tra il numero di iterazioni e il costo del corpo del ciclo.

Ciclo Singolo: Un ciclo che va da 1 a n con operazioni O(1) all'interno ha costo O(n).
Cicli Annidati: Se un ciclo da 1 a n contiene un altro ciclo da 1 a n, il costo diventa n × n = O(n²). Se i cicli sono tre, avremo O(n³).

4. Logaritmi (Dimezzamento)

Se la variabile di controllo del ciclo viene raddoppiata o dimezzata a ogni iterazione (es. for(i=1; i<n; i*=2)), il ciclo verrà eseguito log&sub2;(n) volte. La complessità risultante è O(log n).

Caso Studio: Ricerca Lineare vs Ricerca Binaria

Supponiamo di cercare un nome in un elenco telefonico di n contatti:

Strategia	Analisi Algoritmica	Complessità
Ricerca Lineare	Controlli ogni nome partendo dall'inizio.	O(n)
Ricerca Binaria	Apri a metà, scarti la metà errata (richiede elenco ordinato).	O(log n)

L'impatto reale: Se raddoppi l'elenco (2n), la ricerca lineare raddoppia il tempo. La ricerca binaria richiede un solo confronto in più.

Attenzione alle Chiamate a Funzione:

Se all'interno di un ciclo chiami una funzione esterna, devi moltiplicare le iterazioni del ciclo per la complessità di quella funzione. Ad esempio, un ciclo n che chiama una funzione di ordinamento O(n log n) produce una complessità totale di O(n² log n).

Analisi Dettagliata del Codice: Bubble vs Selection Sort

In ambiente C++, l'efficienza di un algoritmo non si misura solo in termini di tempo teorico, ma nel numero di operazioni primitive eseguite sul processore. Analizziamo il costo di ogni singola riga di codice per capire come si arriva alla complessità quadratica O(n²).

1. Bubble Sort: Il costo dei confronti adiacenti

L'algoritmo "a bolle" sposta ripetutamente l'elemento più grande verso la fine dell'array tramite scambi continui.

            void bubbleSort(int arr[], int n) {

              for (int i = 0; i < n - 1; i++) { // [A] Costo: O(n)

                for (int j = 0; j < n - i - 1; j++) { // [B] Costo: O(n)

                  if (arr[j] > arr[j + 1]) { // [C] Confronto: O(1)

                    swap(arr[j], arr[j + 1]); // [D] Scambio: O(1)

                  }

                }

              }

            }

Analisi Computazionale:

Riga [A]: Il ciclo esterno viene eseguito (n-1) volte. Controlla quante "bolle" devono risalire.
Riga [B]: Il ciclo interno esegue i confronti. Ad ogni iterazione di i, il range di j diminuisce.
Riga [C]: Il confronto avviene n × (n-1) / 2 volte. Totale confronti: O(n²).
Riga [D]: Lo scambio (swap) è l'operazione più costosa. Nel caso peggiore (array rovesciato), viene eseguito ad ogni confronto. Tre assegnamenti per ogni swap: O(n²) assegnamenti.

2. Selection Sort: Ottimizzare il movimento dei dati

A differenza del Bubble Sort, il Selection Sort cerca il minimo e lo mette in posizione una sola volta per ogni ciclo esterno.

            void selectionSort(int arr[], int n) {

              for (int i = 0; i < n - 1; i++) { // [E] Costo: O(n)

                int min_idx = i; // [F] Assegnamento: O(1)

                for (int j = i + 1; j < n; j++) { // [G] Costo: O(n)

                  if (arr[j] < arr[min_idx]) // [H] Confronto: O(1)

                    min_idx = j; // [I] Solo aggiornamento indice

                }

                swap(arr[min_idx], arr[i]); // [L] Scambio fisico: O(1)

              }

            }

Perché è tecnicamente più efficiente del Bubble Sort?

Confronti [H]: Esattamente gli stessi del Bubble Sort, O(n²). La ricerca del minimo non può essere evitata.
Scambi [L]: Qui sta la magia. Lo swap avviene fuori dal ciclo interno. Viene eseguito esattamente n-1 volte.
Costo Totale Scambi: O(n). In C++, se l'array contenesse oggetti complessi o stringhe lunghe, il Selection Sort sarebbe molto più veloce perché sposta i dati il minimo indispensabile.

Operazione	Bubble Sort (Costo)	Selection Sort (Costo)	Vincitore
Confronti	O(n²)	O(n²)	Pareggio
Scambi (Swap)	O(n²)	O(n)	Selection Sort
Caso Ottimale	O(n) (con flag)	O(n²)	Bubble Sort

In sintesi: Se la memoria o la dimensione degli oggetti è un problema, il Selection Sort è superiore grazie al minor numero di scritture. Se l'array è quasi ordinato, un Bubble Sort con ottimizzazione (flag) termina molto prima.

Tecniche di Progettazione: Divide et Impera

La strategia del Divide et Impera (dal latino "dividi e conquista") è uno dei paradigmi più potenti per la risoluzione di problemi complessi. Il cuore della tecnica consiste nel trasformare un problema di dimensione n in sottoproblemi più piccoli, fino a raggiungere una dimensione tale da poter essere risolti direttamente (caso base).

Le Tre Fasi del Paradigma

1. Divide: Il problema originale viene spezzato in un numero a di sottoproblemi, ciascuno di dimensione n/b. In questa fase si cerca di minimizzare lo sforzo computazionale necessario per la scomposizione.

2. Impera (Conquista): Si risolvono i sottoproblemi in modo ricorsivo. Se la dimensione è sufficientemente piccola, si applica la soluzione diretta. La ricorsione "scende" nell'albero delle chiamate fino a toccare le foglie.

3. Combina: Le soluzioni parziali ottenute dai sottoproblemi vengono fuse per costruire la soluzione del problema originale. Questa fase è spesso la più critica per determinare la complessità finale dell'algoritmo.

Caso Studio: Merge Sort

Il Merge Sort è l'applicazione d'eccellenza di questo paradigma per l'ordinamento. A differenza del Bubble Sort (quadratico), il Merge Sort garantisce prestazioni ottime:

Divide: Trova il punto medio dell'array: costo O(1).
Impera: Ordina ricorsivamente le due metà.
Combina (Merge): Fonde le due metà ordinate in un unico array: costo O(n).

Analisi della Complessità:

L'equazione di ricorrenza del Merge Sort è: T(n) = 2T(n/2) + O(n).

Applicando il Teorema Master, otteniamo una complessità asintotica di O(n log n). Questo significa che per ordinare un milione di elementi, il Merge Sort esegue circa 20 milioni di operazioni, contro i mille miliardi (10¹²) necessari a un algoritmo quadratico.

Vantaggi e Svantaggi:

Oltre alla velocità, il Divide et Impera permette di sfruttare facilmente le architetture multi-core (i sottoproblemi possono essere risolti in parallelo). Tuttavia, richiede memoria extra per la gestione dello stack ricorsivo e, nel caso del Merge Sort, per l'array temporaneo di fusione.

Array e Liste Collegate

Una Struttura Dati è un modo sistematico di organizzare e memorizzare i dati per poterli utilizzare in modo efficiente. La scelta della struttura cambia la complessità delle operazioni.

Array (Vettori)

Elementi memorizzati in posizioni contigue.
• Vantaggio: Accesso diretto tramite indice in tempo O(1).
• Svantaggio: Dimensione fissa e inserimento/cancellazione costosi O(n).

Liste Collegate

Elementi sparsi in memoria collegati da puntatori.
• Vantaggio: Dimensione dinamica e inserimento veloce in testa O(1).
• Svantaggio: Per trovare un elemento bisogna scorrere tutta la lista O(n).

Pile e Code: Gestione degli Accessi

Queste strutture limitano il modo in cui i dati vengono inseriti ed estratti per scopi specifici:

Pila (Stack): Segue la logica LIFO (Last In, First Out). L'ultimo elemento inserito è il primo a uscire. Si usa per gestire la ricorsione e le chiamate a funzione.
Coda (Queue): Segue la logica FIFO (First In, First Out). Il primo che arriva è il primo a essere servito. Si usa nella gestione dei processi e delle code di stampa.

Strutture Gerarchiche: Alberi

Un Albero è una struttura dati dinamica e ricorsiva. A differenza delle strutture lineari (come gli array), l'albero organizza i dati in modo gerarchico, partendo da un unico nodo principale chiamato Radice. Ogni nodo può avere zero o più "nodi figli", ma ogni figlio ha esattamente un "nodo padre".

A

B

C

D

Esempio di Albero Binario: A è la radice, D è una foglia.

Proprietà e Complessità

Albero Binario di Ricerca (BST):

In un BST, l'organizzazione dei dati segue una regola ferrea: per ogni nodo X, tutti i nodi nel sottoalbero sinistro hanno chiavi < X, mentre quelli a destra hanno chiavi > X. Questa struttura permette di scartare metà dell'albero ad ogni passo della ricerca.

L'importanza dell'Altezza (h):

La complessità delle operazioni (ricerca, inserimento, cancellazione) dipende dall'altezza dell'albero.
• In un albero bilanciato, l'altezza è log&sub2;(n), garantendo prestazioni eccellenti O(log n).
• In un albero degenere (sbilanciato), l'altezza diventa n, trasformando l'albero in una lista e facendo crollare le prestazioni a O(n).

Curiosità Tecnica: Per mantenere gli alberi sempre efficienti, si utilizzano algoritmi di auto-bilanciamento come gli Alberi AVL o i Red-Black Trees, che eseguono "rotazioni" dei nodi durante l'inserimento per mantenere l'altezza minima possibile.

Strutture Reticolari: Grafi

Un Grafo è la struttura dati più generale possibile, composta da un insieme di nodi (Vertici) connessi da collegamenti (Archi). A differenza degli alberi, i grafi possono contenere cicli e non hanno necessariamente una gerarchia o una radice.

Un modo efficace per visualizzare un grafo non orientato semplice è disporre i vertici ai vertici di un poligono regolare. Nell'esempio sottostante, i tre nodi (V1, V2, V3) sono posizionati geometricamente per formare un triangolo equilatero perfetto, con gli archi che connettono i loro centri.

V1

V2

V3

Grafo triangolare equilatero realizzato in puro HTML/CSS.

Tipo di Grafo	Definizione	Applicazione Reale
Diretto (Orientato)	Gli archi hanno un verso (frecce).	Link tra pagine Web (HTML).
Non Diretto	Le connessioni sono bidirezionali.	Amicizie su Facebook.
Pesato	Ogni arco ha un costo o valore.	Distanze stradali in Google Maps.

Rappresentazione in Memoria:

I grafi vengono solitamente implementati tramite Matrici di Adiacenza (veloci per verificare archi esistenti, ma occupano O(n²)) o Liste di Adiacenza (efficienti per grafi sparsi, occupano O(n + m)).

Conclusione Operativa: La scelta della struttura dati definisce il limite superiore delle performance del software. Se il tuo problema prevede gerarchie fisse, l'Albero garantisce velocità e ordine; se devi modellare interconnessioni libere e complesse, il Grafo è l'unica scelta possibile.

Analisi Avanzata: Equazioni di Ricorrenza

L'analisi di un algoritmo ricorsivo richiede la formulazione di un'equazione di ricorrenza, un modello matematico che descrive il tempo di esecuzione totale T(n) come somma del tempo necessario per risolvere i sottoproblemi e del lavoro aggiuntivo richiesto dal paradigma Divide et Impera.

La Struttura della Ricorrenza

L'equazione standard si presenta nella forma: T(n) = aT(n/b) + f(n)

a: Rappresenta il numero di chiamate ricorsive. Determina quanto "largo" diventa l'albero della ricorsione.
n/b: Rappresenta la frazione dell'input passata a ogni chiamata. Determina quanto velocemente l'input si riduce verso il caso base.
f(n): Include il costo della fase di Divide (preparazione) e della fase di Combine (unione dei risultati).

Il Teorema Master: I Tre Casi

Il Teorema Master ci permette di determinare la complessità asintotica confrontando il lavoro svolto nelle chiamate ricorsive con il lavoro svolto dalla funzione f(n). Esistono tre scenari fondamentali:

Caso	Condizione Prevalente	Complessità Risultante
1. Ricorsivo-Dominante	Il numero di sottoproblemi cresce più velocemente della riduzione dell'input.	O(n^log_ba)
2. Bilanciato	Il lavoro delle chiamate e il lavoro di combinazione (f(n)) sono equivalenti.	O(n^log_ba log n)
3. Locale-Dominante	Il lavoro di combinazione (f(n)) è la parte più costosa dell'algoritmo.	O(f(n))

Esempio Pratico: Merge Sort

Nel Merge Sort abbiamo: T(n) = 2T(n/2) + n

a = 2, b = 2.
Calcoliamo n^log_ba: n^log₂2 = n¹ = n.
Poiché f(n) = n, siamo nel Caso 2 (Bilanciato).
La complessità è quindi O(n log n).

Oltre il Teorema Master: Non tutte le ricorrenze possono essere risolte con questo metodo (ad esempio se a non è costante o f(n) non è polinomiale). In quei casi si ricorre al Metodo dell'Esperto o al Metodo della Sostituzione, che prevede di ipotizzare una soluzione e verificarla per induzione matematica.

Ricerca Binaria: Analisi tra Ricorsione e Iterazione

La Ricerca Binaria è l'esempio classico di come il paradigma Decrease and Conquer possa ridurre drasticamente lo spazio di ricerca. A ogni passo, l'algoritmo scarta metà degli elementi, portando a una crescita temporale logaritmica.

1. Approccio Ricorsivo

        int binarySearchRecursive(int arr[], int low, int high, int x) {

          // Caso Base: intervallo esaurito

          if (low > high) return -1;

          // Calcolo sicuro del punto medio per evitare overflow

          int mid = low + (high - low) / 2;

          // Se l'elemento e nel mezzo, lo restituiamo

          if (arr[mid] == x) return mid;

          // Ricorsione di Coda (Tail Recursion): si sceglie un solo ramo

          if (arr[mid] > x)

            return binarySearchRecursive(arr, low, mid - 1, x);

          else

            return binarySearchRecursive(arr, mid + 1, high, x);

        }

2. Il Confronto: Ricorsione vs Iterazione

Sebbene entrambi gli approcci abbiano la stessa complessità temporale O(log n), differiscono significativamente nell'uso delle risorse hardware.

Caratteristica	Versione Ricorsiva	Versione Iterativa
Struttura di Controllo	Chiamate a funzione (Stack)	Ciclo While
Memoria Ausiliaria	O(log n) - Stack di sistema	O(1) - Variabili locali
Eleganza e Leggibilità	Alta, più vicina alla logica matematica	Media, più vicina alla macchina

Analisi dello Stack: Nella versione ricorsiva, ogni chiamata occupa un "frame" nello stack. Se l'altezza è log₂ n, avremo log₂ n record di attivazione attivi contemporaneamente.

La versione iterativa, invece, aggiorna semplicemente i valori di low e high all'interno dello stesso frame, risultando più efficiente in termini di memoria (O(1)). Tuttavia, molti compilatori moderni (C++/GCC) applicano la Tail Call Optimization, trasformando automaticamente la ricorsione di coda in un ciclo iterativo.

Conclusione: Scegli la ricorsione per favorire la manutenibilità e la chiarezza del codice (specialmente in contesti accademici o con compilatori ottimizzanti). Scegli l'iterazione in contesti critici per le performance o dove la memoria dello stack è estremamente limitata (sistemi embedded).

Implementazione e Analisi del Merge Sort

Il Merge Sort è un algoritmo di tipo out-of-place: richiede memoria aggiuntiva per la fusione, ma garantisce una stabilità e una complessità costante in ogni scenario (ottimo, medio, pessimo).

        // Funzione principale ricorsiva

        void mergeSort(int arr[], int l, int r) {

          if (l < r) { // Caso base: l'intervallo ha almeno 2 elementi

            // 1. Calcolo del centro (previene overflow rispetto a (l+r)/2)

            int m = l + (r - l) / 2;

            // 2. DISCESA RICORSIVA: Scomposizione dell'array

            mergeSort(arr, l, m);      // Chiamata sulla metà sinistra

            mergeSort(arr, m + 1, r); // Chiamata sulla metà destra

            // 3. RISALITA (COMBINE): Fusione dei risultati

            merge(arr, l, m, r); // Costo lineare O(n)

          }

        }

Analisi Dettagliata della Ricorsione

Il Record di Attivazione (Stack)

Ogni volta che mergeSort chiama se stessa, il processore salva lo stato corrente (indici l, m, r) nello Stack di sistema. Questo significa che la memoria utilizzata per la ricorsione è proporzionale all'altezza dell'albero: O(log n). Senza un caso base (l < r), lo stack si riempirebbe fino a causare un errore di Stack Overflow.

La Post-Order Traversal

La funzione merge viene eseguita solo dopo che le chiamate ricorsive sono tornate. Immagina l'albero: l'algoritmo scende fino alle "foglie" (singoli elementi) e inizia a ordinare e fondere risalendo verso la radice. È un approccio Bottom-Up guidato da una struttura Top-Down.

Perché "l + (r - l) / 2"?

In programmazione professionale, sommare due numeri grandi come (l + r) potrebbe superare il valore massimo consentito per un intero (Integer Overflow). La formula usata nel codice è matematicamente identica ma molto più sicura.

Confronto Reale:

Per ordinare 1.000.000 di elementi:

Un algoritmo O(n²) come il Bubble Sort compie circa 1.000.000.000.000 (mille miliardi) di operazioni.
Il Merge Sort compie circa 1.000.000 * 20 = 20.000.000 di operazioni.

La differenza è tra un'esecuzione di diverse ore e una di pochi millisecondi.

Fase	Descrizione Tecnica	Costo Computazionale
Divisione	Calcolo del punto medio e scomposizione logica.	O(1)
Ricorsione	Generazione di 2^h chiamate (dove h è l'altezza).	T(n/2) × 2
Fusione (Merge)	Confronto e copia degli elementi in array ausiliario.	O(n)

Il Disastro Esponenziale: Fibonacci Naive

L'implementazione ricorsiva "standard" della successione di Fibonacci è l'esempio scolastico di come la ridondanza possa distruggere le prestazioni. Il problema risiede nel fatto che l'algoritmo non ha memoria: ricalcola gli stessi valori migliaia di volte lungo rami diversi dell'albero delle chiamate.

        int fib(int n) {

          // 1. Caso Base: O(1)

          if (n <= 1) return n; 

          // 2. Doppia Ricorsione: Genera un albero binario

          return fib(n - 1) + fib(n - 2);

        }

Analisi dei Costi

Equazione di Ricorrenza: T(n) = T(n-1) + T(n-2) + O(1).
Branching Factor (a): 2. Ogni nodo non foglia genera esattamente due chiamate figlie.
Altezza dell'Albero: n. A differenza del Merge Sort, qui l'input si riduce solo di 1 o 2 unità per volta, rendendo l'albero profondissimo.
Complessità Finale: O(φⁿ) (dove φ ≈ 1.618 è la sezione aurea), semplificata comunemente in O(2ⁿ).

Perché è inefficiente?

Per calcolare fib(5), l'algoritmo calcola fib(3) due volte e fib(2) tre volte. Al crescere di n, questo spreco diventa insostenibile: per fib(50), il numero di chiamate supera i 20 miliardi, richiedendo tempi di calcolo proibitivi per un risultato che un semplice ciclo for otterrebbe in nanosecondi.

Soluzione Ottimale: Per correggere questo algoritmo si utilizza la Programmazione Dinamica (Memoization), salvando i risultati già calcolati in una tabella per evitare ricalcoli. Questo trasforma la complessità da esponenziale a lineare O(n).

Introduzione ad Algoritmi e Strutture Dati