Complessità: problemi

Dato un problema P si possono individuare diversi algoritmi risolutivi A1, A2, … Aciascuno 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à 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 26

aa…a, aa…b, …, aa…z

zz…a, zz…b, …, zz…z

Sia c il tempo necessario per visualizzare una risposta allora il tempo necessario per visualizzare tutte le risposte è

T(n) = c·26>> c·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) = c·n! >> c·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)=c·n2, per scrivere i risultati in C
  • T2(n)=2·c·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

Cij = Ai·Bj = Ai1·B1j+Ai2·B2j+…+Ain·Bnj

richiede n moltiplicazioni per ogni prodotto scalare e quindi richiede

T3(n) = c·n·n2 = c·n

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)
c·n2 <= T(n) <= c·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).