Python - Tipi di algoritmi

L'efficienza e l'accuratezza degli algoritmi devono essere analizzate per confrontarli e scegliere un algoritmo specifico per determinati scenari. Il processo di realizzazione di questa analisi è chiamato analisi asintotica. Si riferisce al calcolo del tempo di esecuzione di qualsiasi operazione in unità matematiche di calcolo. Ad esempio, il tempo di esecuzione di un'operazione viene calcolato come f (n) e può essere calcolato come g (n2) per un'altra operazione. Ciò significa che il tempo di esecuzione della prima operazione aumenterà linearmente con l'aumento di n e il tempo di esecuzione della seconda operazione aumenterà esponenzialmente all'aumentare di n. Allo stesso modo, il tempo di esecuzione di entrambe le operazioni sarà quasi lo stesso se n è significativamente piccolo.

Di solito, il tempo richiesto da un algoritmo rientra in tre tipi:

Caso migliore: tempo minimo richiesto per l'esecuzione del programma.
Caso medio: tempo medio necessario per l'esecuzione del programma.
Caso peggiore: tempo massimo richiesto per l'esecuzione del programma.

Notazioni asintotiche

Di seguito sono riportate le notazioni asintotiche comunemente utilizzate per calcolare la complessità del tempo di esecuzione di un algoritmo.

Ο Notazione
Notazione Ω
θ Notazione

Notazione Big Oh, Ο

La notazione Ο (n) è il modo formale per esprimere il limite superiore del tempo di esecuzione di un algoritmo. Misura la complessità temporale del caso peggiore o il tempo più lungo che un algoritmo può impiegare per completare.

Ad esempio, per una funzione f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

Notazione Omega, Ω

La notazione Ω (n) è il modo formale per esprimere il limite inferiore del tempo di esecuzione di un algoritmo. Misura la migliore complessità temporale del caso o la migliore quantità di tempo che un algoritmo può impiegare per completare.

Ad esempio, per una funzione f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Notazione Theta, θ

La notazione θ (n) è il modo formale per esprimere sia il limite inferiore che il limite superiore del tempo di esecuzione di un algoritmo. È rappresentato come segue:

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

Notazioni asintotiche comuni

Di seguito è riportato un elenco di alcune notazioni asintotiche comuni:

costante	-	Ο (1)
logaritmico	-	Ο (log n)
lineare	-	Ο (n)
n log n	-	Ο (n log n)
quadratico	-	Ο (n ² )
cubo	-	Ο (n ³ )
polinomio	-	n ^{Ο (1)}
esponenziale	-	2 ^{Ο (n)}