Strutture dati - Nozioni di base sugli algoritmi

L'algoritmo è una procedura passo passo, che definisce un insieme di istruzioni da eseguire in un certo ordine per ottenere l'output 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.

• Insert - Algoritmo per inserire l'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 chiamate algoritmo. Un algoritmo dovrebbe avere le seguenti caratteristiche:

• Unambiguous- L'algoritmo dovrebbe essere chiaro e non ambiguo. Ciascuno dei suoi passaggi (o fasi) e i loro input / output dovrebbero essere chiari e 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.

• Finiteness - Gli algoritmi devono terminare dopo un numero finito di passaggi.

• Feasibility - Dovrebbe essere fattibile con le risorse disponibili.

• Independent - Un algoritmo dovrebbe avere istruzioni passo passo, che dovrebbero essere indipendenti da qualsiasi codice di programmazione.

Come scrivere un algoritmo?

Non esistono standard ben definiti per la scrittura di algoritmi. Piuttosto, dipende dal problema e dalle risorse. Gli algoritmi non vengono mai scritti per supportare un particolare codice di programmazione.

Come sappiamo, tutti i linguaggi di programmazione condividono costrutti di codice di base come loop (do, for, while), controllo del flusso (if-else), ecc. Questi costrutti comuni possono essere usati per scrivere un algoritmo.

Scriviamo algoritmi in modo graduale, ma non è sempre così. 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 a imparare la scrittura di algoritmi utilizzando un esempio.

Problem - Progettare un algoritmo per aggiungere due numeri e visualizzare il risultato.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Gli algoritmi dicono ai programmatori come codificare il programma. In alternativa, l'algoritmo può essere scritto come:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Nella progettazione e nell'analisi degli algoritmi, di solito il secondo metodo viene utilizzato per descrivere un algoritmo. Rende facile per l'analista analizzare l'algoritmo ignorando tutte le definizioni indesiderate. Può osservare quali operazioni vengono utilizzate e come scorre il processo.

Scrittura step numbers, è facoltativo.

Progettiamo un algoritmo per ottenere una soluzione di un dato problema. Un problema può essere risolto in più modi.

Quindi, molti algoritmi di soluzione possono essere derivati ​​per un dato problema. Il passo successivo è analizzare gli algoritmi di soluzione proposta e implementare la soluzione più adatta.

Analisi dell'algoritmo

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.

Impareremo a conoscere l' analisi dell'algoritmo a priori . L'analisi degli algoritmi 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à 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, 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 determinate variabili e dai 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 consumi 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.