Quando si scrive un algoritmo, è molto importante valutarne il costo. La complessità computazionale di un algoritmo può essere valutata secondo due tipi di costo:
L’obiettivo è quello di ottenere i migliori risultati possibili da un algoritmo per un dato problema. La teoria della complessità computazionale ci offre (tra le altre cose) gli strumenti formali; per determinare la complessità intrinseca di un problema, cioè il limite al di sotto del quale non è possibile andare (lower bound del problema).
Un algoritmo ottimale sarà perciò un numero finito di istruzioni che ha esattamente quella complessità, cioè, il cui costo coincide con il lower bound del problema.
Complessità Temporale (complessità computazionale)
Indichiamo la complessità temporale con il simbolo:
Il termine n indica la dimensione dell’input che viene passata al nostro algoritmo. Siamo infatti interessati al comportamento del nostro algoritmo al variare di n, solitamente prendiamo di esempio un n molto grande. La complessità temporale analizza il tempo impiegato da un algoritmo per risolvere un dato problema. E’ importante inoltre calcolare il costo di un algoritmo in base alla peggiore istanza di input, di dimensione n.
Complessità Spaziale (complessità computazionale)
Indichiamo la complessità spaziale con il simbolo:
E’ molto importante valutare anche questo tipo di complessità del nostro algoritmo; perché ci aiuta a capire e a valutare quanto il nostro algoritmo impatti a livello di memoria. Anche in questo caso n sta ad indicare la dimensione dell’input che il nostro algoritmo dovrà elaborare.
Notazioni Asintotiche
Diciamo anche che f(n) è dominata asintoticamente da g(n). Si dice anche che f(n) è O(g(n)). Siamo interessati come avevo detto prima a cosa succede per n grande, tecnicamente a partire da un certo n segnato; disinteressandoci di fattori costanti arbitrari (sia >1 o anche <1).
Esempio:
Anche per questo articolo è tutto, se vuoi conoscere meglio questo argomento ti rimando a questo link. Spero di esserti stato di aiuto; questa guida non vuole essere di grande rilevanza, ma solo un cenno alla materia.
Ricorda che sul nostro sito trovi il corso per imparare a programmare in Python e tante altre informazioni utili sulla programmazione e tecnologia. Non dimenticare di condividere il post se ti è piaciuto e di lasciare un commento se hai trovato difficoltà.
HAPPY CODING!!