Complessità di un problema
Dato un problema P si possono individuare diversi algoritmi risolutivi
A1, A2, ... Aq
ciascuno con la sua complessità
C1, C2, ..., Cq.
Sia C* la complessità più bassa.
Se si dimostra che per il problema P non può esistere un algoritmo con complessità più bassa 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 [a...z] [a...z] ... [a...z] sono 26n.Soltanto per visualizzare le risposte sarà necessario il tempo
T(n)= 26n >> 2n.
Quindi il problema ha complessità almeno esponenziale
O(2n).
Problema 2
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 può dimostrare che
T(n)=n! >> 2n
e quindi il problema ha complessità almeno esponenziale
O(2n).
Problema 3
Nel prodotto tra matrici 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
L'algoritmo noto (...) che calcola il singolo elemento Cij tramite il prodotto scalare
Cij = Ai*Bj = Ai1*B1j+Ai2*B2j+...+Ain*Bnj
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,
T1(n) < T2(n) <= T(n) <= T3(n)
n2 <= T(n) <= n3
Un algoritmo ottimo per la moltiplicazione tra matrici avrà necessariamente una complessità compresa tra O(n2) e O(n3)...n2 <= T(n) <= n3
Problema 4
Per il problema dell'ordinamento esistono algoritmi con complessità- 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, heapsort.
Si può dimostrare che non possono esistere algoritmi con complessità più bassa di O(nlogn), quindi il problema dell'ordinamento ha complessità
O(nlogn).
