Complessità dei problemi
Dato un problema P si possono individuare diversi algoritmi risolutivi
ciascuno con la sua complessità
Sia C* la complessità più bassa. Se si dimostra che per il problema P non può esistere un algoritmo con complessità minore di C* allora si può affermare che il problema P ha complessità C*.
Problema 1
Le possibili sequenze di lunghezza n costruite con un alfabeto di 26 caratteri sono 26n : aa…a, aa…b, aa…c, …, zz…z.
Se consideriamo il tempo necessario per visualizzare le risposte e tralasciamo qualsiasi altra operazione otteniamo T(n)= 26n >> 2n. Il problema ha complessità almeno esponenziale O(2n).
Problema 2
Consideriamo le permutazioni di n elementi qualsiasi
| Permutazioni | Numero | |
|---|---|---|
| 1 | a | 1 |
| 2 | ab, ba | 2 |
| 3 | abc, acb, bac, bca, cab, cba | 6 |
| 4 | abcd, abdc, acbd, acdb, bacd, badc, bcad, bcda cabd, cadb, cbad, cbda, dabc, dacb, dbac, dbca |
24 |
| 5 | … | 120 |
| … | … | … |
| n | … | n! |
Come prima si ottiene T(n)=n! >> 2n e quindi il problema ha complessità almeno esponenziale O(2n).
Problema 3
Nel prodotto tra matrici di dimensioni nxn, C=AxB, è richiesto almeno il tempo
- T1(n)=n2, per scrivere i risultati in C
- T2(n)=2*n2, per leggere i dati in A e B
Non può esistere un algoritmo con complessità inferiore a quella necessaria per esaminare l’input oppure per generare l’output e quindi si parte comunque da una complessità quadratica.
L’algoritmo tradizionale che calcola il singolo elemento Cij tramite il prodotto scalare
richiede n moltiplicazioni per ogni prodotto scalare e quindi richiede T3(n) = n*n2 = n3 per calcolare tutti i prodotti.
Questo algoritmo potrebbe non essere il migliore (…) ma ci permette di stabilire un limite superiore per la complessità del problema.
In conclusione
n2 <= T(n) <= n3
Il problema del prodotto matriciale ha una complessità compresa tra O(n2) e O(n3).
Problema 4
Per il problema dell’ordinamento esistono molti algoritmi con complessità diverse
| O(n2) | Ingenui | selection sort, bubble sort, shaker sort, insertion sort |
| O(n~1.2) | Intermedi | shell sort |
| O(nlogn) | Evoluti | merge sort, quick sort, heap sort |
Si può dimostrare che non possono esistere algoritmi con complessità più bassa di O(n log n), quindi il problema dell’ordinamento ha complessità O(n log n).