Algoritem je zaporedje navodil, ki se izvajajo v vnaprej določenem zaporedju, da bi rešili problem ali dokončali delo. Funkcija je blok kode, ki ga je mogoče poklicati in izvesti iz drugih delov programa.
Niz navodil za rešitev problema ali izvedbo določene dejavnosti. V računalništvu se algoritmi uporabljajo za širok spekter operacij, od osnovne matematike do zapletene obdelave podatkov.
Eden izmed pogostih algoritmov, ki se uporablja v C, je algoritem za razvrščanje. Algoritem za razvrščanje razporedi zbirko elementov v določenem vrstnem redu, na primer po številu ali abecedi.
Obstaja veliko algoritmov za razvrščanje, vsak ima svoje prednosti in slabosti. Najpogostejši algoritmi za razvrščanje v C so hitro razvrščanje, spajanje in razvrščanje.
Ena od ključnih lastnosti C je podpora za kazalec. To omogoča učinkovito manipulacijo podatkovnih struktur, kot so nizi, čakalne vrste itd. Zaradi tega je primeren za izvajanje algoritmov, ki zahtevajo kompleksno manipulacijo podatkov, kot sta razvrščanje in algoritemsko iskanje.
Eden od znanih primerov knjižnice programske opreme, implementirane v C, je standardna knjižnica predlog (STL). Ta knjižnica ponuja široko paleto algoritmov za naloge, kot so razvrščanje, iskanje in manipulacija podatkovnih struktur.
Lastnosti algoritma
Določa več pomembnih lastnosti algoritma, vključno z:
Analiza algoritmov
Algoritemska analiza je postopek ocenjevanja delovanja algoritma glede na učinkovitost, kompleksnost in druga merila. Običajno se to naredi za oceno številnih algoritmov in izbiro optimalne rešitve za določeno težavo ali programsko opremo.
Analiza algoritmov običajno vključuje merjenje njihove časovne in prostorske kompleksnosti.
Tako kot pri kompleksnosti prostora, ki opisuje količino potrebnega pomnilnika ali prostora na disku, časovna kompleksnost opisuje, koliko časa algoritem določi za izvedbo naloge.
Obstajajo različni načini za analizo časovne kompleksnosti algoritmov, kot sta zapis Big O in Omega. Simbol Omega zagotavlja zgornjo mejo za časovno kompleksnost algoritma, simbol Omega pa spodnjo mejo.
Poleg merjenja kompleksnosti časa in prostora analiza algoritmov vključuje tudi druge kriterije, kot so stabilnost, vzporednost in razširljivost.
Vključujejo dve vrsti analize.
oni so:-
- Predhodna analiza.
- Posteriorna analiza.
Predhodna analiza
Prior je metoda analize algoritma, ki se osredotoča na ocenjevanje učinkovitosti algoritma na podlagi njegovih matematičnih lastnosti, ne da bi algoritem dejansko izvršil.
Ta pristop vam omogoča analizo časovne in prostorske kompleksnosti algoritmov in drugih meritev, ne da bi morali izvajati in izvajati algoritme.
Posteriorna analiza
Posteriorna analiza pa je metoda analize algoritma, ki dejansko izvaja algoritem in meri njegovo delovanje.
Ta pristop zagotavlja natančnejše in podrobnejše informacije o delovanju algoritma, vendar zahteva implementacijo in izvedbo algoritma.
Kompleksnost algoritma
Algoritemska kompleksnost je merilo za merjenje učinkovitosti in zmogljivosti algoritma. Algoritmi se običajno ocenjujejo glede na čas in prostor, potreben za rešitev problema ali doseganje določenega cilja.
Pri kompleksnosti algoritma sta uporabljena dva dejavnika.
oni so:-
- Časovni dejavnik.
- Prostorni faktor.
Časovni dejavnik
- Količina časa, ki ga algoritem potrebuje za izvedbo naloge, se imenuje časovna kompleksnost. Običajno se meri s številom operacij ali korakov, ki jih mora algoritem opraviti, da reši problem.
- Časovna zapletenost algoritma je pomembna, ker določa, koliko časa traja njegovo izvajanje, in lahko pomembno vpliva na delovanje programa in sistema.
- Časovno kompleksnost algoritma je mogoče izraziti z zapisom Big O, načinom izražanja zgornje meje časovne kompleksnosti algoritma.
- Algoritem s časovno kompleksnostjo O(n) pomeni, da je čas, potreben za izvajanje algoritma, neposredno sorazmeren z velikostjo vhodnih podatkov (n).
- Druge pogoste časovne zapletenosti so O(n^2) kvadratna zapletenost in O(log n) logaritemska zapletenost.
Analiza prostora
- Po drugi strani pa se kompleksnost prostora nanaša na količino pomnilnika ali prostora za shranjevanje, ki je potreben za izvedbo algoritma.
- To je pomembno, ker določa število virov, potrebnih za izvajanje algoritmov, ki lahko vplivajo na splošno zmogljivost vaše aplikacije ali sistema.
- Če je prostorska kompleksnost algoritma O(n), uporablja količino pomnilnika, ki raste linearno z velikostjo vnosa.
- Če ima algoritem prostorsko kompleksnost O(1), uporablja fiksno količino pomnilnika ne glede na velikost vnosa.
Kako napisati algoritem
1. Najprej definirajte problem, ki ga želite rešiti z algoritmom.
Na primer, recimo, da želimo napisati algoritem za iskanje največje vrednosti s seznama števil.
2. Težavo razdelite na manjše, obvladljive korake.
- Inicializirajte spremenljivko 'max' na prvo vrednost na seznamu.
- Za vsako naslednjo vrednost na seznamu primerjajte z 'max'.
- Če je vrednost večja od »max«, nastavite »max« na to vrednost.
- Nadaljujte s tem, dokler ne primerjate vseh vrednosti na seznamu.
- Vrne končno vrednost 'max'.
3. Napišite svoj algoritem v psevdokodi ali programskem jeziku.
Algoritem zapisan v psevdo kodi:
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. Preizkusite svoj algoritem in se prepričajte, da je pravilen in učinkovit.
Algoritem lahko preizkusite tako, da vnesete različne sezname številk in preverite, ali vrne največjo pravilno vrednost. Prav tako lahko analizirate časovno kompleksnost svojega algoritma, da ugotovite, kako dobro se prilagaja večjim vnosom.
Primer:-
Vnos: [1, 5, 2, 7, 3]
Izhod: 7.
Pojasnilo: 7 je največja vrednost na seznamu.
5. Optimizirajte algoritem.
Poiščite načine za optimizacijo algoritmov, da bodo hitrejši in učinkovitejši. To lahko vključuje spreminjanje psevdokoda ali implementacijo učinkovitejših podatkovnih struktur ali algoritmov.
10 ml v oz
Osnovno pisanje algoritmov
Primer: - Vsota dveh celih števil.
Korak 1 - Začeti
2. korak - Deklarirajte tri cela števila a, b, c
3. korak - Določite vrednosti a in b
4. korak - Seštejte vrednosti a in b
5. korak - Shranite rezultat 4. koraka v c
6. korak - Natisni c
korak 7 - Nehaj
Vrsta algoritmov, ki se uporabljajo v jeziku C.
1. Algoritmi za razvrščanje
C ponuja bogat nabor tipov podatkov in operatorjev, ki jih je mogoče uporabiti za implementacijo različnih algoritmov za razvrščanje, kot so razvrščanje z mehurčki, razvrščanje z vstavljanjem in hitro razvrščanje.
Ti algoritmi so uporabni v številnih aplikacijah, saj jih je mogoče uporabiti za razvrščanje podatkov različnih velikosti in vrst.
Obstajajo različni algoritmi za razvrščanje.
oni so:-
(i) Razvrščanje mehurčkov: Nezapleten algoritem za razvrščanje, ki vedno znova primerja bližnje komponente in jih izklopi, če niso v redu.
Algoritem za razvrščanje z mehurčki je:
- Začnite z nerazvrščenim seznamom elementov.
- Primerjaj prva dva elementa na seznamu. Če je prvi element večji od drugega elementa, ju zamenjajte.
- Premaknite se na naslednji par elementov in ponavljajte 2. korak, dokler ne dosežete konca seznama.
- Za vsak element na seznamu še enkrat ponovite 2. in 3. korak. ki se imenujejo prepustnice.
- Ponovite korake 2–4 za celoten seznam. Ko ponavljate prehode, se bodo elementi 'povzpeli' na svoje pravilno mesto na razvrščenem seznamu.
- Ko je prehod končan in ni zamenjav, je seznam razvrščen in algoritem se lahko ustavi.
- Vrne se končni razvrščeni seznam.
(ii) Razvrstitev vstavitve : metoda razvrščanja, ki ustvari razvrščen seznam posamezne elemente naenkrat tako, da vsakega postavi na ustrezno mesto.
Algoritem za razvrščanje vstavljanja je:-
- Inicializirajte prazen razvrščen seznam in nerazvrščen seznam elementov, ki jih želite razvrstiti.
- Vzamemo prvega člana z nerazvrščenega seznama in ga postavimo na ustrezno mesto na razvrščenem seznamu.
- Ponovite korak 2 za vsak naslednji element na nerazvrščenem seznamu.
- Primerjajte trenutni element z elementi na razvrščenem seznamu, začnite z elementom takoj na levi.
- Zamenjajte oba elementa, če je trenutni element manjši od elementa na njegovi levi.
- Če je trenutni element večji od elementa na njegovi levi, ga vstavite na pravilno mesto na razvrščenem seznamu.
- Ponovite korake 4–6 za vsak naslednji element na nerazvrščenem seznamu.
- Ko so vsi elementi obdelani, bo razvrščeni seznam vseboval vse elemente v pravilnem vrstnem redu.
- Postopek sortiranja je končan.
(iii) Izbirna vrsta : metoda razvrščanja, ki dosledno začne razvrščeni seznam z najmanjšo podrobnostjo iz neurejenega seznama.
Algoritem za razvrščanje izbire je:-
- Začnite tako, da primarni element seznama nastavite kot element min.
- Ponovite skozi preostale elemente na seznamu in vsakega primerjajte s trenutnim minimumom.
- Nastavite nov minimum, če se ugotovi, da je element manjši od obstoječega.
- Spremenite trenutni minimum na prvi element seznama, kadar koli doseže svoj zaključek.
- Za preostali nerazvrščeni del seznama ponovite korake 2–4, vendar začnite z drugim elementom na seznamu (ker je prvi element že razvrščen).
- Nadaljujte z razvrščanjem seznama na ta način, dokler ni vse razvrščeno.
(iv) Hitro razvrščanje : Algoritem za razvrščanje po principu »deli in vladaj«, ki izbere vrtilni element in razdeli seznam na podsezname glede na to, ali je elementov manj ali več kot vrtilni element. Po tem se podseznami večkrat razvrstijo, dokler ni razvrščen celoten seznam.
Algoritem za hitro razvrščanje je:
- Na seznamu izberite vrtilni element. To je običajno prvi element, lahko pa je tudi naključen element ali mediana seznama.
- Seznam razdelite na dva podseznama: enega, ki vsebuje elemente, manjše od vrtišča, in drugega, ki vsebuje elemente, večje od vrtišča.
- Z istim postopkom rekurzivno razvrstite podseznam, ki vsebuje manj elementov kot vrtišče.
- Uporabite isti postopek za rekurzivno razvrščanje podseznama vnosov, večjih od vrtišča.
- Združite razvrščene podsezname z vrtilnim elementom vmes, da oblikujete popolnoma razvrščen seznam.
- Vrni popolnoma razvrščen seznam.
(v) Lot gre : Algoritem za razvrščanje razdeli in vladaj seznam razdeli na dve polovici, vsako polovico razvrsti in nato obe polovici združi v razvrščenem vrstnem redu.
Algoritem spajanja-razvrščanja:
- Iz seznama naredite dva podseznama: enega z elementi pod vrtiščem in enega z elementi nad vrtiščem.
- Izdela nov razvrščen podseznam z iterativnim združevanjem podseznamov, dokler ne obstaja samo en podseznam. To bo vaš razvrščen seznam.
- Koraki za združitev dveh podimenikov:-
- Ustvarite prazen seznam za razvrščene elemente.
- Primerja prvi element vsakega podseznama.
- Doda manjši element na nov seznam in ga odstrani iz nadrejenega podseznama.
- Ponavljajte koraka 2 in 3, dokler seznam ni popolnoma prazen.
- Doda preostale elemente iz drugih podseznamov na nov seznam.
- Zamenja združeni podseznam z novim razvrščenim seznamom.
- Ta postopek ponavljajte, dokler niso vsi podseznami združeni v en razvrščen seznam.
(vi) Razvrščanje kopice : Algoritem za razvrščanje, ki razvršča elemente z uporabo podatkovne strukture, imenovane kopica.
To je algoritem razvrščanja:
- Zložite preostale elemente. Začenši od korena se vsako vozlišče primerja s svojimi podrejenimi vozlišči, pri čemer se vozlišča zamenjajo z njihovimi starejšimi podrejenimi, dokler ni zadoščena lastnost največje kopice.
- Ponovite koraka 2 in 3 z na novo zloženimi elementi, razen za zadnji element v pravilnem položaju.
- Ta postopek ponavljajte, dokler v skladu ne ostane samo en element. To je zdaj urejeno.
(vii) Razvrstitev Radix : Algoritem za razvrščanje, ki razvršča elemente na podlagi števk ali števk njihove binarne predstavitve.
Algoritem za razvrščanje Radix je:-
- določite, koliko števk vsebuje največji element vhodnega seznama.
- Inicializirajte spremenljivko, recimo mesto števke, na 1, ki predstavlja trenutno mesto števke.
- Ustvarite prazen seznam za vsako možno vrednost števk od 0 do 9.
- Ponavljajte po vhodnem seznamu in dodajte vsak element na ustrezen seznam glede na vrednost trenutnega števnega mesta.
- Združite vse sezname skupaj, da oblikujete nov seznam v vrstnem redu seznamov številk.
- Pomnožite digitPlace z 10, da se premaknete na naslednje mesto.
- Ponavljajte korake 4–6 za vsako števko, dokler ne upoštevate vseh števk v največjem elementu.
- Končni seznam bo razvrščen v naraščajočem vrstnem redu glede na števke elementov.
- Vrni končno razvrščeni seznam.
2. Iskalni algoritmi
C ponuja tudi orodja, potrebna za implementacijo različnih algoritmov iskanja, kot sta linearno iskanje in binarno iskanje. Ti algoritmi lahko hitro najdejo določene elemente v nizu podatkov, zaradi česar so uporabni za širok spekter aplikacij.
Obstaja veliko vrst iskalnih algoritmov.
To so: -
(i) Linearno iskanje : Osnovni algoritem iskanja, ki preiskuje vsak element v seznamu enega za drugim, dokler ne najde želenega elementa.
Algoritem za linearno iskanje: -
- Definirajte vhod za algoritem: Vhod za algoritem linearnega iskanja je seznam elementov (ali niz) in ciljni element, ki ga iščemo.
- Inicializirajte spremenljivko, imenovano 'index', na -1: ta spremenljivka bo uporabljena za shranjevanje indeksa ciljnega elementa, če bo najden.
- Preglejte seznam elementov: Začenši s prvim elementom, preverite vsakega elementa na seznamu enega za drugim.
- Primerjajte trenutni element z želenim elementom za oceno: Ohranite indeks trenutnega elementa v spremenljivki indeksa in zapustite zanko, če sta sodobni element in ciljni element enaka.
- Vrnite indeks ciljnega elementa: Ko je zanka končana, vrnite vrednost, shranjeno v spremenljivki indeksa. Če ciljni element ni najden, bo vrednost indeksa -1.
(ii) Binarno iskanje : Iskalni algoritem, ki deluje tako, da seznam razdeli na polovice in išče znotraj teh polovic, bo bolj verjetno vključil element.
Algoritem za binarno iskanje:-
- Vhod: razvrščen seznam n elementov in ciljni element x.
- Inicializirajte spremenljivke: nizki indeks nastavite na 0, visoki indeks na n-1 in srednji na (nizek+visok)/2.
- Zaženite zanko: Medtem ko je nizki indeks manjši ali enak visokemu indeksu, ponovite naslednje korake.
- Primerjajte srednji element z x: če je srednji element enak x, vrnite srednji indeks.
- Posodobite nizki ali visoki indeks: če je x večji od srednjega elementa, nizki indeks nastavite na srednji + 1. V nasprotnem primeru nastavite visoki indeks na srednji - 1.
- Posodobite srednji indeks: Srednji = (nizko+visoko)/2.
- Konec zanke: če je nizki indeks večji od visokega indeksa, potem x ni na seznamu in algoritem vrne napako.
- Izhod: Indeks x na seznamu ali sporočilo o napaki.
(iii) Iskanje najprej v globino : iskalni algoritem, ki pregleda vsako vejo, kolikor je to izvedljivo, preden se obrne.
Za iskanje v globino veljajo naslednje smernice:
- izberite začetno točko ali vozlišče grafa za začetek.
- Dodajte oznako obiska na prvo točko.
- Neposredno postavite začetno točko v sklad.
- Dokler sklad ni prazen, ponavljajte naslednja dejanja: -
- Odstranite vrhnjo točko sklada.
- Označite kot obiskano in vstavite v sklad vsakega neobiskanega soseda izstreljenega vozlišča.
- Nadaljujte s tem postopkom, dokler ne obiščete vseh točk v grafu.
- Ko so vsa vozlišča obiskana, je algoritem dokončan in na grafu se izvede iskanje najprej v globino.
(iv) Iskanje v širino : iskalni algoritem, ki razišče vse sosede vozlišča, preden se premakne na naslednjo raven.
Algoritem za iskanje v širino je:
- Začnite s korenskim vozliščem ali začetnim stanjem.
- Dodajte korensko vozlišče v čakalno vrsto.
- Preverite, ali je čakalna vrsta prazna; če da, potem prekinite algoritem.
- Vzemite prvi element iz čakalne vrste in ga označite kot obiskanega.
- Razširite sodobno vozlišče tako, da v čakalno vrsto dodate vse njegove neobiskane sosede.
- Dokler ne najdete želenega vozlišča ali dokler ni čakalna vrsta prazna, ponavljajte korake od 3 do 5.
- Vrni pot iz predhodnega stanja v ciljno stanje, če je ciljno vozlišče najdeno.
- Prekinite nabor pravil in sporočite, da ciljno stanje ni bilo identificirano, če je čakalna vrsta prazna.
(v) Interpolacijsko iskanje : iskalni algoritem, ki uporablja vrednosti iskanih elementov za oceno položaja v indeksu.
Pomembno je, da je niz enakomerno porazdeljen. V nasprotnem primeru je to algoritem.
Deluje po pričakovanjih.
Algoritem lahko povzamemo na naslednji način.
- Pridobite seznam vnosov in ključno vrednost za iskanje.
- Inicializirajte spodnje in zgornje spremenljivke na prvem in zadnjem indeksu seznama.
- Če je spodnja vrednost manjša ali enaka višji vrednosti, potem:-
- Izračunajte predvideno lokacijo z naslednjo formulo:
pos = nizka + ((visoka - nizka) / (arr[visoka] - arr[nizka])) * (x - arr[nizka]). - Vrni položaj, če je ocenjena vrednost položaja ključna vrednost.
- c) Če je ocenjena vrednost položaja manjša od ključne vrednosti, jo nastavite nižje.
Položaj + 1. - d) Če je vrednost ocenjene pozicije večja od nastavljene vrednosti ključa, pozicija - 1 navzgor.
- Izračunajte predvideno lokacijo z naslednjo formulo:
- Če vrednosti ključa ni mogoče najti, vrnite -1, da označite, da vrednosti ni na seznamu.
(vi) Preskočno iskanje : Metoda iskanja, ki ponavlja po seznamu v korakih s konstantno dolžino, dokler ne najde ustreznega elementa ali ugotovi, da ni več prisoten.
Algoritem iskanja skokov je naslednji:
- Najprej nastavite velikost skoka na kvadratni koren števila elementov polja.
- Nastavi spremenljivko z imenom 'current' na prvi element matrike.
- Ponavlja matriko tako, da skače po velikosti skoka, medtem ko povečuje spremenljivko, imenovano 'jump'.
- Nadaljujte z naslednjim skokom, če je obstoječi element manjši od želenega.
- Če je trenutni element večji od ciljnega elementa, izvedite linearno iskanje med trenutnim elementom in prejšnjim elementom skoka, da najdete ciljni element.
- Če ciljnega elementa ni v matriki, vrne -1, kar pomeni, da ni v matriki.
- Če je element najden, vrne indeks elementa v matriki.
3. Algoritmi grafov
Podpora C-ja za kazalce in podatkovne strukture, kot so polja in povezani seznami, ga naredi primernega za izvajanje algoritmov, ki manipulirajo z grafi, kot je iskanje najkrajše poti med dvema vozliščema v grafu.
Obstajajo različne vrste algoritmov grafov.
oni so:-
4. Kriptografski algoritmi
C podpira nizkonivojske operacije in učinkovito manipulacijo podatkov, zaradi česar je idealen za izvajanje algoritmov, ki se uporabljajo v kriptografiji, kot so algoritmi za šifriranje in dešifriranje podatkov.
Obstajajo različne vrste šifrirnih algoritmov.
To so: -
Prednosti algoritma
Algoritmi imajo številne prednosti.
oni so:-
Slabosti algoritma
Algoritmi so zelo uporabni za programiranje, vendar imajo algoritmi pomanjkljivosti.
niz nizov v programiranju c
oni so:-