Python - Analisi degli algoritmi

Analisi degli algoritmi

L'efficienza di un algoritmo può essere analizzata in due diverse fasi, prima e dopo l'implementazione. Sono i seguenti:

  • A Priori Analysis- Questa è un'analisi teorica di un algoritmo. L'efficienza di un algoritmo viene misurata assumendo che tutti gli altri fattori, ad esempio la velocità del processore, siano costanti e non abbiano alcun effetto sull'implementazione.

  • A Posterior Analysis- Questa è un'analisi empirica di un algoritmo. L'algoritmo selezionato viene implementato utilizzando il linguaggio di programmazione. Questo viene quindi eseguito sul computer di destinazione. In questa analisi vengono raccolte statistiche effettive come il tempo di esecuzione e lo spazio necessario.

Complessità algoritmo

Supponiamo X è un algoritmo e n è la dimensione dei dati di input, il tempo e lo spazio utilizzati dall'algoritmo X sono i due fattori principali che determinano l'efficienza di X.

  • Time Factor - Il tempo viene misurato contando il numero di operazioni chiave come i confronti nell'algoritmo di ordinamento.

  • Space Factor - Lo spazio viene misurato contando lo spazio di memoria massimo richiesto dall'algoritmo.

La complessità di un algoritmo f(n) fornisce il tempo di esecuzione e / o lo spazio di archiviazione richiesto dall'algoritmo in termini di n come la dimensione dei dati di input.

Complessità spaziale

La complessità dello spazio di un algoritmo rappresenta la quantità di spazio di memoria richiesta dall'algoritmo nel suo ciclo di vita. Lo spazio richiesto da un algoritmo è uguale alla somma delle seguenti due componenti:

  • Una parte fissa che è uno spazio necessario per memorizzare determinati dati e variabili, che sono indipendenti dalla dimensione del problema. Ad esempio, semplici variabili e costanti utilizzate, dimensione del programma, ecc.

  • Una parte variabile è uno spazio richiesto dalle variabili, la cui dimensione dipende dalla dimensione del problema. Ad esempio, allocazione dinamica della memoria, spazio dello stack di ricorsione, ecc.

La complessità spaziale S (P) di qualsiasi algoritmo P è S (P) = C + SP (I), dove C è la parte fissa e S (I) è la parte variabile dell'algoritmo, che dipende dalla caratteristica dell'istanza I. è un semplice esempio che cerca di spiegare il concetto -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Qui abbiamo tre variabili A, B e C e una costante. Quindi S (P) = 1 + 3. Ora, lo spazio dipende dai tipi di dati di date variabili e tipi di costanti e verrà moltiplicato di conseguenza.

Complessità temporale

La complessità temporale di un algoritmo rappresenta la quantità di tempo richiesta dall'algoritmo per essere eseguito fino al completamento. I requisiti di tempo possono essere definiti come una funzione numerica T (n), dove T (n) può essere misurato come numero di passi, a condizione che ogni passo consuma tempo costante.

Ad esempio, l'aggiunta di due interi a n bit richiede npassi. Di conseguenza, il tempo di calcolo totale è T (n) = c ∗ n, dove c è il tempo impiegato per la somma di due bit. Qui, osserviamo che T (n) cresce linearmente all'aumentare della dimensione dell'input.