En algoritme er en sekvens af instruktioner, der udføres i en forudbestemt rækkefølge for at løse et problem eller fuldføre et arbejde. En funktion er en kodeblok, der kan kaldes og udføres fra andre dele af programmet.
Et sæt instruktioner til at løse et problem eller udføre en bestemt aktivitet. Inden for datalogi bruges algoritmer til en bred vifte af operationer, fra grundlæggende matematik til indviklet databehandling.
En af de almindelige algoritmer, der bruges i C, er sorteringsalgoritmen. En sorteringsalgoritme arrangerer en samling af elementer i en bestemt rækkefølge, såsom numerisk eller alfabetisk.
Der er mange sorteringsalgoritmer, hver med fordele og ulemper. De mest almindelige sorteringsalgoritmer i C er quicksort, fletning og sortering.
En af nøglefunktionerne ved C er pointerunderstøttelse. Dette muliggør effektiv manipulation af datastrukturer såsom arrays, køer osv. Dette gør den velegnet til implementering af algoritmer, der kræver kompleks datamanipulation, såsom sortering og algoritmisk søgning.
Et af de berømte eksempler på softwarebibliotek implementeret i C er Standard Template Library (STL). Dette bibliotek giver en bred vifte af algoritmer til opgaver såsom sortering, søgning og manipulation af datastrukturer.
Funktioner af algoritmen
Den definerer flere vigtige funktioner i algoritmen, herunder:
Algoritmeanalyse
Algoritmisk analyse er processen med at evaluere algoritmens ydeevne i form af effektivitet, kompleksitet og andre kriterier. Dette gøres typisk for at evaluere mange algoritmer og vælge den optimale løsning til et bestemt problem eller en software.
Analyse af algoritmer involverer normalt måling af deres tid og rum kompleksitet.
Som med pladskompleksitet, der beskriver mængden af hukommelse eller diskplads, der er nødvendig, beskriver tidskompleksitet, hvor længe en algoritme bestemmer at udføre en opgave.
Der er forskellige måder at analysere tidskompleksiteten af algoritmer, såsom Big O og Omega notation. Omega-symbolet giver en øvre grænse for algoritmens tidskompleksitet, mens Omega-symbolet giver en nedre grænse.
Ud over måling af tid og rumkompleksitet omfatter algoritmeanalyse også andre kriterier såsom stabilitet, parallelitet og skalerbarhed.
De omfatter to typer analyser.
de er:-
- Forudgående analyse.
- Posterior analyse.
Forudgående analyse
Prior er en metode til algoritmeanalyse, der fokuserer på at estimere ydeevnen af en algoritme baseret på dens matematiske egenskaber uden faktisk at udføre algoritmen.
Denne tilgang giver dig mulighed for at analysere tids- og rumkompleksiteten af algoritmer og andre målinger uden at skulle implementere og køre algoritmerne.
Posterior analyse
Posterior analyse er på den anden side en metode til algoritmeanalyse, der rent faktisk udfører algoritmen og måler dens ydeevne.
Denne tilgang giver mere præcise og detaljerede oplysninger om algoritmens ydeevne, men kræver implementering og eksekvering af algoritmen.
Algoritme kompleksitet
Algoritmisk kompleksitet er et mål til at måle effektiviteten og ydeevnen af algoritmen. Algoritmer evalueres normalt i forhold til den tid og det rum, der kræves for at løse et problem eller opnå et specifikt mål.
To faktorer bruges i kompleksiteten af algoritmen.
de er:-
- Tidsfaktor.
- Plads faktor.
Tidsfaktor
- Den tid, en algoritme skal bruge for at udføre en opgave, kaldes tidskompleksitet. Den måles normalt ved antallet af operationer eller trin, en algoritme skal udføre for at løse et problem.
- Tidskompleksiteten af en algoritme er vigtig, fordi den bestemmer, hvor lang tid det tager at udføre og kan have en væsentlig indflydelse på programmets og systemets ydeevne.
- Tidskompleksiteten af en algoritme kan udtrykkes ved hjælp af Big O notation, en måde at udtrykke en øvre grænse for tidskompleksiteten af en algoritme.
- En algoritme med tidskompleksitet O(n) betyder, at den tid, der kræves for at køre algoritmen, er direkte proportional med størrelsen af inputdataene (n).
- Andre almindelige tidskompleksiteter er O(n^2) kvadratisk kompleksitet og O(log n) logaritmisk kompleksitet.
Rumanalyse
- På den anden side refererer pladskompleksitet til mængden af hukommelse eller lagerplads, der kræves for at udføre algoritmen.
- Dette er vigtigt, fordi det bestemmer antallet af ressourcer, der kræves for at køre algoritmer, der kan påvirke den overordnede ydeevne af din applikation eller dit system.
- Hvis rumkompleksiteten af algoritmen er O(n), bruger den en mængde hukommelse, der vokser lineært med størrelsen af inputtet.
- Hvis algoritmen har O(1) pladskompleksitet, bruger den en fast mængde hukommelse uanset størrelsen på inputtet.
Hvordan man skriver en algoritme
1. Definer først det problem, du vil have algoritmen til at løse.
Antag for eksempel, at vi vil skrive en algoritme til at finde den maksimale værdi fra en liste med tal.
2. Opdel problemet i mindre, håndterbare trin.
- Initialiser 'max'-variablen til den første værdi på listen.
- For hver efterfølgende værdi på listen, sammenlign med 'max'.
- Hvis værdien er større end 'max', skal du indstille 'max' til den værdi.
- Fortsæt med at gøre dette, indtil hver værdi på listen er blevet sammenlignet.
- Returnerer den endelige 'max' værdi.
3. Skriv din algoritme i pseudokode eller et programmeringssprog.
præity zinta
Algoritme skrevet i pseudokode:
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. Test din algoritme for at sikre, at den er korrekt og effektiv.
Du kan teste algoritmen ved at indtaste forskellige lister med tal og kontrollere, at den returnerer den maksimale korrekte værdi. Du kan også analysere tidskompleksiteten af din algoritme for at bestemme, hvor godt den skaleres til større input.
Eksempel:-
Input: [1, 5, 2, 7, 3]
Udgang: 7.
Forklaring: 7 er den maksimale værdi på listen.
5. Optimer algoritmen.
Se efter måder at optimere algoritmer for at gøre dem hurtigere og mere effektive. Dette kan involvere ændring af pseudokode eller implementering af mere effektive datastrukturer eller algoritmer.
Grundlæggende skrivning af algoritmer
Eksempel: - Summen af to heltal.
Trin 1 - Kom igang
Trin 2 - Erklær tre heltal a, b, c
Trin 3 - Definer værdierne af a og b
Trin 4 - Tilføj værdierne af a og b
Trin 5 - Gem output fra trin 4 i c
Trin 6 - Tryk c
Trin 7 - Hold op
Type af algoritmer, der bruges i C-sprog.
1. Sorteringsalgoritmer
C giver et rigt sæt af datatyper og operatorer, der kan bruges til at implementere forskellige sorteringsalgoritmer såsom boblesortering, indsættelsessortering og hurtig sortering.
Disse algoritmer er nyttige i mange applikationer, fordi de kan bruges til at sortere data af forskellige størrelser og typer.
Der er forskellige sorteringsalgoritmer.
de er:-
(i) Boblesortering: En ukompliceret sorteringsalgoritme, der sammenligner komponenter i nærheden gentagne gange og skifter dem ud, hvis de er ude af drift.
hvordan man konverterer heltal til streng java
Algoritmen for boblesortering er: -
- Start med en usorteret liste over elementer.
- Sammenlign de to første elementer på listen. Hvis det første element er større end det andet element, skal du bytte dem.
- Gå videre til det næste par elementer, og gentag trin 2, indtil slutningen af listen er nået.
- Gentag trin 2 og 3 igen for hvert punkt på listen. det kaldes pas.
- Gentag trin 2-4 for hele listen. Når du gentager afleveringerne, vil elementerne 'boble op' til deres korrekte position i den sorterede liste.
- Når et pass er gennemført, og der ikke er foretaget bytte, sorteres listen, og algoritmen kan stoppe.
- Den endelige sorterede liste returneres.
(ii) Indsættelsessortering : en sorteringsmetode, der opretter en sorteret liste med ét enkelt element ad gangen ved at placere hvert enkelt på det passende sted.
Algoritmen for indsættelsessortering er: -
- Initialiser en tom sorteret liste og en usorteret liste over de elementer, der skal sorteres.
- Det første medlem fra den usorterede liste skal tages og placeres i den passende position i den sorterede liste.
- Gentag trin 2 for hvert efterfølgende element i den usorterede liste.
- Sammenlign det aktuelle element med elementerne i den sorterede liste, startende med elementet umiddelbart til venstre.
- Skift de to elementer, hvis det aktuelle element er mindre end elementet til venstre for det.
- Hvis det aktuelle element er større end elementet til venstre for det, skal du indsætte det på dens korrekte position i den sorterede liste.
- Gentag trin 4-6 for hvert efterfølgende element i den usorterede liste.
- Når alle elementer er blevet behandlet, vil den sorterede liste indeholde alle elementer i den rigtige rækkefølge.
- Sorteringsprocessen er afsluttet.
(iii) Udvælgelsessortering : en sorteringsmetode, der konsekvent starter den sorterede liste med den mindste detalje fra den uordnede liste.
Algoritmen for udvælgelsessortering er: -
- Begynd med at indstille det primære element i listen som min-elementet.
- Gentag gennem de resterende elementer på listen, og sammenlign hver enkelt med det aktuelle minimum.
- Indstil et nyt minimum, hvis et element viser sig at være mindre end det eksisterende.
- Skift det aktuelle minimum til det første element på listen, når det når sin konklusion.
- For den resterende usorterede del af listen, gentag trin 2-4, men start med det andet punkt på listen (da det første element allerede er sorteret).
- Fortsæt med at sortere listen på denne måde, indtil det hele er sorteret.
(iv) Hurtig sortering : En opdel-og-hersk sorteringsalgoritme, der vælger et pivotelement og opdeler listen i underlister afhængigt af om elementerne er færre end eller flere end pivoten. Derefter sorteres underlisterne gentagne gange, indtil hele listen er sorteret.
Algoritmen for hurtig sortering er: -
- Vælg et pivotelement fra listen. Dette er typisk det første element, men det kan også være et tilfældigt element eller medianen af listen.
- Opdel listen i to underlister: en indeholdende elementer mindre end pivoten og en indeholdende elementer større end pivoten.
- Sorter rekursivt underlisten, der indeholder elementer, der er mindre end pivoten, ved hjælp af den samme proces.
- Brug den samme procedure til rekursivt at sortere underlisten over poster, der er større end pivoten.
- Sammensæt de sorterede underlister med pivotelementet imellem for at danne en fuldt sorteret liste.
- Returner den fuldt sorterede liste.
(v) Lot går : Opdel-og-hersk-sorteringsalgoritmen opdeler listen i to halvdele, sorterer hver halvdel og fletter derefter de to halvdele i sorteret rækkefølge.
Flet-sorteringsalgoritme:
- Lav to underlister ud af listen: en med elementer under pivoten og en med elementer over pivoten.
- Producerer en ny sorteret underliste ved iterativt at flette underlister, indtil der kun eksisterer én underliste. Dette vil være din sorterede liste.
- Trin til at flette to undermapper:-
- Opret en tom liste til at indeholde de sorterede elementer.
- Sammenligner det første element i hver underliste.
- Tilføjer det mindre element til den nye liste og fjerner det fra den overordnede underliste.
- Gentag trin 2 og 3, indtil en liste er helt tom.
- Tilføjer de resterende elementer fra andre underlister til en ny liste.
- Erstatter den flettede underliste med den nye sorterede liste.
- Gentag denne proces, indtil alle underlister er slået sammen til én sorteret liste.
(vi) Dyngesortering : En sorteringsalgoritme, der sorterer elementer ved hjælp af en datastruktur kaldet heap.
Dette er klassifikationsalgoritmen:
- Stable resten af elementerne. Startende fra roden sammenlignes hver node med dens børn, og bytter noder med deres ældre børn, indtil max heap-egenskaben er opfyldt.
- Gentag trin 2 og 3 med de nyligt stablede elementer, bortset fra det sidste element i den korrekte position.
- Gentag denne proces, indtil der kun er ét element tilbage i stakken. Dette er nu ordnet.
(vii) Radix sortering : En sorteringsalgoritme, der sorterer elementer baseret på cifrene eller cifrene i deres binære repræsentation.
Algoritmen for Radix-sortering er: -
- bestemme, hvor mange cifre der er indeholdt i inputlistens største element.
- Initialiser en variabel, f.eks. ciffersted, til 1, som repræsenterer det aktuelle ciffersted.
- Opret en tom liste for hver mulig cifferværdi fra 0 til 9.
- Gentag gennem inputlisten og tilføj hvert element til den relevante liste baseret på værdien af det aktuelle ciffersted.
- Sammensæt alle listerne for at danne den nye liste i rækkefølgen af cifferlisterne.
- Multiplicer cifferPlacer med 10 for at flytte til det næste ciffersted.
- Gentag trin 4-6 for hvert ciffersted, indtil alle cifre i det største element er blevet taget i betragtning.
- Den endelige liste vil blive sorteret i stigende rækkefølge efter cifrene i elementerne.
- Returner den endelige sorterede liste.
2. Søgealgoritmer
C giver også de nødvendige værktøjer til at implementere en række søgealgoritmer, såsom lineær søgning og binær søgning. Disse algoritmer kan hurtigt finde specifikke elementer i et datasæt, hvilket gør dem nyttige til en lang række applikationer.
Der er mange typer søgealgoritmer.
De er:-
(i) Lineær søgning : En grundlæggende søgealgoritme, der undersøger hvert element i listen én efter én, indtil den finder det ønskede element.
Algoritme til lineær søgning:-
- Definer input for algoritmen: Input for en lineær søgealgoritme er en liste over elementer (eller et array) og et målelement, vi søger efter.
- Initialiser en variabel kaldet 'indeks' til -1: Denne variabel vil blive brugt til at gemme indekset for målelementet, hvis det bliver fundet.
- Gå gennem listen over elementer: Start fra det første element, tjek hvert element på listen et efter et.
- Sammenlign det nuværende element med det ønskede element til evaluering: Hold indekset for det aktuelle element i indeksvariablen og forlad loopet, hvis det moderne element og målelementet er identiske.
- Returner indekset for målelementet: Når løkken er fuldført, returneres værdien, der er gemt i indeksvariablen. Hvis målelementet ikke findes, vil værdien af indekset være -1.
(ii) Binær søgning : En søgealgoritme, der fungerer ved at opdele fortegnelsen i halvdele og søgninger inden for disse halvdele, er mere tilbøjelige til at inkludere elementet.
Algoritme til binær søgning:-
- Input: En sorteret liste med n elementer og et målelement x.
- Initialiser variabler: Indstil det lave indeks til 0, det høje indeks til n-1 og mellem til (lav+høj)/2.
- Start en loop: Mens det lave indeks er mindre end eller lig med det høje indeks, skal du gentage følgende trin.
- Sammenlign det midterste element med x: Hvis det midterste element er lig med x, returner det midterste indeks.
- Opdater det lave eller det høje indeks: Hvis x er større end det midterste element, skal du indstille det lave indeks til midt + 1. Ellers skal du indstille det høje indeks til mellem - 1.
- Opdater midtindekset: Mid = (lav+høj)/2.
- Slut på sløjfen: Hvis det lave indeks er større end det høje indeks, er x ikke på listen, og algoritmen returnerer en fejl.
- Output: Indekset for x i listen eller fejlmeddelelsen.
(iii) Dybde-første søgning : En søgealgoritme, der undersøger hver gren så vidt det er muligt, før den vender rundt.
Følgende retningslinjer gælder for dybde-først-søgning:
- vælg grafens startpunkt eller knudepunkt til at starte med.
- Tilføj et besøgsmærke til det første toppunkt.
- Placer det begyndende toppunkt direkte i en stak.
- Indtil stakken er tom, skal du gentage følgende handlinger: -
- Fjern stakkens øverste toppunkt.
- Markér som besøgt, og indsæt hver ubesøgt nabo til det knækkede vertex i stakken.
- Fortsæt denne proces, indtil alle hjørner i grafen er blevet besøgt.
- Når alle hjørner er besøgt, er algoritmen færdig, og en dybde-første søgning udføres på grafen.
(iv) Bredde-først søgning : En søgealgoritme, der udforsker alle naboerne til en node, før den går til næste niveau.
Algoritmen for bredde-først søgning er: -
- Start med rodnoden eller starttilstanden.
- Tilføj rodnoden til en kø.
- Tjek om køen er tom; hvis ja, afslut algoritmen.
- Tag det første element fra køen og marker det som besøgt.
- Forstærk den moderne node ved at tilføje alle dens ubesøgte naboer til køen.
- Gentag trin 3 til 5, indtil den ønskede node er lokaliseret, eller køen er tom.
- Returner stien fra den foreløbige tilstand til måltilstanden, hvis målknuden er fundet.
- Afslut regelsættet og rapporter, at måltilstanden ikke blev identificeret, hvis køen er tom.
(v) Interpolationssøgning : En søgealgoritme, der bruger værdierne af de søgte elementer til at estimere positionen i indekset.
Det er vigtigt, at arrayet er jævnt fordelt. Ellers er det en algoritme.
Det fungerer som forventet.
Algoritmen kan opsummeres som følger.
- Få inputlisten og nøgleværdien for at søge.
- Initialiser de nederste og øvre variable ved det første og sidste indeks på listen.
- Hvis den nedre værdi er mindre end eller lig med den højere værdi, så :-
- Beregn den anslåede placering ved hjælp af følgende formel:
pos = lav + ((høj - lav) / (arr[høj] - arr[lav])) * (x - arr[lav]). - Returner positionen, hvis den estimerede positionsværdi er en nøgleværdi.
- c) Hvis den estimerede positionsværdi er mindre end nøgleværdien, skal den indstilles lavere.
Position + 1. - d) Hvis værdien af den estimerede position er større end nøglen Indstil værdi, position - 1 op.
- Beregn den anslåede placering ved hjælp af følgende formel:
- Hvis nøgleværdien ikke findes, skal du returnere -1 for at angive, at værdien ikke er på listen.
(vi) Spring søgning : En søgemetode, der itererer over listen i trin med konstant længde, indtil den finder det relevante element eller bestemmer, at det ikke længere er til stede.
Springsøgningsalgoritmen er som følger:
- Indstil først springstørrelsen til kvadratroden af antallet af array-elementer.
- Indstiller en variabel ved navn 'aktuel' til det første element i arrayet.
- Itererer over arrayet ved at hoppe efter springstørrelse, mens en variabel kaldet 'jump' øges.
- Gå videre til følgende spring, hvis det eksisterende element er mindre end det ønskede element.
- Hvis det aktuelle element er større end målelementet, skal du udføre en lineær søgning mellem det aktuelle element og det forrige springelement for at finde målelementet.
- Hvis målelementet ikke findes i arrayet, returnerer det -1 for at angive, at det ikke er i arrayet.
- Hvis elementet findes, returnerer det elementets indeks i arrayet.
3. Grafalgoritmer
C's understøttelse af pointere og datastrukturer såsom arrays og linkede lister gør den velegnet til at implementere algoritmer, der manipulerer grafer, såsom at finde den korteste vej mellem to noder i en graf.
Der findes forskellige typer grafalgoritmer.
de er:-
4. Kryptografiske algoritmer
C understøtter operationer på lavt niveau og effektiv datamanipulation, hvilket gør den ideel til implementering af algoritmer, der bruges i kryptografi, såsom datakryptering og dekrypteringsalgoritmer.
Der findes forskellige typer krypteringsalgoritmer.
verilog parameter
De er:-
Fordele ved algoritmen
Algoritmer har mange fordele.
de er:-
Ulemper ved algoritmen
Algoritmer er meget nyttige til programmering, men algoritmer har ulemper.
de er:-