Algoritam je slijed instrukcija koje se izvode unaprijed određenim slijedom kako bi se riješio problem ili dovršio posao. Funkcija je blok koda koji se može pozvati i izvršiti iz drugih dijelova programa.
Skup uputa za rješavanje problema ili provođenje određene aktivnosti. U računalnoj znanosti algoritmi se koriste za širok raspon operacija, od osnovne matematike do zamršene obrade podataka.
Jedan od uobičajenih algoritama koji se koristi u C-u je algoritam sortiranja. Algoritam za sortiranje raspoređuje kolekciju stavki određenim redoslijedom, na primjer numerički ili abecedno.
Postoji mnogo algoritama sortiranja, svaki s prednostima i nedostacima. Najčešći algoritmi sortiranja u C-u su brzo sortiranje, spajanje i sortiranje.
Jedna od ključnih značajki C-a je podrška pokazivača. To omogućuje učinkovitu manipulaciju podatkovnim strukturama kao što su nizovi, redovi čekanja itd. To ga čini prikladnim za implementaciju algoritama koji zahtijevaju složenu manipulaciju podacima, kao što je sortiranje i algoritamsko pretraživanje.
Jedan od poznatih primjera softverske biblioteke implementirane u C je Standard Template Library (STL). Ova biblioteka pruža širok izbor algoritama za zadatke kao što su sortiranje, pretraživanje i manipuliranje strukturama podataka.
Značajke algoritma
Definira nekoliko važnih značajki algoritma, uključujući:
linux pokrenuti cmd
Analiza algoritma
Algoritamska analiza je proces ocjenjivanja performansi algoritma u smislu učinkovitosti, složenosti i drugih kriterija. To se obično radi za procjenu mnogih algoritama i odabir optimalnog rješenja za određeni problem ili softver.
Analiza algoritama obično uključuje mjerenje njihove vremenske i prostorne složenosti.
Kao i kod prostorne složenosti, koja opisuje količinu potrebne memorije ili diskovnog prostora, vremenska složenost opisuje koliko dugo algoritam određuje za obavljanje zadatka.
Postoje različiti načini analize vremenske složenosti algoritama, kao što su Big O i Omega notacija. Simbol Omega daje gornju granicu za vremensku složenost algoritma, dok simbol Omega daje donju granicu.
Uz mjerenje vremenske i prostorne složenosti, analiza algoritma također uključuje druge kriterije kao što su stabilnost, paralelizam i skalabilnost.
Uključuju dvije vrste analiza.
oni su:-
- Prethodna analiza.
- Posteriorna analiza.
Prethodna analiza
Prior je metoda analize algoritma koja se fokusira na procjenu izvedbe algoritma na temelju njegovih matematičkih svojstava bez stvarnog izvršavanja algoritma.
Ovaj vam pristup omogućuje analizu vremenske i prostorne složenosti algoritama i drugih metrika bez potrebe za implementacijom i pokretanjem algoritama.
Posteriorna analiza
Posteriorna analiza je, s druge strane, metoda analize algoritma koja zapravo izvršava algoritam i mjeri njegovu izvedbu.
Ovaj pristup daje točnije i detaljnije informacije o izvedbi algoritma, ali zahtijeva implementaciju i izvršenje algoritma.
Složenost algoritma
Algoritamska složenost je mjera za mjerenje učinkovitosti i performansi algoritma. Algoritmi se obično procjenjuju u smislu vremena i prostora potrebnog za rješavanje problema ili postizanje određenog cilja.
U složenosti algoritma koriste se dva faktora.
oni su:-
- Faktor vremena.
- Prostorni faktor.
Faktor vremena
- Količina vremena koju algoritam treba da obavi zadatak naziva se vremenskom složenošću. Obično se mjeri brojem operacija ili koraka koje algoritam mora izvršiti da bi riješio problem.
- Vremenska složenost algoritma je važna jer određuje koliko mu je vremena potrebno da se izvrši i može imati značajan utjecaj na performanse programa i sustava.
- Vremenska složenost algoritma može se izraziti pomoću Big O notacije, načina izražavanja gornje granice vremenske složenosti algoritma.
- Algoritam s vremenskom složenošću O(n) znači da je vrijeme potrebno za pokretanje algoritma izravno proporcionalno veličini ulaznih podataka (n).
- Druge uobičajene vremenske složenosti su O(n^2) kvadratna složenost i O(log n) logaritamska složenost.
Analiza prostora
- S druge strane, prostorna složenost odnosi se na količinu memorije ili prostora za pohranu potrebnu za izvođenje algoritma.
- Ovo je važno jer određuje broj resursa potrebnih za pokretanje algoritama koji mogu utjecati na ukupnu izvedbu vaše aplikacije ili sustava.
- Ako je prostorna složenost algoritma O(n), on koristi količinu memorije koja raste linearno s veličinom ulaza.
- Ako algoritam ima O(1) prostornu složenost, koristi fiksnu količinu memorije bez obzira na veličinu ulaza.
Kako napisati algoritam
1. Prvo definirajte problem koji želite da algoritam riješi.
Na primjer, pretpostavimo da želimo napisati algoritam za pronalaženje maksimalne vrijednosti s popisa brojeva.
2. Podijelite problem na manje korake kojima se može upravljati.
- Inicijalizirajte varijablu 'max' na prvu vrijednost na popisu.
- Za svaku sljedeću vrijednost na popisu usporedite s 'max'.
- Ako je vrijednost veća od 'max', postavite 'max' na tu vrijednost.
- Nastavite s ovim dok se ne usporedi svaka vrijednost na popisu.
- Vraća konačnu vrijednost 'max'.
3. Napišite svoj algoritam u pseudokodu ili programskom jeziku.
Algoritam napisan u pseudo kodu:
MAX (list) max = list[0] For i = 1 the length of the list list IF[i] > max max = list[i] End for Maximum return Maximum end
4. Testirajte svoj algoritam kako biste bili sigurni da je točan i učinkovit.
Algoritam možete testirati unosom različitih popisa brojeva i provjerom vraća li najveću točnu vrijednost. Također možete analizirati vremensku složenost vašeg algoritma kako biste odredili koliko se dobro skalira za veće ulaze.
Primjer:-
Unos: [1, 5, 2, 7, 3]
Izlaz: 7.
Objašnjenje: 7 je najveća vrijednost na popisu.
5. Optimizirajte algoritam.
Potražite načine za optimizaciju algoritama kako biste bili brži i učinkovitiji. To može uključivati modificiranje pseudokoda ili implementaciju učinkovitijih struktura podataka ili algoritama.
Osnovno pisanje algoritama
Primjer: - Zbroj dva cijela broja.
Korak 1 - Počnite
Korak 2 - Deklarirajte tri cijela broja a, b, c
3. korak - Definirajte vrijednosti a i b
Korak 4 - Zbrojite vrijednosti a i b
Korak 5 - Spremite izlaz koraka 4 u c
Korak 6 - Ispis c
Korak 7 - Stani
Vrsta algoritama koji se koriste u C jeziku.
1. Algoritmi sortiranja
C pruža bogat skup tipova podataka i operatora koji se mogu koristiti za implementaciju različitih algoritama sortiranja kao što su sortiranje u obliku mjehurića, sortiranje umetanjem i brzo sortiranje.
Ovi su algoritmi korisni u mnogim aplikacijama jer se mogu koristiti za sortiranje podataka različitih veličina i vrsta.
Postoje različiti algoritmi sortiranja.
oni su:-
(i) Razvrstavanje mjehurićima: Nekomplicirani algoritam sortiranja koji više puta uspoređuje obližnje komponente i isključuje ih ako nisu u redu.
Algoritam za Bubble sortiranje je:-
- Započnite s nerazvrstanim popisom elemenata.
- Usporedite prva dva elementa na popisu. Ako je prvi element veći od drugog elementa, zamijenite ih.
- Prijeđite na sljedeći par elemenata i ponavljajte korak 2 dok ne dođete do kraja popisa.
- Za svaku stavku na popisu ponovite korake 2 i 3 još jednom. koji se naziva propusnicama.
- Ponovite korake 2-4 za cijeli popis. Kako budete ponavljali prolaze, elementi će se 'napuhati' na svoje ispravno mjesto na sortiranom popisu.
- Nakon što je prolaz dovršen i nema zamjena, popis se sortira i algoritam se može zaustaviti.
- Vraća se konačni sortirani popis.
(ii) Vrsta umetanja : metoda sortiranja koja stvara sortirani popis jedan po jedan pojedinačni element postavljanjem svakog na odgovarajuće mjesto.
Algoritam za sortiranje umetanjem je:-
- Inicijalizirajte prazan sortirani popis i nesortirani popis elemenata koji se sortiraju.
- Treba uzeti prvog člana s nesređenog popisa i staviti ga na odgovarajuće mjesto u sređenom popisu.
- Ponovite korak 2 za svaki sljedeći element na nerazvrstanom popisu.
- Usporedite trenutni element s elementima na sortiranom popisu, počevši od elementa odmah lijevo.
- Zamijenite dva elementa ako je trenutni element manji od elementa lijevo od njega.
- Ako je trenutni element veći od elementa s njegove lijeve strane, umetnite ga na ispravno mjesto u sortiranom popisu.
- Ponovite korake 4-6 za svaki sljedeći element na nerazvrstanom popisu.
- Nakon što su svi elementi obrađeni, sortirani popis sadržavat će sve elemente ispravnim redoslijedom.
- Proces sortiranja je završen.
(iii) Sortiranje odabira : metoda sortiranja koja dosljedno počinje sortirani popis s najmanjim detaljima iz nesređenog popisa.
Algoritam za sortiranje selekcije je:-
- Započnite postavljanjem primarnog elementa liste kao min elementa.
- Ponovite kroz preostale stavke na popisu, uspoređujući svaku s trenutnim minimumom.
- Postavite novi minimum ako se utvrdi da je element manji od postojećeg.
- Promijenite trenutni minimum na prvi element liste kad god dođe do svog zaključka.
- Za preostali nerazvrstani dio popisa ponovite korake 2-4, ali započnite s drugom stavkom na popisu (jer je prvi element već sortiran).
- Nastavite sortirati popis na ovaj način dok ga sve ne posložite.
(iv) Brzo sortiranje : Algoritam za razvrstavanje po principu 'podijeli i vladaj' koji odabire zaokretni element i dijeli popis na podpopise ovisno o tome jesu li elementi manji ili veći od zaokretnog elementa. Nakon toga, podpopisi se više puta sortiraju dok se ne sortira cijeli popis.
Algoritam za brzo sortiranje je:-
- Odaberite stožerni element s popisa. Ovo je obično prvi element, ali može biti i nasumični element ili medijan popisa.
- Podijelite popis na dva podpopisa: jedan koji sadrži elemente manje od stožera i drugi koji sadrži elemente veće od stožera.
- Rekurzivno sortirajte podpopis koji sadrži elemente manje od zaokretne točke koristeći isti postupak.
- Upotrijebite istu proceduru za rekurzivno sortiranje podpopisa unosa većih od stožerne točke.
- Spojite sortirane podpopise sa zaokretnim elementom između kako biste formirali potpuno sortirani popis.
- Vrati potpuno sortirani popis.
(v) Ždrijeb ide : algoritam sortiranja zadijeli i vladaj dijeli popis na dvije polovice, razvrstava svaku polovicu, a zatim spaja dvije polovice sortiranim redoslijedom.
Algoritam sortiranja spajanjem:
naredba git push
- Napravite dva podpopisa od popisa: jedan s elementima ispod pivota i jedan s elementima iznad pivota.
- Proizvodi novi sortirani podpopis iterativnim spajanjem podpopisa dok ne postoji samo jedan podpopis. Ovo će biti vaš sortirani popis.
- Koraci za spajanje dvaju poddirektorija:-
- Napravite prazan popis za držanje sortiranih elemenata.
- Uspoređuje prvi element svakog podpopisa.
- Dodaje manji element novom popisu i uklanja ga s nadređenog podpopisa.
- Ponavljajte korake 2 i 3 dok popis ne bude potpuno prazan.
- Dodaje preostale elemente iz drugih podpopisa u novi popis.
- Zamjenjuje spojeni podpopis novim sortiranim popisom.
- Ponavljajte ovaj postupak dok se svi podpopisi ne spoje u jedan sortirani popis.
(vi) Sortiranje gomile : Algoritam sortiranja koji sortira elemente pomoću podatkovne strukture koja se naziva hrpa.
Ovo je algoritam klasifikacije:
- Složite ostale elemente. Počevši od korijena, svaki se čvor uspoređuje sa svojom djecom, zamjenjujući čvorove sa svojom starijom djecom dok se ne zadovolji svojstvo maksimalne hrpe.
- Ponovite korake 2 i 3 s novosloženim elementima, osim za posljednji element u ispravnom položaju.
- Ponavljajte ovaj postupak sve dok u hrpi ne ostane samo jedan element. Ovo je sada sređeno.
(vii) Radix sorta : Algoritam sortiranja koji sortira elemente na temelju znamenki ili znamenki njihove binarne reprezentacije.
Algoritam za Radix sortiranje je:-
- odrediti koliko je znamenki sadržano u najvećem elementu popisa unosa.
- Inicijalizirajte varijablu, recimo mjesto znamenke, na 1, što predstavlja trenutno mjesto znamenke.
- Napravite prazan popis za svaku moguću vrijednost znamenki od 0 do 9.
- Iterirajte kroz ulaznu listu i dodajte svaki element na odgovarajuću listu na temelju vrijednosti trenutnog mjesta znamenke.
- Spojite sve popise zajedno kako biste formirali novi popis prema redoslijedu popisa znamenki.
- Pomnožite digitPlace s 10 za prelazak na sljedeće mjesto znamenke.
- Ponovite korake 4-6 za svako mjesto znamenke dok se ne uzmu u obzir sve znamenke u najvećem elementu.
- Konačna lista će biti poredana uzlaznim redoslijedom prema znamenkama elemenata.
- Vrati konačni sortirani popis.
2. Algoritmi pretraživanja
C također pruža alate potrebne za implementaciju raznih algoritama pretraživanja, kao što su linearno pretraživanje i binarno pretraživanje. Ovi algoritmi mogu brzo pronaći određene stavke u skupu podataka, što ih čini korisnima za širok raspon aplikacija.
Postoje mnoge vrste algoritama pretraživanja.
Oni su:-
(i) Linearna pretraga : Osnovni algoritam pretraživanja koji ispituje svaku stavku u popisu jednu po jednu dok ne pronađe željenu stavku.
Algoritam za linearno pretraživanje:-
- Definirajte ulaz za algoritam: Ulaz za algoritam linearne pretrage je popis elemenata (ili niz) i ciljni element koji tražimo.
- Inicijalizirajte varijablu pod nazivom 'index' na -1: Ova varijabla će se koristiti za pohranjivanje indeksa ciljnog elementa ako se pronađe.
- Prođite kroz popis elemenata: Počevši od prvog elementa, provjerite svaki element na popisu jedan po jedan.
- Usporedite sadašnji element sa željenim elementom za procjenu: Zadržite indeks trenutnog elementa u varijabli indeksa i izađite iz petlje ako su moderni element i ciljni element identični.
- Vraćanje indeksa ciljnog elementa: Nakon završetka petlje, vratite vrijednost pohranjenu u varijabli indeksa. Ako ciljni element nije pronađen, vrijednost indeksa bit će -1.
(ii) Binarno pretraživanje : Veća je vjerojatnost da će algoritam pretraživanja koji radi dijeljenjem popisa na polovice i pretraživanja unutar tih polovica uključiti element.
Algoritam za binarno pretraživanje:-
- Ulaz: sortirani popis od n elemenata i ciljni element x.
- Inicijalizirajte varijable: Postavite niski indeks na 0, visoki indeks na n-1, a srednji na (niski+visoki)/2.
- Pokrenite petlju: Dok je niski indeks manji ili jednak visokom indeksu, ponovite sljedeće korake.
- Usporedite srednji element s x: Ako je srednji element jednak x, vratite srednji indeks.
- Ažurirajte niski ili visoki indeks: ako je x veći od srednjeg elementa, postavite niski indeks na srednji + 1. Inače, postavite visoki indeks na srednji - 1.
- Ažurirajte srednji indeks: Srednji = (nizak+visok)/2.
- Kraj petlje: Ako je niski indeks veći od visokog indeksa, tada x nije na popisu i algoritam vraća grešku.
- Izlaz: Indeks x na popisu ili poruka o neuspjehu.
(iii) Pretraživanje najprije u dubinu : Algoritam pretraživanja koji ispituje svaku granu koliko god je to moguće prije nego što se okrene.
Sljedeće smjernice primjenjuju se na dubinsko pretraživanje:
- odaberite početni vrh ili čvor grafa za početak.
- Dodajte oznaku posjeta na prvi vrh.
- Izravno postavite početni vrh u hrpu.
- Dok se hrpa ne isprazni, ponavljajte sljedeće radnje: -
- Uklonite gornji vrh snopa.
- Označite kao posjećene i umetnite u stog svakog neposjećenog susjeda izbačenog vrha.
- Nastavite s ovim postupkom dok se ne posjete svi vrhovi u grafu.
- Nakon što su svi vrhovi posjećeni, algoritam je dovršen i na grafu se izvodi prvo dubinsko pretraživanje.
(iv) Pretraživanje u širinu : Algoritam pretraživanja koji istražuje sve susjede čvora prije prelaska na sljedeću razinu.
Algoritam za pretraživanje u širinu je:
- Počnite s korijenskim čvorom ili početnim stanjem.
- Dodajte korijenski čvor u red čekanja.
- Provjerite je li red prazan; ako da, onda prekinuti algoritam.
- Uzmite prvi element iz reda čekanja i označite ga kao posjećen.
- Proširite suvremeni čvor dodavanjem svih njegovih neposjećenih susjeda u red čekanja.
- Dok se ne pronađe željeni čvor ili dok se red čekanja ne isprazni, ponavljajte korake 3 do 5.
- Vrati put iz preliminarnog stanja u ciljno stanje ako je ciljni čvor pronađen.
- Prekinite skup pravila i prijavite da stanje cilja nije identificirano ako je red prazan.
(v) Interpolacijsko pretraživanje : Algoritam pretraživanja koji koristi vrijednosti traženih elemenata za procjenu položaja u indeksu.
Važno je da je niz ravnomjerno raspoređen. Inače, to je algoritam.
Radi prema očekivanjima.
Algoritam se može sažeti na sljedeći način.
- Dobijte popis unosa i ključnu vrijednost za pretraživanje.
- Inicijalizirajte donju i gornju varijablu na prvom i zadnjem indeksu liste.
- Ako je donja vrijednost manja ili jednaka višoj vrijednosti, tada:-
- Izračunajte procijenjenu lokaciju pomoću sljedeće formule:
pos = low + ((visoko - nisko) / (arr[visoko] - arr[nisko])) * (x - arr[nisko]). - Vrati poziciju ako je procijenjena vrijednost pozicije ključna vrijednost.
- c) Ako je procijenjena vrijednost pozicije manja od ključne vrijednosti, postavite je nižu.
Pozicija + 1. - d) Ako je vrijednost procijenjene pozicije veća od ključa Set value, pozicija - 1 gore.
- Izračunajte procijenjenu lokaciju pomoću sljedeće formule:
- Ako vrijednost ključa nije pronađena, vratite -1 da označite da vrijednost nije na popisu.
(vi) Preskočno pretraživanje : Metoda pretraživanja koja ponavlja popis u koracima konstantne duljine dok ne pronađe relevantni element ili dok ne utvrdi da više nije prisutan.
Algoritam pretraživanja skokova je sljedeći:
- Najprije postavite veličinu skoka na kvadratni korijen broja elemenata niza.
- Postavlja varijablu pod nazivom 'current' na prvi element niza.
- Iterira preko niza skačući po veličini skoka dok povećava varijablu pod nazivom 'skok'.
- Prijeđite na sljedeći skok ako je postojeći element manji od željenog.
- Ako je trenutni element veći od ciljanog elementa, izvršite linearno pretraživanje između trenutnog elementa i prethodnog skoka da biste pronašli ciljni element.
- Ako ciljni element nije pronađen u nizu, vraća -1 kako bi označio da nije u nizu.
- Ako je element pronađen, vraća indeks elementa u nizu.
3. Algoritmi grafova
Podrška C-a za pokazivače i strukture podataka kao što su polja i povezane liste čini ga prikladnim za implementaciju algoritama koji manipuliraju grafovima, kao što je pronalaženje najkraćeg puta između dva čvora u grafu.
Postoje različite vrste algoritama za grafove.
oni su:-
4. Kriptografski algoritmi
C podržava operacije niske razine i učinkovitu manipulaciju podacima, što ga čini idealnim za implementaciju algoritama koji se koriste u kriptografiji, kao što su algoritmi za šifriranje i dešifriranje podataka.
Postoje različite vrste algoritama šifriranja.
Oni su:-
Prednosti algoritma
Algoritmi imaju mnoge prednosti.
oni su:-
Nedostaci algoritma
Algoritmi su vrlo korisni za programiranje, ali algoritmi imaju nedostatke.
oni su:-