TechCodeview

En algoritm är en sekvens av instruktioner som utförs i en förutbestämd sekvens för att lösa ett problem eller slutföra ett arbete. En funktion är ett kodblock som kan anropas och exekveras från andra delar av programmet.

En uppsättning instruktioner för att lösa ett problem eller utföra en viss aktivitet. Inom datavetenskap används algoritmer för ett brett spektrum av operationer, från grundläggande matematik till invecklad databehandling.

En av de vanliga algoritmerna som används i C är sorteringsalgoritmen. En sorteringsalgoritm ordnar en samling objekt i en viss ordning, till exempel numeriskt eller alfabetiskt.

Det finns många sorteringsalgoritmer, alla med fördelar och nackdelar. De vanligaste sorteringsalgoritmerna i C är quicksort, merge och sort.

En av nyckelfunktionerna i C är pekarstöd. Detta möjliggör effektiv manipulering av datastrukturer såsom arrayer, köer etc. Detta gör den lämplig för att implementera algoritmer som kräver komplex datamanipulation, såsom sortering och algoritmisk sökning.

Ett av de berömda exemplen på mjukvarubibliotek implementerat i C är Standard Template Library (STL). Detta bibliotek tillhandahåller en mängd olika algoritmer för uppgifter som sortering, sökning och manipulering av datastrukturer.

Funktioner i algoritmen

Den definierar flera viktiga funktioner i algoritmen, inklusive:

Ingångar: Algoritmer måste ta emot indata som kan representeras som värden eller data.Produktion: Algoritmen bör producera viss utdata. Det kan vara en konsekvens av ett problem eller en lösning utformad för att lösa det.Klarhet: Algoritmer måste vara exakt definierade med entydiga instruktioner som en dator eller annat system kan följa entydigt.Ändlighet: Algoritmen kräver ett begränsat steg. Det betyder att den ska avslutas efter att ett visst antal kommandon har utförts.Giltighet: Algoritmen måste vara giltig. Den ska med andra ord kunna ta fram en lösning på problemet som algoritmen är designad att lösa inom rimlig tid.Effektivitet:En algoritm måste vara effektiv, det vill säga att den ska kunna ta fram en lösning på det problem den är designad att lösa inom rimlig tid.Allmänhet:En algoritm måste vara generell, vilket innebär att den kan tillämpas på ett brett spektrum av problem snarare än att vara specifik för ett enskilt problem.

Algoritmanalys

Algoritmanalys är processen att utvärdera algoritmens prestanda i termer av effektivitet, komplexitet och andra kriterier. Detta görs vanligtvis för att utvärdera många algoritmer och välja den optimala lösningen för ett visst problem eller en programvara.

om av rudyard kipling rad för rad förklaring

Analys av algoritmer innebär vanligtvis att mäta deras komplexitet i tid och rum.

Precis som med utrymmeskomplexitet, som beskriver mängden minne eller diskutrymme som behövs, beskriver tidskomplexitet hur länge en algoritm bestämmer sig för att utföra en uppgift.

Det finns olika sätt att analysera tidskomplexiteten hos algoritmer, som Big O och Omega-notation. Omega-symbolen ger en övre gräns för algoritmens tidskomplexitet, medan Omega-symbolen ger en nedre gräns.

Förutom att mäta tids- och rymdkomplexitet inkluderar algoritmanalys även andra kriterier som stabilitet, parallellitet och skalbarhet.

Stabilitet:- Detta hänvisar till algoritmens förmåga att upprätthålla den relativa ordningen för elementen i datamängden.Parallellisering:- Detta syftar på kapaciteten att utföra operationer parallellt över flera processorer.Skalbarhet:- Å andra sidan hänvisar det till en algoritms förmåga att hantera stora mängder data och andra indata.

De inkluderar två typer av analyser.

dom är:-

1. Förhandsanalys.
2. Posterior analys.

Tidigare analys

Prior är en metod för algoritmanalys som fokuserar på att uppskatta prestandan för en algoritm baserat på dess matematiska egenskaper utan att faktiskt exekvera algoritmen.

Detta tillvägagångssätt låter dig analysera tids- och rumskomplexiteten för algoritmer och andra mätvärden utan att behöva implementera och köra algoritmerna.

Posterior analys

Posterior analys, å andra sidan, är en metod för algoritmanalys som faktiskt exekverar algoritmen och mäter dess prestanda.

Detta tillvägagångssätt ger mer exakt och detaljerad information om algoritmens prestanda, men kräver implementering och exekvering av algoritmen.

Algoritm komplexitet

Algoritmisk komplexitet är ett mått för att mäta effektiviteten och prestanda hos algoritmen. Algoritmer utvärderas vanligtvis i termer av tid och utrymme som krävs för att lösa ett problem eller uppnå ett specifikt mål.

Två faktorer används i algoritmens komplexitet.

dom är:-

1. Tidsfaktor.
2. Utrymmesfaktor.

Tidsfaktor

• Mängden tid en algoritm behöver för att utföra en uppgift kallas tidskomplexitet. Den mäts vanligtvis av antalet operationer eller steg en algoritm måste utföra för att lösa ett problem.
• Tidskomplexiteten hos en algoritm är viktig eftersom den avgör hur lång tid det tar att köra och kan ha en betydande inverkan på program och systemprestanda.
• Tidskomplexiteten för en algoritm kan uttryckas med Big O-notation, ett sätt att uttrycka en övre gräns för tidskomplexiteten för en algoritm.
• En algoritm med tidskomplexitet O(n) innebär att tiden som krävs för att köra algoritmen är direkt proportionell mot storleken på indata (n).
• Andra vanliga tidskomplexiteter är O(n^2) kvadratisk komplexitet och O(log n) logaritmisk komplexitet.

Rymdanalys

• Å andra sidan hänvisar utrymmeskomplexitet till mängden minne eller lagringsutrymme som krävs för att exekvera algoritmen.
• Detta är viktigt eftersom det bestämmer antalet resurser som krävs för att köra algoritmer som kan påverka den övergripande prestandan för din applikation eller ditt system.
• Om utrymmeskomplexiteten för algoritmen är O(n), använder den en mängd minne som växer linjärt med storleken på inmatningen.
• Om algoritmen har O(1) rymdkomplexitet använder den en fast mängd minne oavsett storleken på ingången.

Hur man skriver en algoritm

1. Definiera först problemet du vill att algoritmen ska lösa.

Anta till exempel att vi vill skriva en algoritm för att hitta det maximala värdet från en lista med tal.

hur man konverterar från int till sträng i java

2. Dela upp problemet i mindre, hanterbara steg.

• Initiera 'max'-variabeln till det första värdet i listan.
• För varje efterföljande värde i listan, jämför med 'max'.
• Om värdet är större än 'max', ställ in 'max' på det värdet.
• Fortsätt göra detta tills alla värden i listan har jämförts.
• Returnerar det slutliga maxvärdet.

3. Skriv din algoritm i pseudokod eller ett programmeringsspråk.

Algoritm skriven i pseudokod:

 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. Testa din algoritm för att se till att den är korrekt och effektiv.

Du kan testa algoritmen genom att ange olika listor med siffror och verifiera att den returnerar det maximala korrekta värdet. Du kan också analysera tidskomplexiteten för din algoritm för att avgöra hur väl den skalas för större indata.

Exempel:-

Inmatning: [1, 5, 2, 7, 3]

Utgång: 7.

Förklaring: 7 är maxvärdet i listan.

5. Optimera algoritmen.

Leta efter sätt att optimera algoritmer för att göra dem snabbare och mer effektiva. Detta kan innebära att modifiera pseudokod eller implementera mer effektiva datastrukturer eller algoritmer.

Grundläggande skrivning av algoritmer

Exempel: - Summan av två heltal.

Steg 1 - Komma igång

Steg 2 - Deklarera tre heltal a, b, c

Steg 3 - Definiera värdena för a och b

Steg 4 - Lägg till värdena för a och b

Steg 5 - Spara utdata från steg 4 i c

Steg 6 - Tryck c

Steg 7 - Sluta

Typ av algoritmer som används i C-språk.

1. Sorteringsalgoritmer

C tillhandahåller en rik uppsättning datatyper och operatorer som kan användas för att implementera olika sorteringsalgoritmer som bubbelsortering, infogningssortering och snabbsortering.

Dessa algoritmer är användbara i många applikationer eftersom de kan användas för att sortera data av olika storlekar och typer.

Det finns olika sorteringsalgoritmer.

dom är:-

(i) Bubblesortering: En okomplicerad sorteringsalgoritm som jämför närliggande komponenter upprepade gånger och kopplar bort dem om de inte fungerar.

Algoritmen för bubbelsortering är: -

1. Börja med en osorterad lista med element.
2. Jämför de två första elementen i listan. Om det första elementet är större än det andra elementet, byt ut dem.
3. Gå vidare till nästa elementpar och upprepa steg 2 tills slutet av listan nås.
4. För varje punkt på listan upprepar du steg 2 och 3 en gång till. som kallas pass.
5. Upprepa steg 2-4 för hela listan. När du upprepar passen kommer elementen att 'bubbla upp' till sin rätta position i den sorterade listan.
6. När ett pass är klart och inga byten har gjorts, sorteras listan och algoritmen kan stoppas.
7. Den slutliga sorterade listan returneras.

(ii) Insättningssort : en metod för sortering som skapar en sorterad lista ett enskilt element i taget genom att placera vart och ett på lämplig plats.

Algoritmen för infogningssortering är:

1. Initiera en tom sorterad lista och en osorterad lista över de element som ska sorteras.
2. Den första medlemmen från den osorterade listan ska tas och placeras på lämplig plats i den sorterade listan.
3. Upprepa steg 2 för varje efterföljande element i den osorterade listan.
4. Jämför det aktuella elementet med elementen i den sorterade listan, börja med elementet omedelbart till vänster.
5. Byt ut de två elementen om det aktuella elementet är mindre än elementet till vänster om det.
6. Om det aktuella elementet är större än elementet till vänster om det, infogar det på rätt plats i den sorterade listan.
7. Upprepa steg 4-6 för varje efterföljande element i den osorterade listan.
8. När alla element har bearbetats kommer den sorterade listan att innehålla alla element i rätt ordning.
9. Sorteringsprocessen är klar.

(iii) Urvalssortering : en metod för sortering som konsekvent startar den sorterade listningen med minsta detalj från den oordnade listningen.

Algoritmen för urvalssortering är: -

1. Börja med att ställa in det primära elementet i listan som min-element.
2. Upprepa genom de återstående objekten i listan och jämför var och en med det aktuella minimumet.
3. Sätt ett nytt minimum om ett element visar sig vara mindre än det befintliga.
4. Ändra det aktuella minimumet till det första elementet i listan när den når sin slutsats.
5. För den återstående osorterade delen av listan, upprepa steg 2-4, men börja med det andra objektet på listan (eftersom det första elementet redan är sorterat).
6. Fortsätt att sortera listan på detta sätt tills allt är sorterat.

(iv) Snabb sortering : En dela-och-härska sorteringsalgoritm som väljer ett pivotelement och delar upp listan i underlistor beroende på om elementen är färre än eller fler än pivoten. Därefter sorteras underlistorna upprepade gånger tills hela listan är sorterad.

Algoritmen för snabb sortering är:

1. Välj ett pivotelement från listan. Detta är vanligtvis det första elementet, men det kan också vara ett slumpmässigt element eller medianen i listan.
2. Dela upp listan i två underlistor: en som innehåller element mindre än pivoten och en som innehåller element större än pivoten.
3. Sortera rekursivt underlistan som innehåller element mindre än pivoten med samma process.
4. Använd samma procedur för att rekursivt sortera underlistan med poster större än pivoten.
5. Sammanfoga de sorterade underlistorna med pivotelementet mellan för att bilda en fullständigt sorterad lista.
6. Returnera den fullständigt sorterade listan.

(v) Lot går : Dela-och-härska sorteringsalgoritmen delar upp listan i två halvor, sorterar varje halva och slår sedan samman de två halvorna i sorterad ordning.

Slå samman-sorteringsalgoritm:

1. Gör två underlistor av listan: en med element under pivoten och en med element ovanför pivoten.
2. Skapar en ny sorterad underlista genom att iterativt slå samman underlistor tills det bara finns en underlista. Detta kommer att vara din sorterade lista.
3. Steg för att slå samman två underkataloger: -
4. Skapa en tom lista för att hålla de sorterade elementen.
5. Jämför det första elementet i varje underlista.
6. Lägger till det mindre elementet i den nya listan och tar bort det från den överordnade underlistan.
7. Upprepa steg 2 och 3 tills en lista är helt tom.
8. Lägger till de återstående elementen från andra underlistor till en ny lista.
9. Ersätter den sammanslagna underlistan med den nya sorterade listan.
10. Upprepa denna process tills alla underlistor har slagits samman till en sorterad lista.

(vi) Heapsort : En sorteringsalgoritm som sorterar element med hjälp av en datastruktur som kallas heap.

Detta är klassificeringsalgoritmen:

Bygg maxhög: Börja med den första icke-bladsnoden, jämför varje nod med dess underordnade noder och ersätt noderna med den största av dess underordnade för att tillfredsställa egenskapen max heap.Byt rot med det sista elementet: Byt ut roten (största elementet) med det sista elementet i stacken.
1. Stapla resten av elementen. Med utgångspunkt från roten jämförs varje nod med sina barn, och byter noder med sina äldre barn tills egenskapen max heap är uppfylld.
2. Upprepa steg 2 och 3 med de nyligen staplade elementen, förutom det sista elementet i rätt position.
3. Upprepa denna process tills endast ett element finns kvar i högen. Detta är nu sorterat.
Heapify Down: Med start från rotnoden jämför den element med sina underordnade element och byter med den större av de två tills egenskapen max heap är uppfylld.Heapify Up: Börja med det sista elementet i högen, jämför det med dess överordnade och byt ut det med det överordnade för att uppfylla egenskapen max heap.

(vii) Radixsort : En sorteringsalgoritm som sorterar element baserat på siffrorna eller siffrorna i deras binära representation.

Algoritmen för Radix-sortering är:

hur man konverterar str till int

1. bestäm hur många siffror som finns i inmatningslistans största element.
2. Initiera en variabel, säg sifferplats, till 1, som representerar den aktuella sifferplatsen.
3. Skapa en tom lista för varje möjlig siffra från 0 till 9.
4. Iterera genom inmatningslistan och lägg till varje element i lämplig lista baserat på värdet på den aktuella sifferplatsen.
5. Sammanfoga alla listor för att bilda den nya listan i sifferlistornas ordning.
6. Multiplicera siffran Placera med 10 för att flytta till nästa siffra.
7. Upprepa steg 4-6 för varje sifferplats tills alla siffror i det största elementet har beaktats.
8. Den slutliga listan kommer att sorteras i stigande ordning efter elementens siffror.
9. Returnera den slutliga sorterade listan.

2. Sökalgoritmer

C tillhandahåller också de verktyg som krävs för att implementera en mängd olika sökalgoritmer, såsom linjär sökning och binär sökning. Dessa algoritmer kan snabbt hitta specifika objekt i en datamängd, vilket gör dem användbara för ett brett spektrum av applikationer.

Det finns många typer av sökalgoritmer.

Dom är:-

(i) Linjär sökning : En grundläggande sökalgoritm som undersöker varje objekt i listan en efter en tills den hittar det önskade objektet.

Algoritm för linjär sökning:-

1. Definiera indata för algoritmen: Indata för en linjär sökalgoritm är en lista med element (eller en array) och ett målelement vi söker efter.
2. Initiera en variabel som heter 'index' till -1: Denna variabel kommer att användas för att lagra indexet för målelementet om det hittas.
3. Gå igenom listan med element: Börja från det första elementet, kontrollera varje element i listan en efter en.
4. Jämför det aktuella elementet med det önskade elementet för utvärdering: Behåll indexet för det aktuella elementet i indexvariabeln och lämna loopen om det moderna elementet och målelementet är identiska.
5. Returnera indexet för målelementet: När slingan är klar, returnera värdet som lagrats i indexvariabeln. Om målelementet inte hittas blir indexvärdet -1.

(ii) Binär sökning : En sökalgoritm som fungerar genom att dela upp listan i halvor och sökningar inom dessa halvor är mer sannolikt att inkludera elementet.

Algoritm för binär sökning:-

1. Indata: En sorterad lista med n element och ett målelement x.
2. Initiera variabler: Ställ in det låga indexet till 0, det höga indexet till n-1 och mitten till (lågt+högt)/2.
3. Starta en loop: Medan det låga indexet är mindre än eller lika med det höga indexet, upprepar du följande steg.
4. Jämför mittelementet med x: Om mittelementet är lika med x, returnera mittindexet.
5. Uppdatera det låga eller höga indexet: Om x är större än mittelementet, ställ in det låga indexet till mitten + 1. Annars, ställ in det höga indexet till mitten - 1.
6. Uppdatera mittindex: Mid = (låg+hög)/2.
7. Slutet på slingan: Om det låga indexet är större än det höga indexet finns inte x i listan, och algoritmen returnerar ett misslyckande.
8. Utdata: Indexet för x i listan eller felmeddelandet.

(iii) Djup-första sökning : En sökalgoritm som undersöker varje gren så långt det är möjligt innan den vänder.

maskinskrivet datum och tid

Följande riktlinjer gäller för djup-först-sökning:

1. välj grafens startpunkt eller nod till att börja med.
2. Lägg till ett besöksmärke till den första vertexen.
3. Placera början vertex direkt i en stapel.
4. Tills stacken är tom, upprepa följande åtgärder: -
   • Ta bort stapelns övre vertex.
   • Markera som besökt och infoga i stapeln varje obesökt granne till den fällda vertexen.
5. Fortsätt denna process tills alla hörn i grafen har besökts.
6. När alla hörn har besökts är algoritmen klar och en djupsökning utförs på grafen.

(iv) Bredd-först sökning : En sökalgoritm som utforskar alla grannar till en nod innan den går till nästa nivå.

Algoritmen för sökningen på bredden först är:

1. Börja med rotnoden eller initialtillståndet.
2. Lägg till rotnoden i en kö.
3. Kontrollera om kön är tom; om ja, avsluta sedan algoritmen.
4. Ta det första elementet från kön och markera det som besökt.
5. Förstärk den samtida noden genom att lägga till alla dess obesökta grannar i kön.
6. Upprepa steg 3 till 5 tills den önskade noden är lokaliserad eller kön är tom.
7. Återställ sökvägen från det preliminära tillståndet till måltillståndet om målnoden hittas.
8. Avsluta regeluppsättningen och rapportera att måltillståndet inte identifierades om kön är tom.

(v) Interpolationssökning : En sökalgoritm som använder värdena för de sökta elementen för att uppskatta positionen i indexet.

Det är viktigt att arrayen är jämnt fördelad. Annars är det en algoritm.

Det fungerar som förväntat.

Algoritmen kan sammanfattas enligt följande.

1. Hämta inmatningslistan och nyckelvärdet för att söka.
2. Initiera de nedre och övre variablerna vid listans första och sista index.
3. Om det lägre värdet är mindre än eller lika med det högre värdet, då:-
   1. Beräkna den uppskattade platsen med hjälp av följande formel:
      pos = låg + ((hög - låg) / (arr[hög] - arr[låg])) * (x - arr[låg]).
   2. Returnera positionen om det uppskattade positionsvärdet är ett nyckelvärde.
   3. c) Om det uppskattade positionsvärdet är mindre än nyckelvärdet, ställ in det lägre.
      Position + 1.
   4. d) Om värdet på den beräknade positionen är större än nyckeln Inställt värde, position - 1 upp.
4. Om nyckelvärdet inte hittas, returnera -1 för att indikera att värdet inte finns i listan.

(vi) Hoppa sökning : En sökmetod som itererar över listan i steg med konstant längd tills den hittar det relevanta elementet eller avgör att det inte längre finns.

Hoppsökningsalgoritmen är som följer:

1. Ställ först in hoppstorleken till kvadratroten av antalet arrayelement.
2. Ställer in en variabel med namnet 'current' till det första elementet i arrayen.
3. Itererar över arrayen genom att hoppa efter hoppstorlek samtidigt som en variabel som kallas 'hopp' ökas.
4. Gå vidare till följande språng om det befintliga elementet är mindre än det önskade elementet.
5. Om det aktuella elementet är större än målelementet, utför en linjär sökning mellan det aktuella elementet och det föregående hoppelementet för att hitta målelementet.
6. Om målelementet inte hittas i arrayen, returnerar det -1 för att indikera att det inte finns i arrayen.
7. Om elementet hittas returnerar det elementets index i arrayen.

3. Grafalgoritmer

C:s stöd för pekare och datastrukturer som arrayer och länkade listor gör den lämplig för att implementera algoritmer som manipulerar grafer, som att hitta den kortaste vägen mellan två noder i en graf.

Det finns olika typer av grafalgoritmer.

dom är:-

Dijkstras algoritm: En algoritm som hittar den kortaste vägen mellan två noder i en graf genom att kontinuerligt uppdatera det kortaste avståndet från varje nod.Algoritm A*: En metod som kontinuerligt uppdaterar den kortaste kursen till varje nod i en graf för att bestämma den kortaste vägen mellan dem.Prims algoritm: Ett tillvägagångssätt för att räkna ut den viktade anslutna grafens minsta spännträd.Kruskals algoritm: Ett tillvägagångssätt för att identifiera den länkade viktade grafens lägsta spännträd.Bellman-Fords algoritm: En algoritm som, även när grafen har negativa kantvikter, visar den kortaste vägen mellan en viss matningsnod och varannan nod i nätverket.

4. Kryptografiska algoritmer

C stöder lågnivåoperationer och effektiv datamanipulation, vilket gör den idealisk för att implementera algoritmer som används i kryptografi, såsom datakryptering och dekrypteringsalgoritmer.

Det finns olika typer av krypteringsalgoritmer.

Dom är:-

Hash-algoritmer: Dessa algoritmer producerar utdata med fast storlek (hash) från indata av godtycklig storlek. Exempel inkluderar MD5, SHA-1 och SHA-2.Symmetriska nyckelalgoritmer: Krypterings- och dekrypteringsstegen i sådana algoritmer använder samma privata nyckel. AES, DES och Blowfish är några exempel.Asymmetriska nyckelalgoritmer: En offentlig nyckel och en icke-offentlig nyckel används av dessa metoder som separata nycklar för kryptering och dekryptering. Några exempel inkluderar RSA, ECC och DSA.Algoritmer för nyckelutbyte: Dessa algoritmer tillåter två parter att utbyta nycklar över en osäker kanal på ett säkert sätt. Till exempel kan vi nämna Diffie-Hellman och Elliptic Curve Diffie-Hellman.

Fördelar med algoritmen

Algoritmer har många fördelar.

dom är:-

Snabbhet och effektivitet: Algoritmer kan behandla stora mängder data snabbt och exakt, vilket gör dem användbara för uppgifter som är för tidskrävande eller felbenägna för människor att utföra.Konsistens: Algoritmer följer en uppsättning förutbestämda riktlinjer. Det kan ge konsekventa resultat utan att påverkas av personliga fördomar och känslor.Automatisering: Algoritmer kan utföra uppgifter automatiskt, vilket gör att människor kan fokusera på mer komplexa eller kreativa uppgifter.Ökad noggrannhet: Algoritmer kan ofta uppnå högre nivåer av noggrannhet än människor, särskilt när de hanterar stora mängder data.Bättre beslutsfattande: Algoritmer hjälper oss att fatta mer informerade och objektiva beslut genom att analysera data och identifiera mönster och trender som inte är lätt synliga för människor.Skalbarhet: Algoritmer kan lätt skalas upp eller ned för att möta ändrade krav och arbetsbelastningar.

Nackdelar med algoritmen

Algoritmer är mycket användbara för programmering, men algoritmer har nackdelar.

dom är:-

Begränsad omfattning: Algoritmer kan bara lösa problem inom sin omfattning och kanske inte kan lösa komplexa eller abstrakta problem.Partiskhet: Algoritmer kan vidmakthålla och förstärka fördomar i data som används för träning, vilket leder till orättvisa resultat.Otillräcklig transparens: Många algoritmer döljer processen genom vilken de kommer fram till sina slutsatser. Detta kan göra det svårt att tänka på eller kontrollera resultaten.Beroende på finheten hos uppgifterna:Korrektheten av regeluppsättningen är starkt beroende av finheten och tillämpligheten av data som används i instruktionen. Felaktiga eller felaktiga effekter kan vara resultatet av felaktiga data.begränsad anpassningsförmåga:Algoritmer är utformade för att följa riktlinjer och anpassar sig inte till förändrade omständigheter och förhållanden.