Què és un algorisme?
Un algorisme és un procediment pas a pas per resoldre un problema. Un bon algorisme s'ha d'optimitzar en termes de temps i espai. Els diferents tipus de problemes requereixen diferents tipus de tècniques algorítmiques per resoldre de la manera més optimitzada. Hi ha molts tipus d'algoritmes, però en aquest article es comenten els algorismes més importants i fonamentals que heu de fer.
1. Algorisme de força bruta :
Aquest és el tipus d'algorisme més bàsic i més senzill. Un algorisme de força bruta és l'enfocament senzill d'un problema, és a dir, el primer enfocament que ens ve al cap en veure el problema. Més tècnicament, és com repetir totes les possibilitats disponibles per resoldre aquest problema.
Exemple:
Si hi ha un bloqueig de PIN de 4 dígits. Els dígits que es triaran del 0 al 9, la força bruta intentarà totes les combinacions possibles una per una com 0001, 0002, 0003, 0004, i així successivament fins que aconseguim el PIN correcte. En el pitjor dels casos, es necessitaran 10.000 intents per trobar la combinació adequada.
2. Algorisme recursiu :
Es basa en aquest tipus d'algorisme recursivitat . En recursivitat, un problema es resol dividint-lo en subproblemes del mateix tipus i cridant al propi jo una i altra vegada fins que el problema es resol amb l'ajuda d'una condició bàsica.
Alguns problemes comuns que es resolen amb algorismes recursius són Factorial d'un nombre , Sèrie de Fibonacci , Torre de Hanoi , DFS per a gràfic , etc.
a) Algoritme Divideix i Conquista :
En els algorismes Divide and Conquer, la idea és resoldre el problema en dues seccions, la primera secció divideix el problema en subproblemes del mateix tipus. La segona secció consisteix a resoldre el problema més petit de manera independent i després afegir el resultat combinat per produir la resposta final al problema.
Alguns dels problemes comuns que es resolen amb els algorismes Divide and Conquers són Cerca binària , Fusionar Ordenar , Ordenació ràpida, Multiplicació matricial de Strassen , etc.
b) Algorismes de programació dinàmica :
Aquest tipus d'algorisme també es coneix com a tècnica de memorització perquè en això la idea és emmagatzemar el resultat calculat prèviament per evitar calcular-lo una i altra vegada. A la programació dinàmica, divideix el problema complex en més petits subproblemes superposats i emmagatzemar el resultat per a un ús futur.
Els problemes següents es poden resoldre mitjançant l'algorisme de programació dinàmica Problema de la motxilla , Programació de treball ponderada , Algoritme de Floyd Warshall , etc.
c) Algoritme Greedy :
A l'algoritme Greedy, la solució es construeix part per part. La decisió d'escollir la següent part es fa sobre la base que dóna un benefici immediat. Mai té en compte les opcions que s'havien pres anteriorment.
Alguns problemes comuns que es poden resoldre mitjançant l'algoritme Greedy són Algoritme del camí més curt de Dijkstra , Algoritme de Prim , Algoritme de Kruskal , Codificació Huffman , etc.
d) Algoritme de retrocés :
A l'algoritme de retrocés, el problema es resol de manera incremental, és a dir, és una tècnica algorítmica per resoldre problemes de forma recursiva intentant construir una solució de manera incremental, una peça a la vegada, eliminant aquelles solucions que no satisfan les limitacions del problema en qualsevol moment. punt de temps.
Alguns problemes comuns que es poden resoldre mitjançant l'algoritme de retrocés són els Cicle Hamiltonià , Problema de coloració M , Problema N Queen , Problema de la rata al laberint , etc.
3. Algoritme aleatoritzat :
A l'algorisme aleatori, utilitzem un nombre aleatori. Ens ajuda a decidir el resultat esperat. La decisió de triar el nombre aleatori perquè doni el benefici immediat
Alguns problemes comuns que es poden resoldre mitjançant l'algorisme aleatori són Quicksort: A Quicksort fem servir el nombre aleatori per seleccionar el pivot.
4. Algorisme d'ordenació :
L'algorisme d'ordenació s'utilitza per ordenar les dades en ordre potser ascendent o descendent. També s'utilitza per organitzar dades d'una manera eficient i útil.
Alguns problemes comuns que es poden resoldre mitjançant l'algorisme d'ordenació són l'ordenació per bombolles, l'ordenació per inserció, l'ordenació per fusió, l'ordenació per selecció i l'ordenació ràpida són exemples de l'algorisme d'ordenació.
5. Algorisme de cerca :
L'algorisme de cerca és l'algoritme que s'utilitza per cercar la clau específica en dades ordenades o no ordenades. Alguns problemes comuns que es poden resoldre mitjançant l'algorisme de cerca són la cerca binària o la cerca lineal és un exemple d'algorisme de cerca.
6. Algoritme hashing :
Els algorismes hash funcionen igual que l'algorisme de cerca, però contenen un índex amb un ID de clau, és a dir, un parell clau-valor. En hash, assignem una clau a dades específiques.
Alguns problemes comuns es poden resoldre mitjançant l'algoritme hashing en la verificació de contrasenyes.