Mikä on algoritmi?

Algoritmi on vaiheittainen menettely ongelman ratkaisemiseksi. Hyvä algoritmi tulisi optimoida ajan ja tilan suhteen. Erityyppiset ongelmat vaativat erityyppisiä algoritmitekniikoita, jotka ratkaistaan ​​mahdollisimman optimoidulla tavalla. Algoritmeja on monen tyyppisiä, mutta tärkeimmät ja perusalgoritmit, jotka sinun täytyy käsitellä, käsitellään tässä artikkelissa.

1. Brute Force -algoritmi :

Tämä on yksinkertaisin ja yksinkertaisin algoritmityyppi. Brute Force Algorithm on suoraviivainen lähestymistapa ongelmaan, eli ensimmäinen lähestymistapa, joka tulee mieleemme ongelman nähdessämme. Teknisemmin se on aivan kuin toistaisi kaikki mahdolliset mahdollisuudet tämän ongelman ratkaisemiseksi.

Esimerkki:

Jos 4-numeroinen PIN-koodi on lukittu. Numerot valitaan väliltä 0-9, sitten raaka voima yrittää kaikkia mahdollisia yhdistelmiä yksitellen, kuten 0001, 0002, 0003, 0004 ja niin edelleen, kunnes saamme oikean PIN-koodin. Pahimmassa tapauksessa oikean yhdistelmän löytäminen kestää 10 000 yritystä.

2. Rekursiivinen algoritmi :

Tämän tyyppinen algoritmi perustuu rekursio . Rekursiossa ongelma ratkaistaan ​​jakamalla se samantyyppisiksi aliongelmiksi ja kutsumalla omaa itseään uudestaan ​​ja uudestaan, kunnes ongelma ratkeaa perusehdon avulla.
Joitakin yleisiä ongelmia, jotka ratkaistaan ​​rekursiivisilla algoritmeilla, ovat Lukujen tekijä , Fibonacci-sarja , Hanoin torni , DFS Graphille , jne.

a) hajota ja hallitse -algoritmi :

Divide and Conquer -algoritmeissa ajatuksena on ratkaista ongelma kahdessa osassa, joista ensimmäinen jakaa ongelman samantyyppisiin osaongelmiin. Toinen osa on ratkaista pienempi ongelma itsenäisesti ja sitten lisätä yhdistetty tulos tuottaaksesi lopullisen vastauksen ongelmaan.
Jotkut yleiset ongelmat, jotka ratkaistaan ​​Divide and Conquers -algoritmeilla, ovat Binäärihaku , Yhdistä lajittelu , nopea lajittelu, Strassenin matriisikertolasku , jne.

b) Dynaamiset ohjelmointialgoritmit :

Tämän tyyppinen algoritmi tunnetaan myös nimellä memoisointitekniikka koska tässä ajatuksena on tallentaa aiemmin laskettu tulos, jotta sitä ei tarvitse laskea uudestaan ​​​​ja uudestaan. Jaa monimutkainen ongelma dynaamisessa ohjelmoinnissa pienemmiksi päällekkäisiä aliongelmia ja säilytä tulos tulevaa käyttöä varten.
Seuraavat ongelmat voidaan ratkaista käyttämällä dynaamista ohjelmointialgoritmia Reppu ongelma , Painotettu työaikataulu , Floyd Warshall -algoritmi , jne.

c) Ahne algoritmi :

Greedy Algorithmissa ratkaisu rakennetaan osa kerrallaan. Päätös valita seuraava osa tehdään sillä perusteella, että siitä on välitöntä hyötyä. Se ei koskaan ota huomioon aiemmin tehtyjä valintoja.
Jotkut yleiset ongelmat, jotka voidaan ratkaista Greedy Algorithmin avulla, ovat Dijkstra lyhimmän polun algoritmi , Primin algoritmi , Kruskalin algoritmi , Huffman koodaus , jne.

d) Peruutusalgoritmi :

Backtracking Algorithmissa ongelma ratkaistaan ​​inkrementaalisesti eli se on algoritminen tekniikka ongelmien ratkaisemiseksi rekursiivisesti yrittämällä rakentaa ratkaisu asteittain, pala kerrallaan poistamalla ne ratkaisut, jotka eivät täytä ongelman rajoituksia missään vaiheessa. ajankohta.
Joitakin yleisiä ongelmia, jotka voidaan ratkaista Backtracking-algoritmin avulla, ovat Hamiltonin sykli , M-Coloring ongelma , N Queen -ongelma , Rotta sokkeloongelmassa , jne.

3. Satunnaistettu algoritmi :

Satunnaistetussa algoritmissa käytämme satunnaislukua.se auttaa päättämään odotetun tuloksen. Päätös valita satunnaisluku niin, että siitä on välitöntä hyötyä
Joitakin yleisiä ongelmia, jotka voidaan ratkaista satunnaistetun algoritmin avulla, ovat Quicksort: Quicksortissa käytämme satunnaislukua pivotin valinnassa.

4. Lajittelualgoritmi :

Lajittelualgoritmia käytetään tietojen lajitteluun ehkä nousevaan tai laskevaan järjestykseen. Sitä käytetään myös tietojen järjestämiseen tehokkaalla ja hyödyllisellä tavalla.
Joitakin yleisiä ongelmia, jotka voidaan ratkaista lajittelualgoritmin avulla, ovat Bubble lajittelu, lisäyslajittelu, yhdistämislajittelu, valintalajittelu ja pikalajittelu ovat esimerkkejä lajittelualgoritmista.

5. Hakualgoritmi :

Hakualgoritmi on algoritmi, jota käytetään tietyn avaimen etsimiseen tietystä lajitellusta tai lajittelemattomasta tiedosta. Joitakin yleisiä ongelmia, jotka voidaan ratkaista hakualgoritmin avulla, ovat binaarihaku tai lineaarinen haku on yksi esimerkki hakualgoritmista.

6. Hajautusalgoritmi :

Hashing-algoritmit toimivat samalla tavalla kuin hakualgoritmi, mutta ne sisältävät indeksin avaintunnuksella eli avain-arvo-parin. Hashingissa määritämme avaimen tietyille tiedoille.
Jotkin yleiset ongelmat voidaan ratkaista salasanan tarkistuksen tiivistysalgoritmin avulla.