algoritme is een stap-voor-stap procedure, die een set instructies definieert om worden uitgevoerd in een bepaalde volgorde om de gewenste output te krijgen. Algoritmen worden over het algemeen gemaakt onafhankelijk van onderliggende talen, dat wil zeggen een algoritme kan worden geïmplementeerd in meer dan één programmeertaal.,
vanuit het oogpunt van de gegevensstructuur, volgen enkele belangrijke categorieën algoritmen –
-
zoekalgoritme om een item in een gegevensstructuur te zoeken.
-
sorteeralgoritme om items in een bepaalde volgorde te sorteren.
-
Insert-algoritme om item in een gegevensstructuur in te voegen.
-
Update-algoritme om een bestaand item in een gegevensstructuur bij te werken.
-
Delete-algoritme om een bestaand item uit een gegevensstructuur te verwijderen.
Kenmerken van een algoritme
niet alle procedures kunnen een algoritme worden genoemd., Een algoritme moet de volgende kenmerken hebben –
-
ondubbelzinnig-algoritme moet duidelijk en ondubbelzinnig zijn. Elk van de stappen (of fasen), en hun inputs/outputs moet duidelijk zijn en moet leiden tot slechts één betekenis.
-
Input – een algoritme moet 0 of meer goed gedefinieerde ingangen hebben.
-
Output – een algoritme moet 1 of meer goed gedefinieerde outputs hebben, en moet overeenkomen met de gewenste output.
-
eindigheid-algoritmen moeten eindigen na een eindig aantal stappen.,
-
haalbaarheid – moet haalbaar zijn met de beschikbare middelen.
-
onafhankelijk-een algoritme moet stap-voor-stap aanwijzingen hebben, die onafhankelijk moeten zijn van enige programmeercode.
Hoe schrijf ik een algoritme?
Er zijn geen goed gedefinieerde standaarden voor het schrijven van algoritmen. Integendeel, het is probleem en resource afhankelijk. Algoritmen worden nooit geschreven om een bepaalde programmeercode te ondersteunen.
omdat we weten dat alle programmeertalen basiscodeconstructies delen zoals loops (do, for, while), flow-control (if-else), etc., Deze gemeenschappelijke constructies kunnen worden gebruikt om een algoritme te schrijven.
We schrijven algoritmen stap voor stap, maar dat is niet altijd het geval. Algoritme schrijven is een proces en wordt uitgevoerd nadat het probleemdomein goed gedefinieerd is. Dat wil zeggen, we moeten het probleemdomein kennen, waarvoor we een oplossing ontwerpen.
voorbeeld
laten we proberen algoritme-schrijven te leren met behulp van een voorbeeld.
probleem-ontwerp een algoritme om twee getallen toe te voegen en het resultaat weer te geven.
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
algoritmen vertellen de programmeurs hoe ze het programma moeten coderen., Als alternatief kan het algoritme worden geschreven als –
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
in het ontwerp en de analyse van algoritmen, meestal wordt de tweede methode gebruikt om een algoritme te beschrijven. Het maakt het gemakkelijk voor de analist om het algoritme te analyseren en alle ongewenste definities te negeren. Hij kan zien welke bewerkingen worden gebruikt en hoe het proces verloopt.
het schrijven van stapnummers is optioneel.
We ontwerpen een algoritme om een oplossing voor een bepaald probleem te krijgen. Een probleem kan op meerdere manieren worden opgelost.,
daarom kunnen veel oplossingsalgoritmen worden afgeleid voor een bepaald probleem. De volgende stap is het analyseren van die voorgestelde oplossing algoritmen en implementeren van de beste geschikte oplossing.
Algoritmeanalyse
efficiëntie van een algoritme kan in twee verschillende fasen worden geanalyseerd, vóór implementatie en na implementatie. Ze zijn de volgende −
-
a Priori analyse-Dit is een theoretische analyse van een algoritme., De efficiëntie van een algoritme wordt gemeten door aan te nemen dat alle andere factoren, bijvoorbeeld processorsnelheid, constant zijn en geen effect hebben op de implementatie.
-
een posterieure analyse – Dit is een empirische analyse van een algoritme. Het geselecteerde algoritme wordt geïmplementeerd met behulp van de programmeertaal. Dit wordt vervolgens uitgevoerd op de doelcomputer machine. In deze analyse worden actuele statistieken zoals de benodigde tijd en ruimte verzameld.
We zullen meer te weten komen over a priori algoritme analyse., Algoritme analyse behandelt de uitvoering of looptijd van de verschillende betrokken operaties. De looptijd van een operatie kan worden gedefinieerd als het aantal computerinstructies dat per operatie wordt uitgevoerd.
Algoritmecomplexiteit
stel dat X een algoritme is en n de grootte van invoergegevens is, de tijd en ruimte die door het algoritme X worden gebruikt zijn de twee belangrijkste factoren, die de efficiëntie van X.
-
tijdfactor bepalen − de tijd wordt gemeten door het aantal belangrijke bewerkingen zoals vergelijkingen in het sorteeralgoritme te tellen.,
-
Ruimtefactor-de ruimte wordt gemeten door de maximale geheugenruimte te tellen die door het algoritme wordt vereist.
de complexiteit van een algoritme f (n) Geeft de door het algoritme vereiste looptijd en/of opslagruimte in termen van n als de grootte van invoergegevens.
complexiteit van de ruimte
complexiteit van de ruimte van een algoritme vertegenwoordigt de hoeveelheid geheugenruimte die het algoritme nodig heeft in zijn levenscyclus., De door een algoritme vereiste ruimte is gelijk aan de som van de volgende twee componenten −
-
een vast deel dat een ruimte is die nodig is om bepaalde gegevens en variabelen op te slaan, die onafhankelijk zijn van de grootte van het probleem. Bijvoorbeeld, eenvoudige variabelen en constanten gebruikt, programma grootte, enz.
-
een variabel deel is een ruimte die vereist is door variabelen, waarvan de grootte afhankelijk is van de grootte van het probleem. Bijvoorbeeld, dynamic memory allocation, recursion stack space, etc.,
ruimtecomplexiteit S(P) van elk algoritme P is S(P) = C + SP(I), waarbij C het vaste deel is en S(I) het variabele deel van het algoritme is, dat afhankelijk is van de instantie karakteristiek I. Hieronder volgt een eenvoudig voorbeeld dat het concept probeert uit te leggen −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
hebben drie variabelen a, b, en c en een constante. Vandaar S (P)=1 + 3. Nu is ruimte afhankelijk van gegevenstypen van gegeven variabelen en constante typen en het zal dienovereenkomstig worden vermenigvuldigd.,
tijdcomplexiteit
tijdcomplexiteit van een algoritme vertegenwoordigt de tijd die het algoritme nodig heeft om te voltooien. Tijdvereisten kunnen worden gedefinieerd als een numerieke functie T(n), waarbij T(n) kan worden gemeten als het aantal stappen, op voorwaarde dat elke stap een constante tijd verbruikt.
bijvoorbeeld, optellen van twee n-Bit gehele getallen neemt n stappen. Bijgevolg is de totale rekentijd T ( n) = c * n, waarbij c de tijd is die nodig is voor het optellen van twee bits. Hier zien we dat T(n) lineair groeit naarmate de invoergrootte toeneemt.,