Algoritme er en trin-for-trin procedure, som definerer et sæt af instruktioner, der skal udføres i en bestemt rækkefølge for at få det ønskede output. Algoritmer oprettes generelt uafhængigt af underliggende sprog, dvs. en algoritme kan implementeres på mere end et programmeringssprog.,
fra datastrukturens synspunkt er følgende nogle vigtige kategorier af algoritmer −
-
søgealgoritme for at søge et element i en datastruktur.
-
Sorter − algoritme til at sortere elementer i en bestemt rækkefølge.
-
Indsæt − algoritme til at indsætte element i en datastruktur.
-
Update − algoritme til at opdatere et eksisterende element i en datastruktur.
-
Delete − algoritme til at slette et eksisterende element fra en datastruktur.
egenskaber ved en algoritme
ikke alle procedurer kan kaldes en algoritme., En algoritme skal have følgende egenskaber-
-
entydig − algoritmen skal være klar og entydig. Hvert af dets trin (eller faser), og deres input/output skal være klare og må kun føre til en betydning.
-
Input − en algoritme skal have 0 eller flere veldefinerede indgange.
-
Output − en algoritme skal have 1 eller flere veldefinerede udgange og skal matche det ønskede output.
-
Finiteness − algoritmer skal afslutte efter et begrænset antal trin.,
-
gennemførlighed − bør være muligt med de tilgængelige ressourcer.
-
uafhængig − en algoritme skal have trinvise retninger, som skal være uafhængige af enhver programmeringskode.
hvordan man skriver en algoritme?
Der er ingen veldefinerede standarder for skrivning af algoritmer. Det er snarere problem og ressourceafhængig. Algoritmer er aldrig skrevet for at understøtte en bestemt programmeringskode.
som vi ved, at alle programmeringssprog deler grundlæggende kodekonstruktioner som sløjfer (gør, for, mens), Flo.-kontrol (hvis-ellers) osv., Disse fælles konstruktioner kan bruges til at skrive en algoritme.
Vi skriver algoritmer trin for trin, men det er ikke altid tilfældet. Algoritme skrivning er en proces og udføres efter problemet domæne er veldefineret. Det vil sige, vi skal kende problemdomænet, som vi designer en løsning til.
eksempel
Lad”s forsøge at lære algoritme-skrivning ved hjælp af et eksempel.
Problem − Design En algoritme til at tilføje to tal og vise resultatet.
Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP
algoritmer fortæller programmørerne, hvordan de skal kode programmet., Alternativt kan algoritmen skrives som –
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
i design og analyse af algoritmer bruges normalt den anden metode til at beskrive en algoritme. Det gør det nemt for analytikeren at analysere algoritmen og ignorere alle uønskede definitioner. Han kan observere, hvilke operationer der bruges, og hvordan processen flyder.
skrivning af trinnumre er valgfrit.
Vi designer en algoritme for at få en løsning på et givet problem. Et problem kan løses på mere end onen måde.,
derfor kan mange løsningsalgoritmer udledes for et givet problem. Det næste trin er at analysere de foreslåede løsningsalgoritmer og implementere den bedst egnede løsning.
Algoritmeanalyse
effektiviteten af en algoritme kan analyseres på to forskellige stadier, før implementering og efter implementering. De er følgende –
-
a Priori analyse − Dette er en teoretisk analyse af en algoritme., Effektiviteten af en algoritme måles ved at antage, at alle andre faktorer, for eksempel processorhastighed, er konstante og ikke har nogen indflydelse på implementeringen.en Posterior analyse-Dette er en empirisk analyse af en algoritme. Den valgte algoritme implementeres ved hjælp af programmeringssprog. Dette udføres derefter på målcomputeren. I denne analyse indsamles faktiske statistikker som køretid og plads, der kræves.
Vi skal lære om a priori algoritme analyse., Algoritmeanalyse omhandler udførelse eller driftstid for forskellige involverede operationer. Driftstiden for en operation kan defineres som antallet af computerinstruktioner, der udføres pr.
Algoritme Kompleksitet
Antag at X er en algoritme, og n er størrelsen af input-data, tid og rum, der anvendes af den algoritme X er de to vigtigste faktorer, som bestemmer effektiviteten af X.
-
Tiden Faktor − Tid måles ved at tælle antallet af vigtigste operationer, såsom sammenligninger i sorterings-algoritme.,
-
Rumfaktor − rummet måles ved at tælle den maksimale hukommelsesplads, der kræves af algoritmen.
kompleksiteten af en algoritme f(n) giver køretiden og / eller den lagerplads, der kræves af algoritmen, med hensyn til n som størrelsen af inputdata.
Rumkompleksitet
Rumkompleksitet af en algoritme repræsenterer den mængde hukommelsesplads, der kræves af algoritmen i dens livscyklus., Den plads, der kræves af en algoritme, er lig med summen af de følgende to komponenter −
-
en fast del, der er et rum, der kræves til at gemme visse data og variabler, der er uafhængige af størrelsen på problemet. For eksempel anvendte enkle variabler og konstanter, programstørrelse osv.
-
en variabel del er et rum, der kræves af variabler, hvis størrelse afhænger af størrelsen af problemet. For eksempel dynamisk hukommelsesallokering, rekursionsstakplads osv.,
Plads kompleksitet S(P) af en algoritme P er S(P) = C + SP(jeg), hvor C er den faste del og S(I) er den variable del af den algoritme, der afhænger eksempel karakteristiske I. Følgende er et simpelt eksempel, der forsøger at forklare begrebet −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
Her har vi tre variable A, B og C og en konstant. Derfor S (P) = 1 + 3. Nu afhænger rummet af datatyper af givne variabler og konstante typer, og det vil blive multipliceret i overensstemmelse hermed.,
tidskompleksitet
tidskompleksitet af en algoritme repræsenterer den tid, der kræves af algoritmen til at køre til færdiggørelse. Tidskrav kan defineres som en numerisk funktion T(n), hvor T (n) kan måles som antallet af trin, forudsat at hvert trin bruger konstant tid.for eksempel tager tilsætning af to n-bit heltal n-trin. Følgelig er den samlede beregningstid T (n) = c n n, hvor c er den tid, det tager for tilsætning af to bits. Her observerer vi, at T(n) vokser lineært, når inputstørrelsen stiger.,