Algoritmo è un passo-passo la procedura, che definisce un insieme di istruzioni da eseguire in un determinato ordine per ottenere il risultato desiderato. Gli algoritmi sono generalmente creati indipendentemente dai linguaggi sottostanti, cioè un algoritmo può essere implementato in più di un linguaggio di programmazione.,
Dal punto di vista della struttura dei dati, di seguito sono riportate alcune importanti categorie di algoritmi −
-
Search − Algoritmo per cercare un elemento in una struttura dati.
-
Sort − Algoritmo per ordinare gli elementi in un certo ordine.
-
Inserisci-Algoritmo per inserire un elemento in una struttura dati.
-
Update − Algoritmo per aggiornare un elemento esistente in una struttura dati.
-
Delete − Algoritmo per eliminare un elemento esistente da una struttura dati.
Caratteristiche di un algoritmo
Non tutte le procedure possono essere definite un algoritmo., Un algoritmo dovrebbe avere le seguenti caratteristiche −
-
Non ambiguo-L’algoritmo dovrebbe essere chiaro e non ambiguo. Ciascuno dei suoi passaggi (o fasi) e i loro input/output dovrebbero essere chiari e devono portare a un solo significato.
-
Input-Un algoritmo dovrebbe avere 0 o più input ben definiti.
-
Output-Un algoritmo dovrebbe avere 1 o più output ben definiti e dovrebbe corrispondere all’output desiderato.
-
Finitezza − Gli algoritmi devono terminare dopo un numero finito di passaggi.,
-
Fattibilità-Dovrebbe essere fattibile con le risorse disponibili.
-
Indipendente − Un algoritmo dovrebbe avere indicazioni passo-passo, che dovrebbero essere indipendenti da qualsiasi codice di programmazione.
Come scrivere un algoritmo?
Non esistono standard ben definiti per gli algoritmi di scrittura. Piuttosto, è dipendente da problemi e risorse. Gli algoritmi non vengono mai scritti per supportare un particolare codice di programmazione.
Come sappiamo che tutti i linguaggi di programmazione condividono costrutti di codice di base come loop (do, for, while), flow-control (if-else), ecc., Questi costrutti comuni possono essere usati per scrivere un algoritmo.
Scriviamo algoritmi in modo passo-passo, ma non è sempre il caso. La scrittura dell’algoritmo è un processo e viene eseguita dopo che il dominio del problema è ben definito. Cioè, dovremmo conoscere il dominio del problema, per il quale stiamo progettando una soluzione.
Esempio
Proviamo ad imparare la scrittura dell’algoritmo usando un esempio.
Problema-Progettare un algoritmo per aggiungere due numeri e visualizzare il risultato.
Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP
Gli algoritmi dicono ai programmatori come codificare il programma., In alternativa, l’algoritmo può essere scritto come –
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
Nella progettazione e analisi di algoritmi, di solito viene utilizzato il secondo metodo per descrivere un algoritmo. Lo rende facile per l’analista di analizzare l’algoritmo ignorando tutte le definizioni indesiderate. Può osservare quali operazioni vengono utilizzate e come scorre il processo.
La scrittura dei numeri di passo è facoltativa.
Progettiamo un algoritmo per ottenere una soluzione di un dato problema. Un problema può essere risolto in più di un modo.,
Quindi, molti algoritmi di soluzione possono essere derivati per un dato problema. Il prossimo passo è analizzare gli algoritmi di soluzione proposti e implementare la soluzione più adatta.
Analisi dell’algoritmo
L’efficienza di un algoritmo può essere analizzata in due diverse fasi, prima dell’implementazione e dopo l’implementazione. Sono i seguenti −
-
Analisi a priori-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.
-
Un’analisi posteriore − Questa è un’analisi empirica di un algoritmo. L’algoritmo selezionato viene implementato utilizzando il linguaggio di programmazione. Questo viene quindi eseguito sulla macchina del computer di destinazione. In questa analisi, vengono raccolte statistiche effettive come il tempo di esecuzione e lo spazio richiesto.
Impareremo l’analisi dell’algoritmo a priori., L’analisi dell’algoritmo si occupa dell’esecuzione o del tempo di esecuzione delle varie operazioni coinvolte. Il tempo di esecuzione di un’operazione può essere definito come il numero di istruzioni del computer eseguite per operazione.
Complessità dell’algoritmo
Supponiamo che X sia un algoritmo e n sia la dimensione dei dati di input, il tempo e lo spazio utilizzati dall’algoritmo X sono i due fattori principali, che decidono l’efficienza di X.
-
Fattore tempo: il tempo viene misurato contando il numero di operazioni chiave come i confronti nell’algoritmo di ordinamento.,
-
Fattore spazio-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 dimensione dei dati di input.
Complessità dello spazio
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 dei 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.,
Spazio complessità S(P) di un qualsiasi algoritmo di P S(P) = C + SP(I), dove C è la parte fissa e S(I) la parte variabile dell’algoritmo, che dipende istanza caratteristico I. Seguito è riportato un semplice esempio che tenta di spiegare il concetto −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
Qui ci sono tre variabili A, B, e C e una costante. Quindi S (P) = 1&più; 3. Ora, lo spazio dipende dai tipi di dati di determinate variabili e tipi costanti e verrà moltiplicato di conseguenza.,
Complessità temporale
La complessità temporale di un algoritmo rappresenta la quantità di tempo richiesta dall’algoritmo per l’esecuzione fino al completamento. I requisiti di tempo possono essere definiti come una funzione numerica T(n), dove T (n) può essere misurata come il numero di passi, a condizione che ogni passo consumi un tempo costante.
Ad esempio, l’aggiunta di due interi a n bit richiede n passaggi. Di conseguenza, il tempo computazionale totale è T (n) = c n n, dove c è il tempo impiegato per l’aggiunta di due bit. Qui, osserviamo che T (n) cresce linearmente all’aumentare della dimensione dell’input.,