|
|
Un algoritmo si dice efficiente se la sua complessità è di ordine polinomiale , ovvero O(nc) con c costante positiva.
Un algoritmo è inefficiente se la sua complessità è di ordine superpolinominale.
Per superpolinominale si intende una funzione di ordine esponenziale O(cn) o maggiore.
Vediamo due esempi; si consideri il problema di ordinare un insieme di n interi.
Un banale algoritmo superpolinominale è il seguente:
genera tutte le possibile permutazioni dei valori da ordinare ( complessità =O(n!)) e verifica l’ ordinamento ( complessità =O(n)). La complessità complessiva è quindi O(n n!). Essendo una funzione fattoriale addirittura maggiore (inteso come ordine di grandezza) di una esponenziale, la complessità di questo algoritmo è classificabile come superpolinominale.
Tale algoritmo può essere descritto anche nel seguente modo: cerca il minimo tra gli n valori e ponilo in prima posizione; cerca il minimo tra gli n-1 valori e ponilo in 2° posizione; e cosi via.
La complessità di questo algoritmo sarà O(n2) e quindi classificabile come polinomiale.
Per risolvere un problema si cerca di scoprire algoritmi di complessità sempre più bassa. Fino a che punto questa ricerca può essere spinta? In altri termini, esiste una limitazione inferiore alla complessità, che dipende solo dal problema in esame, che stabilisca una soglia invalicabile alla complessità di ogni algoritmo?La risposta è si, si ottiene studiando la complessità del problema.
Se si dimostra che qualunque algoritmo per il nostro problema ha complessità omega(f(n)), si è stabilita una limitazione inferiore alla complessità del problema.
Analogamente se si dimostra che un particolare algoritmo ha complessità O(g(n)), si è stabilita una limitazione superiore alla complessità del problema.
Se f(n)=g(n) allora l’ algoritmo è detto ottimo, perché la sua complessità in ordine di grandezza risulta la migliore possibile.
Calcolare le limitazioni inferiori non è semplice, sono noti pochi modi generali di dimostrazione per limitazioni inferiori.
Vediamone tre molto semplici:
Dimensione dei dati: se un problema ha in ingresso n dati e richiede di esaminarli tutti, allora una limitazione inferiore della complessità è oemga(n)
Eventi contabili: se un problema richiede che un certo evento sia ripetuto almeno n volte, allora una limitazione inferiore della complessità è omega(n)
Oracolo: se un oracolo (o avversario) utilizzando una certa regola che l’ algoritmo non conosce e che vale solo per certi dati in ingresso “divina” ad ogni opportunità la situazione più sfavorevole e fa lavorare l’ algoritmo il più possibile, allora si può individuare una limitazione inferiore della complessità.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.