Algoritem je dobro definirana zaporedna računska tehnika, ki sprejme vrednost ali zbirko vrednosti kot vhod in proizvede izhod(e), potrebne za rešitev problema.

Lahko pa rečemo, da je algoritem točen, če in samo če se ustavi s pravilnim izhodom za vsak vhodni primerek.

POTREBA PO ALGORITMIH:

Algoritmi se uporabljajo za reševanje problemov ali avtomatizacijo nalog na sistematičen in učinkovit način. So nabor navodil ali pravil, ki vodijo računalnik ali programsko opremo pri izvajanju določene naloge ali reševanju težave.

tuple java

Obstaja več razlogov, zakaj uporabljamo algoritme:

Učinkovitost: algoritmi lahko hitro in natančno izvajajo naloge, zaradi česar so bistveno orodje za naloge, ki zahtevajo veliko izračunov ali obdelave podatkov. Doslednost: Algoritmi so ponovljivi in ​​dajejo dosledne rezultate vsakič, ko se izvedejo. To je pomembno pri delu z velikimi količinami podatkov ali zapletenimi procesi. Razširljivost: algoritme je mogoče povečati za obvladovanje velikih naborov podatkov ali kompleksnih težav, zaradi česar so uporabni za aplikacije, ki zahtevajo obdelavo velikih količin podatkov. Avtomatizacija: Algoritmi lahko avtomatizirajo ponavljajoče se naloge, s čimer zmanjšajo potrebo po človeškem posredovanju in sprostijo čas za druga opravila. Standardizacija: algoritme je mogoče standardizirati in deliti med različnimi ekipami ali organizacijami, kar ljudem olajša sodelovanje in izmenjavo znanja.

Na splošno so algoritmi bistveno orodje za reševanje problemov na različnih področjih, vključno z računalništvom, inženiringom, analizo podatkov, financami in številnimi drugimi.

primer:

Razmislite o škatli, v kateri nihče ne vidi, kaj se dogaja v njej, pravimo črna skrinjica.

Polje damo vhodne podatke in ta nam da izhod, ki ga potrebujemo, vendar je postopek, ki bi ga morda morali poznati za pretvorbo vnosa v želeni izhod, ALGORITEM.

Algoritem je neodvisen od uporabljenega jezika. Programerju pove logiko, uporabljeno za rešitev problema. Gre torej za logičen postopek po korakih, ki programerjem deluje kot načrt.

Primeri iz resničnega življenja, ki opredeljujejo uporabo algoritmov:

• Razmislite o uri. Vemo, da ura tiktaka, toda kako proizvajalec nastavi te matice in vijake tako, da se vsakih 60 sekund premakne kazalec min in vsakih 60 minut se mora premakniti urni kazalec? Za rešitev tega problema mora torej obstajati algoritem.
• Ste videli nekoga, ki vam kuha vašo najljubšo hrano? Je za to potreben recept? Da, potrebno je, saj je recept zaporedni postopek, ki spremeni surov krompir v hladen krompir. To je tisto, kar je algoritem: sledenje postopku za pridobitev želenega rezultata. Ali je treba upoštevati zaporedje? Da, zaporedje je najpomembnejša stvar, ki se je moramo držati, da dobimo tisto, kar želimo.

Vrste algoritmov:

• Algoritmi za razvrščanje: Razvrščanje z mehurčki, razvrščanje z vstavljanjem in še veliko več. Ti algoritmi se uporabljajo za razvrščanje podatkov v določeni obliki.
• Algoritmi iskanja: Linearno iskanje, binarno iskanje itd. Ti algoritmi se uporabljajo pri iskanju vrednosti ali zapisa, ki ga zahteva uporabnik.
• Algoritmi grafov : Uporablja se za iskanje rešitev za težave, kot je iskanje najkrajše poti med mesti, in težave iz resničnega življenja, kot so težave s trgovskim potnikom.

Algoritmi za razvrščanje so algoritmi, ki vzamejo zbirko elementov in jih prerazporedijo v določenem vrstnem redu (npr. naraščajoče ali padajoče). Obstaja veliko različnih algoritmov za razvrščanje, od katerih ima vsak svoje prednosti in slabosti. Nekateri najpogosteje uporabljeni algoritmi za razvrščanje vključujejo:

Razvrščanje mehurčkov: Preprost algoritem za razvrščanje, ki večkrat koraka po seznamu, primerja sosednje elemente in jih zamenja, če so v napačnem vrstnem redu.

Razvrstitev vstavljanja: Preprost algoritem za razvrščanje, ki sestavi končno razvrščeno matriko en element naenkrat, tako da primerja vsak nov element z že razvrščenimi elementi in ga vstavi na pravilno mesto.

Razvrstitev izbora: Preprost algoritem za razvrščanje, ki vedno znova izbere najmanjši element iz nerazvrščenega dela matrike in ga premakne na konec razvrščenega dela.

Spoji razvrsti: Algoritem za razvrščanje deli in vladaj, ki deluje tako, da razdeli nerazvrščen seznam na n podseznamov, razvrsti vsak podseznam in jih nato združi nazaj v en sam razvrščen seznam.

Hitro razvrščanje: Algoritem za razvrščanje razdeli in vladaj, ki deluje tako, da iz matrike izbere vrtilni element in druge elemente razdeli na dve podmatriki, glede na to, ali so manjši ali večji od vrtišča. Podnize so nato razvrščene rekurzivno.

Vsak od teh algoritmov ima drugačno časovno in prostorsko kompleksnost, zaradi česar so nekateri primernejši za določene primere uporabe kot drugi.

veriženje naprej

Iskalni algoritmi so algoritmi, ki iščejo določen element ali vrednost v podatkovni strukturi (kot je polje ali povezan seznam). Nekateri najpogosteje uporabljeni iskalni algoritmi vključujejo:

Linearno iskanje: Preprost algoritem iskanja, ki ponavlja vsak element seznama, dokler ne najde ujemanja.

Binarno iskanje: Iskalni algoritem, ki deluje tako, da razvrščeni seznam večkrat razdeli na polovico, dokler ni najden želeni element ali se lahko ugotovi, da elementa ni.

Skoči iskanje: Iskalni algoritem, ki deluje tako, da skače naprej po fiksnih korakih na seznamu, dokler ni najden ustrezen kandidat, nato pa izvede linearno iskanje v okoliških elementih.

Interpolacijsko iskanje : iskalni algoritem, ki deluje tako, da uporabi informacije o obsegu vrednosti na seznamu za oceno položaja želenega elementa in nato preveri, ali je res prisoten.

Iskanje zgoščene tabele: Iskalni algoritem, ki uporablja zgoščevalno funkcijo za preslikavo elementov v indekse v matriki, nato pa izvede iskanje v matriki v konstantnem času, da najde želeni element.

Vsak od teh algoritmov ima drugačno časovno in prostorsko kompleksnost, zaradi česar so nekateri primernejši za določene primere uporabe kot drugi. Izbira algoritma za uporabo je odvisna od posebnih zahtev problema, kot so velikost podatkovne strukture, porazdelitev vrednosti in želena časovna kompleksnost.

Algoritmi grafov so nabor algoritmov, ki se uporabljajo za obdelavo, analizo in razumevanje podatkovnih struktur grafov. Grafi so matematične strukture, ki se uporabljajo za modeliranje odnosov med objekti, kjer so objekti predstavljeni kot vozlišča (ali vozlišča), odnosi med njimi pa kot robovi. Algoritmi grafov se uporabljajo v različnih aplikacijah, kot so analiza omrežij, analiza socialnih omrežij, sistemi priporočil in na številnih drugih področjih, kjer je razumevanje odnosov med objekti pomembno. Nekateri pogosti algoritmi grafov vključujejo:

Algoritmi najkrajše poti (npr. Dijkstra's, Bellman-Ford, A*)
Algoritmi minimalnega vpetega drevesa (npr. Kruskal, Prim)
Algoritmi največjega pretoka (npr. Ford-Fulkerson, Edmonds-Karp)
Algoritmi mrežnega toka (npr. Bipartitno ujemanje)
Algoritmi povezljivosti (npr. iskanje v globino, iskanje v širino)

Zakaj uporabljamo algoritme?

Predstavljajte si dva otroka, Amana in Rohana, ki rešujeta Rubikovo kocko. Aman zna rešiti v točno določenem številu korakov. Po drugi strani pa Rohan ve, da bo to storil, vendar se ne zaveda postopka. Aman reši kocko v 2 minutah, medtem ko je Rohan še vedno obtičal in do konca dneva mu jo je nekako uspelo rešiti (morda je goljufal, ker je postopek potreben).

Torej je čas, potreben za reševanje s postopkom/algoritmom, veliko bolj učinkovit kot tisti brez kakršnega koli postopka. Zato je potreba po algoritmu nujna.

Z vidika oblikovanja rešitve za IT problem so računalniki hitri, vendar ne neskončno hitri. Pomnilnik je morda poceni, vendar ne brezplačen. Torej je računalniški čas torej omejen vir, prav tako pa tudi prostor v pomnilniku. Zato bi morali te vire uporabljati pametno, pri tem pa vam bodo pomagali algoritmi, ki so časovno in prostorsko učinkoviti.

Ustvarjanje algoritma:

Ker je algoritem neodvisen od jezika, napišemo korake, da pokažemo logiko rešitve, ki se uporablja za rešitev problema. Toda preden napišete algoritem, upoštevajte naslednje:

• Algoritem mora biti jasen in nedvoumen.
• V algoritmu mora biti 0 ali več dobro definiranih vnosov.
• Algoritem mora proizvesti enega ali več dobro definiranih izhodov, ki so enakovredni želenemu izhodu. Po določenem številu korakov se morajo algoritmi ustaviti.
• Algoritmi se mora ustaviti ali končati po končnem številu korakov.
• V algoritmu morajo biti podana navodila po korakih, ki morajo biti neodvisna od kakršne koli računalniške kode.

primer: algoritem za množenje 2 števil in izpis rezultata:

Korak 1: Začetek
2. korak: Pridobite znanje o vnosu. Tukaj potrebujemo 3 spremenljivke; a in b bosta uporabniški vnos, c pa bo vseboval rezultat.
3. korak: Deklarirajte spremenljivke a, b, c.
4. korak: Sprejemite vnos za spremenljivki a in b od uporabnika.
5. korak: Spoznajte problem in poiščite rešitev z uporabo operatorjev, podatkovnih struktur in logike

Spremenljivki a in b moramo pomnožiti, zato uporabimo operator * in rezultat dodelimo c.
To je c <- a * b

6. korak: Preverite, kako podati izhod. Tukaj moramo natisniti izhod. Torej napiši natisni c
7. korak: Konec

Primer 1: Napišite algoritem za iskanje največjega števila vseh elementov v matriki.
Sledite naslednjemu algoritmu:

teorija avtomatov

Korak 1: Zaženite program
2. korak: Deklarirajte spremenljivko max z vrednostjo prvega elementa matrike.
3. korak: Primerjajte max z drugimi elementi z uporabo zanke.
4. korak: Če je maks 5. korak: Če ni nobenega elementa, vrnite ali natisnite max, sicer pojdite na 3. korak.
6. korak: Konec rešitve

Primer 2: Napišite algoritem za iskanje povprečja 3 predmetov.
Sledite naslednjemu algoritmu:

Korak 1: Zaženite program
2. korak: Navedite in preberite 3 zadevo, recimo S1, S2, S3
3. korak: Izračunajte vsoto vseh 3 vrednosti predmeta in shranite rezultat v spremenljivko vsota (Vsota = S1+S2+S3)
4. korak: Vsoto delite s 3 in jo dodelite spremenljivki Average. (Povprečje = vsota/3)
5. korak: Natisnite vrednost Povprečje 3 predmetov
6. korak: Konec rešitve

Vedeti o zapletenosti algoritma:

Kompleksnost v algoritmih se nanaša na količino virov (kot je čas ali pomnilnik), ki so potrebni za rešitev problema ali izvedbo naloge. Najpogostejša mera zapletenosti je časovna zapletenost, ki se nanaša na količino časa, ki ga algoritem potrebuje, da ustvari rezultat kot funkcijo velikosti vnosa. Kompleksnost pomnilnika se nanaša na količino pomnilnika, ki ga uporablja algoritem. Oblikovalci algoritmov si prizadevajo razviti algoritme z najnižjo možno časovno in pomnilniško kompleksnostjo, saj so zaradi tega bolj učinkoviti in razširljivi.

Kompleksnost algoritma je funkcija, ki opisuje učinkovitost algoritma glede na količino podatkov, ki jih mora algoritem obdelati.

Običajno obstajajo naravne enote za domeno in obseg te funkcije.

Algoritem se analizira s časovno kompleksnostjo in prostorsko kompleksnostjo. Pisanje učinkovitega algoritma pomaga porabiti minimalno količino časa za obdelavo logike. Za algoritem A se presoja na podlagi dveh parametrov za vnos velikosti n:

• Časovna zapletenost: Čas, ki ga algoritem porabi za rešitev problema. Izmeri se z izračunom iteracije zank, števila primerjav itd.
• Časovna kompleksnost je funkcija, ki opisuje količino časa, ki ga algoritem potrebuje glede na količino vnosa v algoritem.
• Čas lahko pomeni število opravljenih dostopov do pomnilnika, število primerjav med celimi števili, kolikokrat se izvede notranja zanka ali kakšno drugo naravno enoto, povezano s količino realnega časa, ki ga bo algoritem potreboval.
• Kompleksnost prostora: Prostor, ki ga algoritem zavzame za rešitev problema. Vključuje prostor, ki ga uporabljajo potrebne vhodne spremenljivke, in morebitni dodatni prostor (razen prostora, ki ga zavzamejo vhodi), ki ga uporablja algoritem. Na primer, če uporabljamo razpršilno tabelo (neke vrste podatkovne strukture), potrebujemo matriko za shranjevanje vrednosti
• to je zaseden dodatni prostor, zato se bo štelo k kompleksnosti prostora algoritma. Ta dodatni prostor je znan kot pomožni prostor.
• Kompleksnost prostora je funkcija, ki opisuje količino pomnilnika (prostora), ki ga algoritem porabi glede na količino vnosa v algoritem.
• Zapletenost prostora je včasih prezrta, ker je uporabljeni prostor minimalen in/ali očiten, včasih pa postane težava kot čas.

.Časovna zahtevnost operacij:

• Izbira strukture podatkov mora temeljiti na časovni zahtevnosti operacij, ki se bodo izvajale.
• Časovna kompleksnost je opredeljena glede na to, kolikokrat je potrebno zagnati dani algoritem glede na dolžino vnosa.
• Časovna kompleksnost algoritma je čas, ki je potreben za dokončanje posamezne izjave. Zelo je odvisno od velikosti obdelanih podatkov.
• Na primer, če morate pogosto izvajati iskanja, uporabite binarno iskalno drevo.

.Prostorska zahtevnost operacij:

• Izbira strukture podatkov mora temeljiti na prostorski zahtevnosti operacij, ki se bodo izvajale.
• Količina pomnilnika, ki ga program uporablja za izvajanje, je predstavljena z njegovo prostorsko kompleksnostjo.
• Ker program med delovanjem potrebuje pomnilnik za shranjevanje vhodnih podatkov in časovnih vrednosti, je kompleksnost prostora pomožni in vhodni prostor.
• Na primer, če morate shraniti veliko podatkov, uporabite matriko.

zapleteni primeri:

Obstajata dva pogosto raziskana primera zapletenosti algoritmov:

1. Zapletenost najboljšega primera: Najboljši scenarij za algoritem je scenarij, v katerem algoritem opravi najmanjšo količino dela (npr. vzame najkrajši čas, uporabi najmanjšo količino pomnilnika itd.).

2. Kompleksnost v najslabšem primeru: Najslabši možni scenarij za algoritem je scenarij, v katerem algoritem opravi največjo količino dela (npr. vzame najdlje časa, porabi največ pomnilnika itd.).

Pri analizi kompleksnosti algoritma je pogosto bolj informativno preučiti najslabši možni scenarij, saj to daje zajamčeno zgornjo mejo učinkovitosti algoritma. Včasih se izvede analiza najboljšega scenarija, vendar je na splošno manj pomembna, saj zagotavlja spodnjo mejo, ki jo je pogosto nepomembno doseči.

Prednosti algoritmov

• Lahko razumeti: Ker gre za postopno predstavitev rešitve danega problema, ga je enostavno razumeti.
• Neodvisno od jezika: Ni odvisen od nobenega programskega jezika, zato ga zlahka razume vsak.
• Odpravljanje napak/iskanje napak: Vsak korak je neodvisen/v toku, tako da bo napako enostavno opaziti in odpraviti.
• Podproblemi: Napisan je v toku, tako da lahko zdaj programer razdeli naloge, kar olajša njihovo kodiranje.

Slabosti algoritmov

• Ustvarjanje učinkovitih algoritmov je dolgotrajno in zahteva dobre logične sposobnosti.
• Neprijeten prikaz razvejanosti in zank v algoritmih.