La complessità algoritmica descrive come cambiano il tempo di esecuzione e il consumo di risorse di un algoritmo quando cresce la dimensione dell’input. Un programma che funziona rapidamente su cento elementi può diventare troppo lento quando deve elaborarne un milione, soprattutto se il numero di operazioni aumenta in modo quadratico o esponenziale rispetto alla dimensione dei dati.
Per valutare questo comportamento si utilizzano le notazioni asintotiche [math]O[/math], [math]\Omega[/math] e [math]\Theta[/math], che permettono di descrivere rispettivamente un limite superiore, un limite inferiore e un ordine di crescita preciso, a meno di costanti moltiplicative. Gli algoritmi ricorsivi richiedono spesso un ulteriore strumento di analisi, il Master Theorem, che consente di risolvere molte ricorrenze tipiche degli algoritmi basati sulla tecnica divide et impera.
Il test propone dieci esercizi a difficoltà crescente, dai confronti tra funzioni elementari fino alle ricorrenze per cui il teorema classico non è direttamente applicabile. Ogni soluzione comprende il ragionamento matematico, la spiegazione della risposta corretta e un commento sui passaggi che possono generare errori.
Riferimento rapido: le notazioni asintotiche
Prima di affrontare gli esercizi, conviene distinguere con precisione le tre notazioni fondamentali, perché una parte degli errori nasce dal confondere un limite superiore con una stima dell’ordine di crescita.
| Notazione | Significato | Interpretazione |
|---|---|---|
| [math]O(g(n))[/math] | Limite superiore asintotico | La funzione non cresce più rapidamente di [math]g(n)[/math], a meno di una costante moltiplicativa, per [math]n[/math] sufficientemente grande. |
| [math]\Omega(g(n))[/math] | Limite inferiore asintotico | La funzione cresce almeno quanto [math]g(n)[/math], a meno di una costante moltiplicativa, per [math]n[/math] sufficientemente grande. |
| [math]\Theta(g(n))[/math] | Limite superiore e inferiore dello stesso ordine | La funzione è compresa tra due multipli positivi di [math]g(n)[/math], per [math]n[/math] sufficientemente grande. |
In forma matematica, [math]f(n)=\Theta(g(n))[/math] se esistono costanti positive [math]c_1[/math], [math]c_2[/math] e [math]n_0[/math] tali che
[math]\displaystyle \begin{aligned} 0\leq c_1g(n)\leq f(n)\leq c_2g(n) \end{aligned}[/math]
per ogni [math]n\geq n_0[/math].
La distinzione è importante perché dimostrare che [math]f(n)=O(n^2)[/math] non significa necessariamente che [math]f(n)=\Theta(n^2)[/math]: per ottenere quest’ultima conclusione bisogna dimostrare anche un limite inferiore dello stesso ordine.
Il Master Theorem: formula e condizioni di applicabilità
Il Master Theorem permette di stimare la complessità di numerosi algoritmi ricorsivi, in particolare quelli basati sulla tecnica divide et impera.
La versione standard considera ricorrenze della forma
[math]\displaystyle \begin{aligned} T(n)=aT\left(\frac{n}{b}\right)+f(n), \end{aligned}[/math]
dove [math]a\geq1[/math] e [math]b>1[/math] sono costanti, [math]a[/math] rappresenta il numero di sottoproblemi e [math]n/b[/math] la dimensione di ciascun sottoproblema. La funzione [math]f(n)[/math] descrive il lavoro svolto al di fuori delle chiamate ricorsive, come la suddivisione del problema e la combinazione dei risultati.
Si assume un caso base con costo costante e si devono rispettare le condizioni richieste dalla versione del teorema utilizzata. Il confronto fondamentale riguarda [math]f(n)[/math] e la funzione
[math]\displaystyle \begin{aligned} n^{\log_b a}, \end{aligned}[/math]
che esprime il contributo associato alla struttura ricorsiva.
Primo caso: il lavoro esterno è asintoticamente inferiore.
Se esiste [math]\varepsilon>0[/math] tale che
[math]\displaystyle \begin{aligned} f(n)=O\left(n^{\log_b a-\varepsilon}\right), \end{aligned}[/math]
allora
[math]\displaystyle \begin{aligned} T(n)=\Theta\left(n^{\log_b a}\right). \end{aligned}[/math]
In questa situazione domina il costo generato dalla struttura ricorsiva, perché il lavoro aggiuntivo a ogni livello cresce più lentamente.
Secondo caso: i due contributi hanno lo stesso ordine.
Se
[math]\displaystyle \begin{aligned} f(n)=\Theta\left(n^{\log_b a}\log^k n\right),\qquad k\geq0, \end{aligned}[/math]
nella versione generalizzata del secondo caso si ottiene
[math]\displaystyle \begin{aligned} T(n)=\Theta\left(n^{\log_b a}\log^{k+1}n\right). \end{aligned}[/math]
Il fattore logaritmico aumenta di una potenza, perché il contributo dei livelli della ricorsione si accumula lungo la sua profondità.
Terzo caso: il lavoro esterno cresce più rapidamente.
Se esiste [math]\varepsilon>0[/math] tale che
[math]\displaystyle \begin{aligned} f(n)=\Omega\left(n^{\log_b a+\varepsilon}\right), \end{aligned}[/math]
e sono soddisfatte le condizioni di regolarità richieste, allora
[math]\displaystyle \begin{aligned} T(n)=\Theta(f(n)). \end{aligned}[/math]
In questo caso il lavoro svolto al di fuori delle chiamate ricorsive è il contributo dominante.
Queste formule non si applicano automaticamente a qualsiasi ricorrenza che contenga termini simili: il numero delle chiamate, le dimensioni dei sottoproblemi e il termine di costo devono rispettare le ipotesi del teorema. Quando i sottoproblemi hanno dimensioni differenti, oppure il costo esterno non rientra nei casi previsti, occorre utilizzare un metodo più generale, come il teorema di Akra–Bazzi, o svolgere un’analisi diretta.
Il test di autovalutazione
Per ciascun esercizio individua la risposta corretta prima di leggere la soluzione, prestando attenzione alle ipotesi della ricorrenza e alla differenza tra un limite superiore e un ordine asintotico preciso.
Quesito 1 — Confronto tra funzioni elementari
Qual è la complessità asintotica della funzione
[math]\displaystyle \begin{aligned} f(n)=7n^3+4n^2+15n+9? \end{aligned}[/math]
A. [math]\Theta(n^2)[/math]
B. [math]\Theta(n^3)[/math]
C. [math]\Theta(n^3\log n)[/math]
D. [math]\Theta(7^n)[/math]
Soluzione: risposta B, [math]\Theta(n^3)[/math].
Per [math]n[/math] sufficientemente grande, il termine [math]7n^3[/math] cresce più rapidamente di tutti gli altri termini del polinomio. Le costanti moltiplicative e i contributi di ordine inferiore non modificano l’ordine asintotico, per cui
[math]\displaystyle \begin{aligned} 7n^3+4n^2+15n+9=\Theta(n^3). \end{aligned}[/math]
La risposta A trascura il termine cubico, mentre la risposta C introduce un fattore logaritmico che non è presente nella funzione. La risposta D confonde la crescita polinomiale con quella esponenziale, che è molto più rapida.
Se il termine dominante fosse [math]7n^3\log n[/math], la complessità diventerebbe [math]\Theta(n^3\log n)[/math], perché il fattore logaritmico non potrebbe più essere eliminato come se fosse una costante.
Quesito 2 — Ricerca binaria e ricorrenze
La ricerca binaria opera su un array ordinato e, a ogni passo, elimina circa metà degli elementi ancora da esaminare. Assumendo un costo costante per ogni passo e un caso base di costo costante, quale complessità temporale si ottiene dalla ricorrenza
[math]\displaystyle \begin{aligned} T(n)=T\left(\frac n2\right)+\Theta(1)? \end{aligned}[/math]
A. [math]\Theta(1)[/math]
B. [math]\Theta(\log n)[/math]
C. [math]\Theta(n)[/math]
D. [math]\Theta(n\log n)[/math]
Soluzione: risposta B, [math]\Theta(\log n)[/math].
Dopo ogni passaggio la dimensione del problema si dimezza, quindi, dopo [math]k[/math] passaggi, la dimensione residua è approssimativamente [math]n/2^k[/math]. La ricerca termina quando questa dimensione diventa costante, condizione che si verifica quando
[math]\displaystyle \begin{aligned} \frac{n}{2^k}\approx1 \quad\Longrightarrow\quad k\approx\log_2 n. \end{aligned}[/math]
Poiché ogni passaggio ha costo costante, il costo complessivo è proporzionale al numero dei passaggi e pertanto [math]T(n)=\Theta(\log n)[/math].
Precisazione sulle ipotesi. Questa ricorrenza è un modello semplificato della ricerca binaria standard, non una descrizione completa di ogni possibile implementazione. Si assume che l’accesso all’elemento centrale, il confronto e le altre operazioni del singolo passo abbiano costo costante, come avviene normalmente con un array e un confronto elementare, e che il caso base abbia costo costante. Se il confronto richiede un tempo non costante oppure la struttura dati presenta costi di accesso differenti, la ricorrenza deve essere modificata per rappresentare il comportamento effettivo dell’algoritmo.
Se la dimensione del problema si riducesse di una sola unità a ogni passaggio, anziché dimezzarsi, la ricorrenza diventerebbe [math]T(n)=T(n-1)+\Theta(1)[/math], con complessità [math]\Theta(n)[/math].
Quesito 3 — Complessità di un algoritmo divide et impera
Considera la ricorrenza
[math]\displaystyle \begin{aligned} T(n)=2T\left(\frac n2\right)+n. \end{aligned}[/math]
Qual è il suo ordine asintotico?
A. [math]\Theta(n)[/math]
B. [math]\Theta(n\log n)[/math]
C. [math]\Theta(n^2)[/math]
D. [math]\Theta(\log n)[/math]
Soluzione: risposta B, [math]\Theta(n\log n)[/math].
La ricorrenza contiene due sottoproblemi di dimensione [math]n/2[/math] e un costo aggiuntivo lineare. Per il Master Theorem si ha [math]a=2[/math], [math]b=2[/math] e [math]f(n)=n[/math], mentre il contributo associato alla struttura ricorsiva è
[math]\displaystyle \begin{aligned} n^{\log_b a}=n^{\log_2 2}=n. \end{aligned}[/math]
Il costo esterno e il contributo ricorsivo hanno quindi lo stesso ordine, per cui si applica il secondo caso del teorema:
[math]\displaystyle \begin{aligned} T(n)=\Theta(n\log n). \end{aligned}[/math]
Un’interpretazione equivalente si ottiene osservando l’albero della ricorsione: a ogni livello il costo complessivo è dell’ordine di [math]n[/math], mentre il numero dei livelli è dell’ordine di [math]\log n[/math]. Moltiplicando questi contributi si ricava [math]n\log n[/math].
Quesito 4 — Un fattore logaritmico nella ricorrenza
Considera la ricorrenza
[math]\displaystyle \begin{aligned} T(n)=2T\left(\frac n2\right)+n\log n. \end{aligned}[/math]
Qual è la complessità asintotica?
A. [math]\Theta(n\log n)[/math]
B. [math]\Theta(n\log^2 n)[/math]
C. [math]\Theta(n^2)[/math]
D. [math]\Theta(\log^2 n)[/math]
Soluzione: risposta B, [math]\Theta(n\log^2 n)[/math].
In questa ricorrenza [math]a=2[/math], [math]b=2[/math] e il contributo della struttura ricorsiva è [math]n^{\log_2 2}=n[/math]. Il costo esterno è [math]f(n)=n\log n[/math], che corrisponde alla forma generalizzata del secondo caso del Master Theorem con [math]k=1[/math]:
[math]\displaystyle \begin{aligned} f(n)=\Theta(n\log^1 n). \end{aligned}[/math]
Applicando il teorema si ottiene
[math]\displaystyle \begin{aligned} T(n)=\Theta(n\log^{1+1}n)=\Theta(n\log^2 n). \end{aligned}[/math]
Il fattore logaritmico aggiuntivo deriva dall’accumulo del costo dei diversi livelli della ricorsione, ciascuno dei quali contribuisce in misura non trascurabile al totale.
Quesito 5 — Complessità di un ciclo annidato
Un algoritmo esegue due cicli annidati, ciascuno dei quali scorre [math]n[/math] elementi, e svolge un numero costante di operazioni all’interno del ciclo più interno. Qual è la complessità temporale?
A. [math]\Theta(n)[/math]
B. [math]\Theta(n\log n)[/math]
C. [math]\Theta(n^2)[/math]
D. [math]\Theta(2^n)[/math]
Soluzione: risposta C, [math]\Theta(n^2)[/math].
Il ciclo esterno viene eseguito [math]n[/math] volte e, per ogni sua iterazione, quello interno esegue a sua volta [math]n[/math] iterazioni. Il numero complessivo delle operazioni elementari è quindi proporzionale al prodotto [math]n\cdot n[/math], da cui
[math]\displaystyle \begin{aligned} T(n)=\Theta(n^2). \end{aligned}[/math]
La conclusione presuppone che entrambi i cicli effettuino effettivamente un numero di iterazioni proporzionale a [math]n[/math] e che il lavoro interno abbia costo costante. Un ciclo annidato non implica sempre una complessità quadratica: se il ciclo interno dimezza progressivamente una variabile, per esempio, il costo potrebbe essere [math]\Theta(n\log n)[/math].
Quesito 6 — Un costo esterno con fattore logaritmico
Considera la ricorrenza
[math]\displaystyle \begin{aligned} T(n)=2T\left(\frac n2\right)+n\log n. \end{aligned}[/math]
Quale ordine asintotico descrive correttamente la funzione?
A. [math]\Theta(n\log n)[/math]
B. [math]\Theta(n\log^2 n)[/math]
C. [math]\Theta(n^2)[/math]
D. [math]\Theta(n^3)[/math]
Soluzione: risposta B, [math]\Theta(n\log^2 n)[/math].
Il risultato coincide con quello del quesito 4, perché la ricorrenza è la stessa. Questo esercizio serve a verificare se il ragionamento è stato compreso, anziché memorizzare soltanto una risposta. Con [math]a=2[/math] e [math]b=2[/math], il termine critico è [math]n^{\log_2 2}=n[/math], mentre il costo esterno è [math]n\log n[/math]. La versione generalizzata del secondo caso del Master Theorem fornisce quindi
[math]\displaystyle \begin{aligned} T(n)=\Theta(n\log^2 n). \end{aligned}[/math]
L’analisi tramite albero della ricorsione conduce allo stesso risultato: al livello [math]j[/math] ci sono [math]2^j[/math] sottoproblemi di dimensione [math]n/2^j[/math]. Il costo complessivo del livello è proporzionale a
[math]\displaystyle \begin{aligned} 2^j\frac{n}{2^j}\log\left(\frac{n}{2^j}\right)=n(\log n-j\log2). \end{aligned}[/math]
Sommando i contributi lungo i [math]\Theta(\log n)[/math] livelli si ottiene una somma di termini che decrescono linearmente rispetto al livello, con risultato complessivo dell’ordine di [math]n\log^2n[/math].
Quesito 7 — Una funzione oscillante: [math]n^{\sin n}[/math]
Considera la funzione
[math]\displaystyle \begin{aligned} f(n)=n^{\sin n},\qquad n\in\mathbb N,\ n\geq1. \end{aligned}[/math]
Quale delle seguenti affermazioni è corretta?
A. [math]f(n)=\Theta(n)[/math]
B. [math]f(n)=\Theta(1)[/math]
C. [math]f(n)=\Theta(n\log n)[/math]
D. [math]f(n)\notin\Theta(n)[/math] e [math]f(n)\notin\Theta(1)[/math]
Soluzione: risposta D.
Poiché il seno assume valori compresi tra [math]-1[/math] e [math]1[/math], per [math]n\geq1[/math] si ha
[math]\displaystyle \begin{aligned} -1\leq\sin n\leq1, \end{aligned}[/math]
e, di conseguenza,
[math]\displaystyle \begin{aligned} \frac1n\leq n^{\sin n}\leq n. \end{aligned}[/math]
Questi limiti sono corretti, ma non bastano per stabilire che la funzione sia [math]\Theta(n)[/math] o [math]\Theta(1)[/math]. Per capire il comportamento asintotico occorre considerare le oscillazioni del seno lungo sottosuccessioni di interi.
Perché il seno si avvicina infinite volte a entrambi gli estremi?
La successione degli angoli [math]n[/math] considerati modulo [math]2\pi[/math] è densa sulla circonferenza, perché [math]1/(2\pi)[/math] è irrazionale. In termini intuitivi, i multipli interi dell’angolo di un radiante non rimangono confinati in una porzione della circonferenza, ma si avvicinano arbitrariamente a ogni angolo. Esistono quindi sottosuccessioni di interi lungo le quali [math]n\bmod 2\pi[/math] si avvicina a [math]\pi/2[/math] e altre lungo le quali si avvicina a [math]3\pi/2[/math]. Ne consegue che [math]\sin n[/math] si avvicina rispettivamente a [math]1[/math] e a [math]-1[/math], infinite volte.
Questa proprietà consente di escludere le prime due risposte.
- Non vale [math]f(n)=\Theta(n)[/math]. Lungo una sottosuccessione per cui [math]\sin n\to-1[/math], il rapporto tra la funzione e [math]n[/math] è[math]\displaystyle \begin{aligned} \frac{n^{\sin n}}n=n^{\sin n-1}\longrightarrow0. \end{aligned}[/math]Non può quindi esistere una costante positiva [math]c[/math] tale che [math]f(n)\geq cn[/math] per tutti gli interi sufficientemente grandi.
- Non vale [math]f(n)=\Theta(1)[/math]. Lungo una sottosuccessione per cui [math]\sin n\to1[/math], la funzione diventa arbitrariamente grande. In particolare, quando [math]\sin n>1/2[/math], si ha[math]\displaystyle \begin{aligned} f(n)=n^{\sin n}>\sqrt n. \end{aligned}[/math]Questa condizione si verifica infinite volte, quindi la funzione non è limitata superiormente da una costante.
La conclusione è che
[math]\displaystyle \begin{aligned} f(n)\notin\Theta(n),\qquad f(n)\notin\Theta(1). \end{aligned}[/math]
La funzione non è limitata superiormente da una costante, ma non è neppure limitata inferiormente da una costante positiva: lungo una sottosuccessione tende a valori arbitrariamente piccoli, mentre lungo un’altra assume valori arbitrariamente grandi.
Il caso mostra perché la notazione [math]\Theta[/math] richiede un controllo uniforme per tutti gli interi sufficientemente grandi. Non basta individuare un limite superiore o osservare che l’esponente oscilla: occorre verificare che esistano entrambi i limiti richiesti e che abbiano lo stesso ordine.
Quesito 8 — Una ricorrenza con costo quadratico
Considera la ricorrenza
[math]\displaystyle \begin{aligned} T(n)=T(n-1)+n,\qquad T(1)=1. \end{aligned}[/math]
Qual è la complessità asintotica?
A. [math]\Theta(n)[/math]
B. [math]\Theta(n\log n)[/math]
C. [math]\Theta(n^2)[/math]
D. [math]\Theta(2^n)[/math]
Soluzione: risposta C, [math]\Theta(n^2)[/math].
Sviluppando la ricorrenza si ottiene
[math]\displaystyle \begin{aligned} T(n)&=T(n-1)+n\\ &=T(n-2)+(n-1)+n\\ &=\cdots\\ &=1+2+3+\cdots+n. \end{aligned}[/math]
La somma dei primi [math]n[/math] interi positivi è
[math]\displaystyle \begin{aligned} T(n)=\frac{n(n+1)}2, \end{aligned}[/math]
e pertanto
[math]\displaystyle \begin{aligned} T(n)=\Theta(n^2). \end{aligned}[/math]
Il risultato si può comprendere anche osservando che la ricorrenza aggiunge un costo lineare a ogni passo, mentre il numero dei passi è proporzionale a [math]n[/math]. Il totale corrisponde quindi alla somma di una progressione aritmetica.
Quesito 9 — Una ricorrenza con un termine inversamente logaritmico
Considera la ricorrenza
[math]\displaystyle \begin{aligned} T(n)=3T\left(\frac n3\right)+\frac{n}{\log n}. \end{aligned}[/math]
Qual è l’ordine asintotico?
A. [math]\Theta(n)[/math]
B. [math]\Theta(n\log\log n)[/math]
C. [math]\Theta(n\log n)[/math]
D. [math]\Theta(n^2)[/math]
Soluzione: risposta B, [math]\Theta(n\log\log n)[/math].
Questa ricorrenza richiede attenzione, perché il termine [math]n/\log n[/math] non rientra direttamente nelle tre forme standard del Master Theorem presentate in precedenza. Si può ottenere il risultato analizzando l’albero della ricorsione.
Al livello [math]j[/math] ci sono [math]3^j[/math] sottoproblemi, ciascuno di dimensione approssimativa [math]n/3^j[/math]. Il costo complessivo del livello è quindi
[math]\displaystyle \begin{aligned} 3^j\frac{n/3^j}{\log(n/3^j)}=\frac{n}{\log n-j\log3}. \end{aligned}[/math]
La profondità dell’albero è dell’ordine di [math]\log_3 n[/math]. Sommando i costi dei livelli interni, il contributo complessivo è proporzionale a
[math]\displaystyle \begin{aligned} n\sum_{j=0}^{\Theta(\log n)}\frac{1}{\log n-j\log3}. \end{aligned}[/math]
Questa somma ha un comportamento armonico: dopo un opportuno cambio d’indice, la somma dei reciproci cresce come [math]\log\log n[/math]. Il contributo complessivo dei livelli è pertanto dell’ordine di [math]n\log\log n[/math], da cui
[math]\displaystyle \begin{aligned} T(n)=\Theta(n\log\log n). \end{aligned}[/math]
Il costo delle foglie è dell’ordine di [math]n[/math], quindi non modifica il risultato finale, che cresce più rapidamente di [math]n[/math].
Quesito 10 — Tre sottoproblemi e il teorema di Akra–Bazzi
Considera la ricorrenza
[math]\displaystyle \begin{aligned} T(n)=2T\left(\left\lfloor\frac n2\right\rfloor\right)+T\left(\left\lceil\frac n2\right\rceil\right)+n. \end{aligned}[/math]
Qual è la complessità asintotica?
A. [math]\Theta(n)[/math]
B. [math]\Theta(n\log n)[/math]
C. [math]\Theta(n^2)[/math]
D. [math]\Theta(n^{\log_2 3})[/math]
Soluzione: risposta D, [math]\Theta(n^{\log_2 3})[/math].
La ricorrenza contiene tre chiamate ricorsive: due riguardano sottoproblemi di dimensione [math]\lfloor n/2\rfloor[/math], mentre la terza riguarda un sottoproblema di dimensione [math]\lceil n/2\rceil[/math]. Il costo aggiuntivo è lineare.
Il Master Theorem classico non si applica direttamente nella sua forma standard, perché presuppone sottoproblemi di dimensione [math]n/b[/math], con lo stesso fattore di riduzione. Per risolvere la ricorrenza si può utilizzare il teorema di Akra–Bazzi, che estende l’analisi a ricorrenze con sottoproblemi di dimensioni differenti.
Nella forma generale, l’esponente [math]p[/math] è determinato dall’equazione
[math]\displaystyle \begin{aligned} \sum_{i=1}^{k}a_i b_i^p=1, \end{aligned}[/math]
dove [math]a_i[/math] indica il numero di sottoproblemi del tipo [math]i[/math], mentre [math]b_i[/math] rappresenta il fattore che determina la loro dimensione relativa.
Trascurando per il momento gli arrotondamenti, la nostra ricorrenza conduce a
[math]\displaystyle \begin{aligned} 2\left(\frac12\right)^p+\left(\frac12\right)^p=1, \end{aligned}[/math]
da cui
[math]\displaystyle \begin{aligned} 3\cdot2^{-p}=1 \quad\Longrightarrow\quad 2^p=3 \quad\Longrightarrow\quad p=\log_2 3. \end{aligned}[/math]
Il teorema di Akra–Bazzi fornisce, nelle condizioni previste, una stima della forma
[math]\displaystyle \begin{aligned} T(n)=\Theta\left(n^p\left[1+\int_1^n\frac{g(u)}{u^{p+1}}\,du\right]\right), \end{aligned}[/math]
dove [math]g(u)[/math] è il costo esterno, che nel nostro caso vale [math]g(u)=u[/math]. L’integrale diventa
[math]\displaystyle \begin{aligned} \int_1^n u^{-p}\,du. \end{aligned}[/math]
Poiché [math]p=\log_2 3>1[/math], questo integrale resta limitato al crescere di [math]n[/math]. Il fattore tra parentesi è quindi dell’ordine di una costante e il risultato è
[math]\displaystyle \begin{aligned} T(n)=\Theta\left(n^{\log_2 3}\right). \end{aligned}[/math]
Perché floor e ceil non cambiano l’ordine? Gli arrotondamenti modificano le dimensioni dei sottoproblemi al massimo di un’unità rispetto a [math]n/2[/math]. Non cambiano il fattore di riduzione asintotico né l’equazione caratteristica che determina l’esponente [math]p[/math]; la ricorrenza mantiene quindi l’ordine [math]\Theta(n^{\log_2 3})[/math].
La distinzione tra Master Theorem e Akra–Bazzi non è soltanto formale: il primo è adatto a ricorrenze con sottoproblemi della stessa dimensione, mentre il secondo permette di trattare anche strutture ricorsive con dimensioni differenti. Prima di applicare un teorema conviene quindi verificare che le ipotesi corrispondano alla ricorrenza che si vuole risolvere.
Come interpretare il risultato del test
Il punteggio può aiutare a capire quali concetti meritano un ulteriore ripasso, ma non sostituisce la revisione dei passaggi matematici, soprattutto negli esercizi sulle funzioni oscillanti e sulle ricorrenze meno standard.
| Risposte corrette | Interpretazione |
|---|---|
| 0–4 | È utile riprendere le definizioni di [math]O[/math], [math]\Omega[/math] e [math]\Theta[/math], insieme alle regole fondamentali per confrontare le funzioni. |
| 5–7 | Le basi sono presenti, ma conviene esercitarsi sulle ricorrenze e sul confronto tra i contributi dei diversi livelli. |
| 8–9 | La comprensione è buona; rivedi soprattutto le ipotesi dei teoremi e i casi in cui il Master Theorem classico non è sufficiente. |
| 10 | Le risposte sono corrette; per consolidare il risultato, verifica di saper ricostruire autonomamente le dimostrazioni e motivare le ipotesi utilizzate. |
Gli errori da evitare quando si studia la complessità
Un errore frequente consiste nell’identificare la complessità con il tempo effettivo misurato su una singola macchina. La notazione asintotica descrive invece il comportamento della funzione di costo al crescere dell’input e non determina da sola i tempi assoluti, che dipendono anche dall’hardware, dall’implementazione e dalla distribuzione dei dati.
È altrettanto importante non confondere un limite superiore con una stima precisa: da [math]T(n)=O(n^2)[/math] non segue necessariamente che [math]T(n)=\Theta(n^2)[/math], perché il limite superiore potrebbe essere più ampio del necessario. Quando si utilizza il Master Theorem, inoltre, bisogna controllare che il numero e le dimensioni dei sottoproblemi rispettino le ipotesi della versione scelta, senza applicare automaticamente una formula a ogni ricorrenza.
Infine, le funzioni oscillanti mostrano che il comportamento medio o più intuitivo non è sufficiente per dimostrare un risultato asintotico. Per concludere che una funzione appartiene a [math]\Theta(g(n))[/math], occorre verificare che i limiti superiore e inferiore siano entrambi validi per tutti gli interi sufficientemente grandi, non soltanto lungo una parte della successione.
La complessità algoritmica diventa davvero utile quando le formule vengono accompagnate da un ragionamento esplicito sulle ipotesi, sul costo delle operazioni e sulla struttura del problema. In questo modo le notazioni asintotiche non restano un insieme di regole da memorizzare, ma diventano strumenti per confrontare algoritmi e valutare le conseguenze della crescita dei dati.
📚 Per approfondire: Notazione Big O, analisi degli algoritmi e complessità computazionale
Per consolidare lo studio della complessità algoritmica, puoi proseguire con questi approfondimenti di Matematica Oltre, dedicati alle notazioni asintotiche, all’efficienza degli algoritmi e ai principi fondamentali dell’informatica.
- 👉 Confronti asintotici e notazione Big O: 6 esercizi svolti
Esercizi commentati per confrontare funzioni, riconoscere i termini dominanti e distinguere O, Ω e Θ.
- 👉 Simboli di Landau: la guida pratica a O-grande, Omega e Theta
Una guida per comprendere le notazioni asintotiche e il loro ruolo nella valutazione dell’efficienza degli algoritmi.
- 👉 Cos’è un algoritmo
Le caratteristiche fondamentali degli algoritmi, il modello di costo e i concetti di complessità temporale e spaziale.
(4)
Altri articoli nella categoria "Esercizi di Analisi Matematica"
- Integrali con 1 ± cos x: formule, sostituzioni ed esercizi svolti
- Studio di Funzione: Come Riconoscere Simmetrie, Funzioni Pari e Dispari (Guida con Esercizi)
- Ottimizzazione con vincoli: Lagrangiana e condizioni di Kuhn-Tucker
- Integrali che valgono π: formule, dimostrazioni ed esempi applicativi
- Successioni Ricorsive Fratte: Come Risolverle con il Metodo dei Reciproci ed Esercizi Svolti
- Teorema della permanenza del segno: 6 esercizi svolti con soluzioni e intorni espliciti
- Teorema del confronto con esercizi svolti: come calcolare i limiti con funzioni oscillanti
- Limiti notevoli: formulario completo con formule ed esercizi svolti
- Funzioni Iniettive: Guida con 6 Esercizi Svolti e Metodi di Risoluzione
- Successioni numeriche: 6 esercizi svolti con soluzioni e limiti