Kas yra Algoritmas?
Algoritmas yra žingsnis po žingsnio procedūra, skirta problemai išspręsti. Geras algoritmas turėtų būti optimizuotas laiko ir erdvės atžvilgiu. Įvairių tipų problemos reikalauja skirtingų algoritminių metodų, kad būtų išspręstos optimaliausiu būdu. Yra daugybė algoritmų tipų, tačiau šiame straipsnyje aptariami svarbiausi ir pagrindiniai algoritmai, kuriuos turite atlikti.
1. Brute Force algoritmas :
Tai pats paprasčiausias ir paprasčiausias algoritmo tipas. Brute Force Algorithm yra paprastas požiūris į problemą, t. y. pirmasis požiūris, kuris ateina į galvą pamačius problemą. Techniškai tai lyg ir kartojamos visos galimybės išspręsti šią problemą.
Pavyzdys:
Jei yra 4 skaitmenų PIN kodo užraktas. Skaičius, kuriuos reikia pasirinkti nuo 0 iki 9, tada grubi jėga išbandys visas įmanomas kombinacijas po vieną, pvz., 0001, 0002, 0003, 0004 ir taip toliau, kol gausime tinkamą PIN kodą. Blogiausiu atveju, norint rasti tinkamą derinį, prireiks 10 000 bandymų.
2. Rekursyvinis algoritmas :
Šio tipo algoritmas pagrįstas rekursija . Rekursijos metu problema sprendžiama ją suskaidant į to paties tipo subproblemas ir vėl ir vėl vadinant savuoju, kol problema išsprendžiama bazinės sąlygos pagalba.
Kai kurios bendros problemos, kurios išsprendžiamos naudojant rekursinius algoritmus, yra Skaičiaus faktorius , Fibonačio serija , Hanojaus bokštas , DFS grafui ir kt.
a) Skaldyk ir užkariauk algoritmas :
„Skaldyk ir užkariauk“ algoritmuose idėja yra išspręsti problemą dviem skyriais, pirmoji dalis padalina problemą į to paties tipo subproblemas. Antrasis skyrius skirtas savarankiškai išspręsti mažesnę problemą ir pridėti bendrą rezultatą, kad gautumėte galutinį problemos atsakymą.
Yra keletas bendrų problemų, kurios išsprendžiamos naudojant „Skaldyk ir užkariauja“ algoritmus Dvejetainė paieška , Sujungti Rūšiuoti , Greitas rūšiavimas, Strasseno matricos daugyba ir kt.
b) Dinaminio programavimo algoritmai :
Šio tipo algoritmas taip pat žinomas kaip atmintinės technika nes čia siekiama išsaugoti anksčiau apskaičiuotą rezultatą, kad jo nereikėtų skaičiuoti vėl ir vėl. Dinaminiame programavime padalinkite sudėtingą problemą į mažesnes persidengiančios subproblemos ir išsaugokite rezultatą ateityje.
Šios problemos gali būti išspręstos naudojant dinaminio programavimo algoritmą Kuprinės problema , Svertinis darbų planavimas , Floydo Warshall algoritmas ir kt.
c) Godus algoritmas :
Greedy Algorithm sprendimas kuriamas dalis po dalies. Sprendimas pasirinkti kitą dalį priimamas remiantis tuo, kad ji duoda tiesioginės naudos. Ji niekada neatsižvelgia į pasirinkimus, kurie buvo priimti anksčiau.
Yra keletas bendrų problemų, kurias galima išspręsti naudojant „Gedy“ algoritmą Dijkstra trumpiausio kelio algoritmas , Primo algoritmas , Kruskal algoritmas , Huffmano kodavimas ir kt.
d) Atgalinis algoritmas :
Programoje „Backtracking Algorithm“ problema sprendžiama laipsniškai, t. y. tai algoritminis metodas, skirtas problemų sprendimui rekursyviai, bandant sukurti sprendimą laipsniškai, po vieną, pašalinant tuos sprendimus, kurie bet kuriuo metu nepatenkina problemos suvaržymų. laiko taškas.
Kai kurios bendros problemos, kurias galima išspręsti naudojant „Backtracking“ algoritmą, yra šios Hamiltono ciklas , M spalvinimo problema , N Karalienės problema , Žiurkė labirinto problema ir kt.
3. Atsitiktinis algoritmas :
Atsitiktinių imčių algoritme naudojame atsitiktinį skaičių.jis padeda nuspręsti laukiamą rezultatą. Sprendimas pasirinkti atsitiktinį skaičių, kad tai būtų tiesioginė nauda
Kai kurios įprastos problemos, kurias galima išspręsti naudojant atsitiktinių imčių algoritmą, yra greitasis rūšiavimas: „Quicksort“ mes naudojame atsitiktinį skaičių, kad pasirinktume sukimąsi.
4. Rūšiavimo algoritmas :
Rūšiavimo algoritmas naudojamas duomenims rūšiuoti didėjimo arba mažėjimo tvarka. Jis taip pat naudojamas duomenims tvarkyti efektyviai ir naudingai.
Kai kurios bendros problemos, kurias galima išspręsti naudojant rūšiavimo algoritmą, yra burbulų rūšiavimas, įterpimo rūšiavimas, sujungimo rūšiavimas, pasirinkimo rūšiavimas ir greitas rūšiavimas yra rūšiavimo algoritmo pavyzdžiai.
5. Paieškos algoritmas :
Paieškos algoritmas yra algoritmas, naudojamas ieškant konkretaus rakto tam tikruose surūšiuotuose arba nerūšiuotuose duomenyse. Kai kurios bendros problemos, kurias galima išspręsti naudojant paieškos algoritmą, yra dvejetainė paieška arba linijinė paieška yra vienas paieškos algoritmo pavyzdžių.
6. Maišos algoritmas :
Maišos algoritmai veikia taip pat, kaip ir paieškos algoritmas, tačiau juose yra indeksas su rakto ID, t. y. rakto ir reikšmių pora. Taikant maišą, konkretiems duomenims priskiriame raktą.
Kai kurias įprastas problemas galima išspręsti naudojant maišos algoritmą tikrinant slaptažodį.