Un algoritm este o secvență de instrucțiuni care sunt efectuate într-o secvență predeterminată pentru a rezolva o problemă sau a finaliza o lucrare. O funcție este un bloc de cod care poate fi apelat și executat din alte părți ale programului.
Un set de instrucțiuni pentru rezolvarea unei probleme sau desfășurarea unei anumite activități. În informatică, algoritmii sunt utilizați pentru o gamă largă de operațiuni, de la matematică fundamentală până la procesarea complicată a datelor.
Unul dintre algoritmii obișnuiți utilizați în C este algoritmul de sortare. Un algoritm de sortare aranjează o colecție de articole într-o anumită ordine, cum ar fi numeric sau alfabetic.
Există mulți algoritmi de sortare, fiecare cu avantaje și dezavantaje. Cei mai comuni algoritmi de sortare din C sunt sortarea rapidă, îmbinare și sortare.
Una dintre caracteristicile cheie ale C este suportul pointerului. Acest lucru permite manipularea eficientă a structurilor de date, cum ar fi matrice, cozi etc. Acest lucru îl face potrivit pentru implementarea algoritmilor care necesită manipulare complexă a datelor, cum ar fi sortarea și căutarea algoritmică.
Unul dintre exemplele celebre de bibliotecă software implementată în C este Standard Template Library (STL). Această bibliotecă oferă o mare varietate de algoritmi pentru sarcini precum sortarea, căutarea și manipularea structurilor de date.
Caracteristicile algoritmului
Acesta definește câteva caracteristici importante ale algoritmului, inclusiv:
funcția săgeată dactilografiată
Analiza algoritmului
Analiza algoritmică este procesul de evaluare a performanței algoritmului în termeni de eficiență, complexitate și alte criterii. De obicei, aceasta se face pentru a evalua mulți algoritmi și pentru a selecta soluția optimă pentru o anumită problemă sau un software.
Analiza algoritmilor implică de obicei măsurarea complexității lor în timp și spațiu.
Ca și în cazul complexității spațiului, care descrie cantitatea de memorie sau spațiu pe disc necesară, complexitatea timpului descrie cât timp un algoritm determină să realizeze o sarcină.
Există diferite moduri de a analiza complexitatea temporală a algoritmilor, cum ar fi notația Big O și Omega. Simbolul Omega oferă o limită superioară pentru complexitatea temporală a algoritmului, în timp ce simbolul Omega oferă o limită inferioară.
Pe lângă măsurarea complexității timpului și spațiului, analiza algoritmului include și alte criterii precum stabilitatea, paralelismul și scalabilitatea.
Acestea includ două tipuri de analiză.
sunt:-
- Analiza prealabilă.
- Analiza posterioara.
Analiza prealabila
Prior este o metodă de analiză a algoritmului care se concentrează pe estimarea performanței unui algoritm pe baza proprietăților sale matematice fără a executa efectiv algoritmul.
Această abordare vă permite să analizați complexitatea în timp și spațiu a algoritmilor și a altor metrici fără a fi nevoie să implementați și să rulați algoritmii.
Analiza posterioara
Analiza posterioară, pe de altă parte, este o metodă de analiză a algoritmului care execută de fapt algoritmul și măsoară performanța acestuia.
Această abordare oferă informații mai precise și detaliate despre performanța algoritmului, dar necesită implementarea și execuția algoritmului.
Complexitatea algoritmului
Complexitatea algoritmică este o măsură pentru a măsura eficiența și performanța algoritmului. Algoritmii sunt de obicei evaluați în termeni de timp și spațiu necesar pentru a rezolva o problemă sau pentru a atinge un anumit scop.
Doi factori sunt utilizați în complexitatea algoritmului.
sunt:-
- Factorul timp.
- Factorul spațial.
Factorul timp
masa din latex
- Cantitatea de timp de care are nevoie un algoritm pentru a efectua o sarcină este denumită complexitate în timp. De obicei, este măsurată prin numărul de operații sau pași pe care trebuie să îi efectueze un algoritm pentru a rezolva o problemă.
- Complexitatea în timp a unui algoritm este importantă deoarece determină cât timp durează pentru a se executa și poate avea un impact semnificativ asupra performanței programului și sistemului.
- Complexitatea de timp a unui algoritm poate fi exprimată folosind notația Big O, o modalitate de a exprima o limită superioară a complexității de timp a unui algoritm.
- Un algoritm cu complexitate temporală O(n) înseamnă că timpul necesar rulării algoritmului este direct proporțional cu dimensiunea datelor de intrare (n).
- Alte complexități de timp comune sunt complexitatea pătratică O(n^2) și complexitatea logaritmică O(log n).
Analiza spatiala
- Pe de altă parte, complexitatea spațiului se referă la cantitatea de memorie sau spațiu de stocare necesară pentru a executa algoritmul.
- Acest lucru este important deoarece determină numărul de resurse necesare pentru a rula algoritmi care pot afecta performanța generală a aplicației sau a sistemului dumneavoastră.
- Dacă complexitatea spațială a algoritmului este O(n), acesta utilizează o cantitate de memorie care crește liniar cu dimensiunea intrării.
- Dacă algoritmul are complexitatea spațiului O(1), acesta utilizează o cantitate fixă de memorie, indiferent de dimensiunea intrării.
Cum se scrie un algoritm
1. Mai întâi definiți problema pe care doriți să o rezolve algoritmul.
De exemplu, să presupunem că vrem să scriem un algoritm pentru a găsi valoarea maximă dintr-o listă de numere.
2. Împărțiți problema în pași mai mici și ușor de gestionat.
- Inițializați variabila „max” la prima valoare din listă.
- Pentru fiecare valoare ulterioară din listă, comparați cu „max”.
- Dacă valoarea este mai mare decât „max”, setați „max” la acea valoare.
- Continuați să faceți acest lucru până când fiecare valoare din listă a fost comparată.
- Returnează valoarea „max” finală.
3. Scrieți algoritmul în pseudocod sau într-un limbaj de programare.
Algoritm scris in pseudocod:
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. Testează-ți algoritmul pentru a te asigura că este corect și eficient.
Puteți testa algoritmul introducând diferite liste de numere și verificând dacă returnează valoarea maximă corectă. De asemenea, puteți analiza complexitatea temporală a algoritmului pentru a determina cât de bine se scalează pentru intrări mai mari.
Exemplu:-
Intrare: [1, 5, 2, 7, 3]
Ieșire: 7.
Explicație: 7 este valoarea maximă din listă.
5. Optimizați algoritmul.
Căutați modalități de optimizare a algoritmilor pentru a-i face mai rapidi și mai eficienți. Aceasta poate implica modificarea pseudocodului sau implementarea unor structuri de date sau algoritmi mai eficienți.
Scrierea de bază a algoritmilor
Exemplu: - Suma a două numere întregi.
Pasul 1 - Incepe
Pasul 2 - Declarați trei numere întregi a, b, c
Pasul 3 - Definiți valorile lui a și b
Pasul 4 - Adăugați valorile lui a și b
Pasul 5 - Salvați rezultatul pasului 4 din c
ce este s în python
Pasul 6 - Imprimare c
Pasul 7 - Stop
Tip de algoritmi utilizați în limbajul C.
1. Algoritmi de sortare
C oferă un set bogat de tipuri de date și operatori care pot fi utilizați pentru a implementa diverși algoritmi de sortare, cum ar fi sortarea cu bule, sortarea prin inserție și sortarea rapidă.
Acești algoritmi sunt utili în multe aplicații, deoarece pot fi utilizați pentru a sorta date de diferite dimensiuni și tipuri.
Există diferiți algoritmi de sortare.
sunt:-
(i) Sortare cu bule: Un algoritm de sortare necomplicat care compară în mod repetat componentele din apropiere și le dezactivează dacă nu sunt în ordine.
Algoritmul pentru sortarea cu bule este: -
- Începeți cu o listă nesortată de elemente.
- Comparați primele două elemente din listă. Dacă primul element este mai mare decât al doilea element, schimbați-le.
- Treceți la următoarea pereche de elemente și repetați pasul 2 până când ajungeți la sfârșitul listei.
- Pentru fiecare articol din listă, repetați pașii 2 și 3 încă o dată. care se numește treceri.
- Repetați pașii 2-4 pentru întreaga listă. Pe măsură ce repeți trecerile, elementele vor „bulbore” în poziția lor corectă în lista sortată.
- Odată ce o trecere este finalizată și nu se fac schimburi, lista este sortată, iar algoritmul se poate opri.
- Se returnează lista finală sortată.
(ii) Sortare prin inserare : o metodă de sortare care creează o listă sortată câte un element individual, plasând fiecare în locul potrivit.
Algoritmul pentru sortarea prin inserare este:
- Inițializați o listă sortată goală și o listă nesortată a elementelor de sortat.
- Primul membru din lista nesortată trebuie luat și plasat în poziția corespunzătoare în lista sortată.
- Repetați pasul 2 pentru fiecare element următor din lista nesortată.
- Comparați elementul curent cu elementele din lista sortată, începând cu elementul imediat din stânga.
- Schimbați cele două elemente dacă elementul curent este mai mic decât elementul din stânga sa.
- Dacă elementul curent este mai mare decât elementul din stânga sa, introduceți-l în poziția corectă în lista sortată.
- Repetați pașii 4-6 pentru fiecare element următor din lista nesortată.
- Odată ce toate elementele au fost procesate, lista sortată va conține toate elementele în ordinea corectă.
- Procesul de sortare este finalizat.
(iii) Sortarea selecției : o metodă de sortare care începe în mod constant lista sortată cu cel mai mic detaliu din lista neordonată.
Algoritmul pentru sortarea selecției este:
- Începeți prin a seta elementul principal al listei ca element min.
- Repetați elementele rămase din listă, comparând fiecare cu minimul curent.
- Setați un nou minim dacă se constată că un element este mai mic decât cel existent.
- Schimbați minimul curent la primul element al listei ori de câte ori ajunge la final.
- Pentru porțiunea rămasă nesortată a listei, repetați pașii 2-4, dar începeți cu al doilea element din listă (deoarece primul element este deja sortat).
- Continuați să sortați lista în acest mod până când este sortată.
(iv) Sortare rapidă : un algoritm de sortare împărțiți și cuceriți care alege un element pivot și împarte lista în subliste, în funcție de dacă elementele sunt mai puține sau mai multe decât pivotul. După aceea, sublistele sunt sortate în mod repetat până când lista completă este sortată.
Algoritmul pentru sortarea rapidă este: -
- Alegeți un element pivot din listă. Acesta este de obicei primul element, dar poate fi și un element aleatoriu sau mediana listei.
- Împărțiți lista în două subliste: una care conține elemente mai mici decât pivotul și una care conține elemente mai mari decât pivotul.
- Sortați recursiv sublista care conține elemente mai mici decât pivotul utilizând același proces.
- Utilizați aceeași procedură pentru a sorta recursiv sublista de intrări mai mare decât pivotul.
- Concatenați sublistele sortate cu elementul pivot între ele pentru a forma o listă complet sortată.
- Returnează lista complet sortată.
(v) Merge sort : Algoritmul de sortare divide-and-conquer împarte lista în două jumătăți, sortează fiecare jumătate și apoi îmbină cele două jumătăți în ordine sortată.
Algoritmul de sortare fuzionare:
- Faceți două subliste din listă: una cu elemente sub pivot și una cu elemente deasupra pivotului.
- Produce o nouă sublistă sortată prin îmbinarea iterativă a sublistelor până când există o singură sublistă. Aceasta va fi lista dvs. sortată.
- Pași pentru a fuziona două subdirectoare: -
- Creați o listă goală pentru a păstra elementele sortate.
- Compară primul element al fiecărei subliste.
- Adaugă elementul mai mic la noua listă și îl elimină din sublista părinte.
- Repetați pașii 2 și 3 până când o listă este complet goală.
- Adaugă elementele rămase din alte subliste la o nouă listă.
- Înlocuiește sublista îmbinată cu noua listă sortată.
- Repetați acest proces până când toate sublistele sunt îmbinate într-o singură listă sortată.
(vi) Sortare în grămada : un algoritm de sortare care sortează elemente folosind o structură de date numită heap.
Acesta este algoritmul de clasificare:
- Stivuiți restul elementelor. Pornind de la rădăcină, fiecare nod este comparat cu copiii săi, schimbând nodurile cu copiii mai mari până când proprietatea maxim heap este satisfăcută.
- Repetați pașii 2 și 3 cu elementele nou stivuite, cu excepția ultimului element în poziția corectă.
- Repetați acest proces până când rămâne un singur element în stivă. Acest lucru este acum sortat.
(vii) Sortare Radix : Un algoritm de sortare care sortează elementele pe baza cifrelor sau cifrelor reprezentării lor binare.
Algoritmul pentru sortarea Radix este:
bou vs taur
- determinați câte cifre sunt conținute în cel mai mare element al listei de intrare.
- Inițializați o variabilă, să spunem locul cifrei, la 1, care reprezintă locul cifrei curente.
- Creați o listă goală pentru fiecare valoare posibilă a cifrei de la 0 la 9.
- Repetați lista de intrare și adăugați fiecare element la lista corespunzătoare, pe baza valorii locului cifrei curente.
- Concatenați toate listele împreună pentru a forma noua listă în ordinea listelor de cifre.
- Înmulțiți digitPlace cu 10 pentru a trece la următoarea cifră.
- Repetați pașii 4-6 pentru fiecare loc de cifră până când au fost luate în considerare toate cifrele din elementul cel mai mare.
- Lista finală va fi sortată în ordine crescătoare după cifrele elementelor.
- Returnează lista finală sortată.
2. Algoritmi de căutare
C oferă, de asemenea, instrumentele necesare pentru a implementa o varietate de algoritmi de căutare, cum ar fi căutarea liniară și căutarea binară. Acești algoritmi pot găsi rapid elemente specifice într-un set de date, făcându-le utile pentru o gamă largă de aplicații.
Există multe tipuri de algoritmi de căutare.
Sunt:-
(i) Căutare liniară : Un algoritm de căutare de bază care examinează fiecare articol din listă unul câte unul până când găsește articolul dorit.
Algoritm pentru căutare liniară: -
- Definiți intrarea pentru algoritm: Intrarea pentru un algoritm de căutare liniară este o listă de elemente (sau o matrice) și un element țintă pe care îl căutăm.
- Inițializați o variabilă numită „index” la -1: Această variabilă va fi folosită pentru a stoca indexul elementului țintă dacă este găsit.
- Buclă prin lista de elemente: Pornind de la primul element, verificați fiecare element din listă unul câte unul.
- Comparați elementul prezent cu elementul dorit pentru evaluare: Păstrați indicele elementului curent în variabila index și ieșiți din buclă dacă elementul modern și elementul obiectiv sunt identice.
- Returnează indexul elementului țintă: după ce bucla se termină, returnează valoarea stocată în variabila index. Dacă elementul țintă nu este găsit, valoarea indexului va fi -1.
(ii) Căutare binară : un algoritm de căutare care funcționează prin împărțirea listei în jumătăți și căutările în cadrul acestor jumătăți sunt mai probabil să includă elementul.
Algoritm pentru căutare binară: -
- Intrare: o listă sortată de n elemente și un element țintă x.
- Inițializați variabile: setați indicele scăzut la 0, indicele ridicat la n-1 și mediu la (scăzut + ridicat)/2.
- Începeți o buclă: în timp ce indicele scăzut este mai mic sau egal cu indicele ridicat, repetați pașii următori.
- Comparați elementul din mijloc cu x: dacă elementul din mijloc este egal cu x, returnați indicele din mijloc.
- Actualizați indicele scăzut sau ridicat: dacă x este mai mare decât elementul mijlociu, setați indicele scăzut la mijloc + 1. În caz contrar, setați indicele ridicat la mijloc - 1.
- Actualizați indicele mijlociu: Mid = (scăzut + ridicat)/2.
- Sfârșitul buclei: Dacă indicele scăzut este mai mare decât indicele ridicat, atunci x nu este în listă, iar algoritmul returnează un eșec.
- Ieșire: indicele lui x din listă sau mesajul de eșec.
(iii) Căutare în profunzime : Un algoritm de căutare care examinează fiecare ramură cât de mult este posibil înainte de a se întoarce.
Următoarele recomandări se aplică căutării în profunzime:
- selectați vârful sau nodul de pornire al graficului pentru a începe.
- Adăugați un semn de vizită la primul vârf.
- Așezați direct vârful de început într-o stivă.
- Până când stiva este goală, repetați următoarele acțiuni: -
- Îndepărtați vârful superior al stivei.
- Marcați ca vizitat și introduceți în stivă fiecare vecin nevizitat al vârfului pop.
- Continuați acest proces până când toate vârfurile din grafic au fost vizitate.
- Odată ce toate nodurile au fost vizitate, algoritmul este complet și se efectuează o căutare în profunzime pe grafic.
(iv) Căutarea pe lățimea întâi : Un algoritm de căutare care explorează toți vecinii unui nod înainte de a trece la nivelul următor.
Algoritmul pentru căutarea pe lățimea întâi este: -
- Începeți cu nodul rădăcină sau cu starea inițială.
- Adăugați nodul rădăcină la o coadă.
- Verificați dacă coada este goală; dacă da, atunci închideți algoritmul.
- Luați primul element din coadă și marcați-l ca vizitat.
- Amplifică nodul contemporan adăugând toți vecinii săi nevizitați la coadă.
- Până când nodul dorit este localizat sau coada este goală, repetați pașii de la 3 la 5.
- Întoarceți calea de la starea preliminară la starea țintă dacă este găsit nodul obiectiv.
- Închideți setul de reguli și raportați că starea obiectivului nu a fost identificată dacă coada este goală.
(v) Căutare prin interpolare : Un algoritm de căutare care utilizează valorile elementelor căutate pentru a estima poziția în index.
Este important ca matricea să fie distribuită uniform. Altfel, este un algoritm.
Funcționează conform așteptărilor.
Algoritmul poate fi rezumat după cum urmează.
- Obțineți lista de intrare și valoarea cheii pentru a căuta.
- Inițializați variabilele inferioare și superioare la primul și ultimul indici ai listei.
- Dacă valoarea inferioară este mai mică sau egală cu valoarea mai mare, atunci:
- Calculați locația estimată folosind următoarea formulă:
pos = scăzut + ((ridicat - scăzut) / (arr[high] - arr[low])) * (x - arr[low]). - Returnați poziția dacă valoarea estimată a poziției este o valoare cheie.
- c) Dacă valoarea estimată a poziţiei este mai mică decât valoarea cheii, setaţi-o mai jos.
Poziție + 1. - d) Dacă valoarea poziţiei estimate este mai mare decât valoarea setată a tastei, poziţia - 1 sus.
- Calculați locația estimată folosind următoarea formulă:
- Dacă valoarea cheii nu este găsită, returnați -1 pentru a indica faptul că valoarea nu este în listă.
(vi) Salt de căutare : O metodă de căutare care iterează peste listă în pași de lungime constantă până când găsește elementul relevant sau determină că acesta nu mai este prezent.
Algoritmul de căutare prin salt este următorul:
- Mai întâi, setați dimensiunea saltului la rădăcina pătrată a numărului de elemente ale matricei.
- Setează o variabilă numită „curent” la primul element al matricei.
- Iterează peste matrice, sărind după dimensiunea saltului în timp ce incrementează o variabilă numită „salt”.
- Treceți la următorul salt dacă elementul existent este mai mic decât elementul dorit.
- Dacă elementul curent este mai mare decât elementul țintă, efectuați o căutare liniară între elementul curent și elementul de salt anterior pentru a găsi elementul țintă.
- Dacă elementul țintă nu este găsit în matrice, returnează -1 pentru a indica faptul că nu se află în matrice.
- Dacă elementul este găsit, returnează indexul elementului în matrice.
3. Algoritmi grafici
Suportul lui C pentru pointeri și structuri de date, cum ar fi matrice și liste legate, îl face potrivit pentru implementarea algoritmilor care manipulează grafice, cum ar fi găsirea celei mai scurte căi între două noduri dintr-un grafic.
Există diferite tipuri de algoritmi grafici.
sunt:-
model de proiectare din fabrică
4. Algoritmi criptografici
C acceptă operațiuni de nivel scăzut și manipulare eficientă a datelor, făcându-l ideal pentru implementarea algoritmilor utilizați în criptografie, cum ar fi algoritmii de criptare și decriptare a datelor.
Există diferite tipuri de algoritmi de criptare.
Sunt:-
Avantajele algoritmului
Algoritmii au multe avantaje.
sunt:-
Dezavantajele algoritmului
Algoritmii sunt foarte utili pentru programare, dar algoritmii au dezavantaje.
sunt:-