Problema della password
Le possibili sequenze di lunghezza n costruite con un alfabeto di 26 caratteri sono 26n (disposizioni con ripetizione).
Se si utilizzano lettere maiuscole e minuscole (26+26 = 52), se si utilizzano anche le cifre (26+26+10 = 62), …
Sia c il tempo necessario per calcolare (visualizzare, salvare, stampare) una parola allora il tempo necessario per tutte è
T(n) = c · kn >> 2n.
Il problema della generazione della password, con un alfabeto di k caratteri, ha complessità esponenziale O(kn).
Problema dell’anagramma
Consideriamo le permutazioni di n caratteri
| Numero di caratteri | Permutazioni | Numero di permutazioni | |
|---|---|---|---|
| 1 | {a} | a | 1 |
| 2 | {a, b} | ab, ba | 2 |
| 3 | {a, b, c} | abc, acb, bac, bca, cab, cba | 6 |
| 4 | {a, b, c, d} | abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba | 24 |
| 5 | … | 120 | |
| … | … | … | |
| n | … | n! |
Sia c il tempo necessario per calcolare (visualizzare, salvare, …) una parola allora il tempo necessario per tutte le parole è
T(n) = c · n! >> 2n
e quindi il problema ha complessità O(n!) che è più che esponenziale O(2n).