algoritm är ett steg för steg förfarande, som definierar en uppsättning instruktioner som ska utföras i en viss ordning för att få önskad utgång. Algoritmer skapas i allmänhet oberoende av underliggande språk, dvs en algoritm kan implementeras i mer än ett programmeringsspråk.,
från datastrukturens synvinkel är följande några viktiga kategorier av algoritmer −
-
sökalgoritm för att söka efter ett objekt i en datastruktur.
-
Sortera − algoritm för att sortera objekt i en viss ordning.
-
infoga − algoritm för att infoga objekt i en datastruktur.
-
Update − algoritm för att uppdatera ett befintligt objekt i en datastruktur.
-
Ta bort − algoritm för att ta bort ett befintligt objekt från en datastruktur.
egenskaper hos en algoritm
inte alla procedurer kan kallas en algoritm., En algoritm ska ha följande egenskaper −
-
entydig − algoritmen ska vara tydlig och entydig. Var och en av dess steg (eller faser), och deras ingångar/utgångar ska vara tydliga och måste leda till endast en mening.
-
Input − en algoritm ska ha 0 eller fler väldefinierade ingångar.
-
utgång − en algoritm ska ha 1 eller flera väldefinierade utgångar och ska matcha önskad utgång.
-
Finiteness − algoritmer måste avslutas efter ett begränsat antal steg.,
-
genomförbarhet − bör vara genomförbar med tillgängliga resurser.
-
oberoende − en algoritm bör ha steg-för-steg-anvisningar, som bör vara oberoende av någon programmeringskod.
hur man skriver en algoritm?
det finns inga väldefinierade standarder för att skriva algoritmer. Snarare är det problem och resursberoende. Algoritmer skrivs aldrig för att stödja en viss programmeringskod.
eftersom vi vet att alla programmeringsspråk delar grundläggande kodkonstruktioner som loopar (gör, för, medan), flödeskontroll (if-else) etc., Dessa vanliga konstruktioner kan användas för att skriva en algoritm.
vi skriver algoritmer steg för steg, men det är inte alltid fallet. Algoritmskrivning är en process och utförs efter att problemdomänen är väldefinierad. Det vill säga vi borde känna till problemområdet, för vilket vi utformar en lösning.
exempel
låt oss försöka lära oss algoritmskrivning genom att använda ett exempel.
Problem − utforma en algoritm för att lägga till två nummer och visa 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 berättar programmerarna hur man kodar programmet., Alternativt kan algoritmen skrivas som –
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
i design och analys av algoritmer används vanligtvis den andra metoden för att beskriva en algoritm. Det gör det enkelt för analytikern att analysera algoritmen ignorerar alla oönskade definitioner. Han kan observera vilka operationer som används och hur processen flyter.
skriva stegnummer, är valfritt.
vi utformar en algoritm för att få en lösning på ett givet problem. Ett problem kan lösas på mer än ett sätt.,
därför kan många lösningsalgoritmer härledas för ett visst problem. Nästa steg är att analysera de föreslagna lösningsalgoritmerna och genomföra den bästa lämpliga lösningen.
Algoritmanalys
effektiviteten hos en algoritm kan analyseras i två olika steg, före implementering och efter implementering. De är följande −
-
a Priori − analys-det här är en teoretisk analys av en algoritm., Effektiviteten hos en algoritm mäts genom att anta att alla andra faktorer, till exempel processorhastighet, är konstanta och inte har någon effekt på genomförandet.
-
en bakre analys − det här är en empirisk analys av en algoritm. Den valda algoritmen implementeras med programmeringsspråk. Detta utförs sedan på mål dator maskin. I denna analys samlas faktisk statistik som körtid och utrymme som krävs.
vi ska lära oss om a priori-algoritmanalys., Algoritmanalys behandlar utförandet eller körtiden för olika inblandade operationer. Drifttiden för en operation kan definieras som antalet datorinstruktioner utförda per operation.
algoritm komplexitet
Antag att X är en algoritm och n är storleken på indata, tid och utrymme som används av algoritmen X är de två huvudfaktorerna, som bestämmer effektiviteten av X.
-
Tidsfaktortid mäts genom att räkna antalet nyckeloperationer som jämförelser i sorteringsalgoritmen.,
-
Space Factor − Space mäts genom att räkna det maximala minnesutrymme som krävs av algoritmen.
komplexiteten hos en algoritm f(n) ger körtiden och / eller det lagringsutrymme som algoritmen kräver när det gäller n som storleken på indata.
rymd komplexitet
rymd komplexitet av en algoritm representerar den mängd minnesutrymme som krävs av algoritmen i dess livscykel., Utrymmet som krävs av en algoritm är lika med summan av följande två komponenter –
-
en fast del som är ett utrymme som krävs för att lagra vissa data och variabler, som är oberoende av storleken på problemet. Till exempel, enkla variabler och konstanter som används, programstorlek etc.
-
en variabel del är ett utrymme som krävs av variabler, vars storlek beror på problemets storlek. Till exempel dynamisk minnesallokering, rekursion stack utrymme, etc.,
Utrymme komplexitet S(P) av någon algoritm P är S(P) = C+ SP(i), där C är den fasta delen och S(I) är den variabla delen av algoritmen, vilket beror på instans karakteristisk I. Följande är ett enkelt exempel som försöker förklara konceptet −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
Här har vi tre variabler A, B, och C och en konstant. Därmed S(P) = 1 + 3. Nu, utrymme beror på datatyper av givna variabler och konstanta typer och det kommer att multipliceras i enlighet därmed.,
tidskomplexitet
tidskomplexitet för en algoritm representerar den tid som algoritmen behöver för att köras till färdigställande. Tidskrav kan definieras som en numerisk funktion T (n), där T(n) kan mätas som antalet steg, förutsatt att varje steg förbrukar konstant tid.
till exempel tar tillägg av två N-bitars heltal n steg. Följaktligen är den totala beräkningstiden T ( n) = c n, där C är tiden för tillsats av två bitar. Här observerar vi att T (n) växer linjärt när inmatningsstorleken ökar.,