Cos'è un algoritmo?
Un algoritmo è una procedura passo passo per risolvere un problema. Un buon algoritmo dovrebbe essere ottimizzato in termini di tempo e spazio. Diversi tipi di problemi richiedono diversi tipi di tecniche algoritmiche per essere risolti nel modo più ottimizzato. Esistono molti tipi di algoritmi, ma gli algoritmi più importanti e fondamentali necessari sono discussi in questo articolo.
conversione di una stringa in un numero intero
1. Algoritmo della forza bruta :
Questo è il tipo di algoritmo più elementare e semplice. Un algoritmo di forza bruta è l’approccio diretto a un problema, ovvero il primo approccio che ci viene in mente vedendo il problema. Più tecnicamente è come ripetere tutte le possibilità disponibili per risolvere quel problema.
Esempio:
Se è presente un blocco del PIN a 4 cifre. Scegli le cifre da 0 a 9, quindi la forza bruta proverà tutte le combinazioni possibili una per una come 0001, 0002, 0003, 0004 e così via finché non otterremo il PIN corretto. Nel peggiore dei casi, ci vorranno 10.000 tentativi per trovare la giusta combinazione.
2. Algoritmo ricorsivo :
Questo tipo di algoritmo è basato su ricorsione . Nella ricorsione, un problema viene risolto suddividendolo in sottoproblemi dello stesso tipo e richiamando ripetutamente il proprio self finché il problema non viene risolto con l'aiuto di una condizione di base.
Alcuni problemi comuni che vengono risolti utilizzando algoritmi ricorsivi sono Fattoriale di un numero , Serie di Fibonacci , Torre di Hanoi , DFS per grafico , eccetera.
UN) Algoritmo 'dividi e conquista'. :
Negli algoritmi Dividi e Impera, l'idea è di risolvere il problema in due sezioni, la prima sezione divide il problema in sottoproblemi dello stesso tipo. La seconda sezione consiste nel risolvere il problema più piccolo in modo indipendente e quindi aggiungere il risultato combinato per produrre la risposta finale al problema.
Alcuni problemi comuni che vengono risolti utilizzando gli algoritmi Divide and Conquers sono Ricerca binaria , Unisci ordinamento , Ordinamento rapido, Moltiplicazione di matrici di Strassen , eccetera.
B) Algoritmi di programmazione dinamica :
Questo tipo di algoritmo è noto anche come tecnica di memorizzazione perché in questo l'idea è di memorizzare il risultato calcolato in precedenza per evitare di calcolarlo ancora e ancora. Nella Programmazione Dinamica, dividi il problema complesso in problemi più piccoli sottoproblemi sovrapposti e memorizzare il risultato per un uso futuro.
I seguenti problemi possono essere risolti utilizzando l'algoritmo di Programmazione Dinamica Problema dello zaino , Pianificazione del lavoro ponderato , Algoritmo di Floyd Warshall , eccetera.
C) Algoritmo goloso :
Nell’algoritmo Greedy, la soluzione viene costruita parte per parte. La decisione di scegliere la parte successiva viene presa sulla base del fatto che offre un beneficio immediato. Non considera mai le scelte fatte in precedenza.
Alcuni problemi comuni che possono essere risolti tramite l'algoritmo Greedy sono Algoritmo del cammino minimo di Dijkstra , Algoritmo di Prim , Algoritmo di Kruskal , Codifica Huffman , eccetera.
D) Algoritmo di backtracking :
Nel Backtracking Algorithm, il problema viene risolto in modo incrementale, ovvero è una tecnica algoritmica per risolvere i problemi in modo ricorsivo cercando di costruire una soluzione in modo incrementale, un pezzo alla volta, rimuovendo quelle soluzioni che non riescono a soddisfare i vincoli del problema in ogni momento punto del tempo.
Alcuni problemi comuni che possono essere risolti tramite l'algoritmo di backtracking sono: Ciclo Hamiltoniano , Problema della colorazione M , Problema della Regina N , Problema del ratto nel labirinto , eccetera.
Numeri primi di programmazione Java
3. Algoritmo randomizzato :
Nell'algoritmo randomizzato, utilizziamo un numero casuale. Aiuta a decidere il risultato atteso. La decisione di scegliere il numero casuale dà quindi un vantaggio immediato
Alcuni problemi comuni che possono essere risolti tramite l'algoritmo randomizzato sono Quicksort: In Quicksort utilizziamo il numero casuale per selezionare il pivot.
4. Algoritmo di ordinamento :
L'algoritmo di ordinamento viene utilizzato per ordinare i dati in ordine ascendente o discendente. Viene utilizzato anche per organizzare i dati in modo efficiente e utile.
Alcuni problemi comuni che possono essere risolti tramite l'algoritmo di ordinamento sono l'ordinamento a bolle, l'ordinamento per inserimento, l'ordinamento per unione, l'ordinamento per selezione e l'ordinamento rapido sono esempi dell'algoritmo di ordinamento.
5. Algoritmo di ricerca :
L'algoritmo di ricerca è l'algoritmo utilizzato per cercare la chiave specifica in particolari dati ordinati o non ordinati. Alcuni problemi comuni che possono essere risolti tramite l'algoritmo di ricerca sono la ricerca binaria o la ricerca lineare è un esempio di algoritmo di ricerca.
6. Algoritmo di hashing :
Gli algoritmi di hashing funzionano allo stesso modo dell'algoritmo di ricerca ma contengono un indice con un ID chiave, ovvero una coppia chiave-valore. Nell'hashing, assegniamo una chiave a dati specifici.
Alcuni problemi comuni possono essere risolti tramite l'algoritmo di hashing nella verifica della password.