logo

TechCodeview

Hva er Algoritme | Introduksjon til algoritmer

Definisjon av Algoritme

Ordet Algoritme midler Et sett med begrensede regler eller instruksjoner som skal følges i beregninger eller andre problemløsningsoperasjoner
Eller
En prosedyre for å løse et matematisk problem i et begrenset antall trinn som ofte involverer rekursive operasjoner .

Derfor refererer Algoritme til en sekvens av endelige trinn for å løse et bestemt problem.

java stabler
Hva er algoritme

Bruk av algoritmene:

Algoritmer spiller en avgjørende rolle på ulike felt og har mange bruksområder. Noen av nøkkelområdene der algoritmer brukes inkluderer:



  1. Datavitenskap: Algoritmer danner grunnlaget for dataprogrammering og brukes til å løse problemer som spenner fra enkel sortering og søking til komplekse oppgaver som kunstig intelligens og maskinlæring.
  2. Matematikk: Algoritmer brukes til å løse matematiske problemer, for eksempel å finne den optimale løsningen på et system med lineære ligninger eller å finne den korteste veien i en graf.
  3. Driftsforskning : Algoritmer brukes til å optimalisere og ta beslutninger innen felt som transport, logistikk og ressursallokering.
  4. Kunstig intelligens: Algoritmer er grunnlaget for kunstig intelligens og maskinlæring, og brukes til å utvikle intelligente systemer som kan utføre oppgaver som bildegjenkjenning, naturlig språkbehandling og beslutningstaking.
  5. Datavitenskap: Algoritmer brukes til å analysere, behandle og trekke ut innsikt fra store datamengder innen felt som markedsføring, finans og helsetjenester.

Dette er bare noen få eksempler på mange anvendelser av algoritmer. Bruken av algoritmer utvides kontinuerlig etter hvert som nye teknologier og felt dukker opp, noe som gjør det til en viktig komponent i det moderne samfunnet.

Algoritmer kan være enkle og komplekse avhengig av hva du ønsker å oppnå.

Det kan forstås ved å ta eksemplet med å lage en ny oppskrift. For å lage en ny oppskrift, leser man instruksjonene og trinnene og utfører dem én etter én, i gitt rekkefølge. Resultatet er at den nye retten er perfekt tilberedt. Hver gang du bruker telefonen, datamaskinen, bærbar PC eller kalkulatoren, bruker du algoritmer. På samme måte hjelper algoritmer til å gjøre en oppgave i programmering for å få forventet utgang.

Algoritmen som er designet er språkuavhengig, det vil si at de bare er enkle instruksjoner som kan implementeres på et hvilket som helst språk, og likevel vil utgangen være den samme, som forventet.

Hva er behovet for algoritmer?

  1. Algoritmer er nødvendige for å løse komplekse problemer effektivt og effektivt.
  2. De hjelper til med å automatisere prosesser og gjøre dem mer pålitelige, raskere og enklere å utføre.
  3. Algoritmer gjør det også mulig for datamaskiner å utføre oppgaver som ville være vanskelige eller umulige for mennesker å gjøre manuelt.
  4. De brukes i ulike felt som matematikk, informatikk, ingeniørfag, finans og mange andre for å optimalisere prosesser, analysere data, lage spådommer og gi løsninger på problemer.

Hva er kjennetegnene til en algoritme?

Egenskaper til en algoritme

Ettersom man ikke ville følge noen skriftlige instruksjoner for å tilberede oppskriften, men kun standarden. På samme måte er ikke alle skriftlige instruksjoner for programmering en algoritme. For at noen instruksjoner skal være en algoritme, må den ha følgende egenskaper:

  • Klart og entydig : Algoritmen skal være entydig. Hvert av trinnene skal være tydelige i alle aspekter og må kun føre til én mening.
  • Veldefinerte innganger : Hvis en algoritme sier å ta innganger, bør det være veldefinerte innganger. Det kan ta innspill eller ikke.
  • Veldefinerte utganger: Algoritmen må klart definere hvilken utgang som skal gis, og den bør også være godt definert. Den skal produsere minst 1 utgang.
  • Begrensethet: Algoritmen må være endelig, dvs. den skal avsluttes etter en begrenset tid.
  • Gjennomførbart: Algoritmen må være enkel, generisk og praktisk, slik at den kan utføres med de tilgjengelige ressursene. Den må ikke inneholde noen fremtidig teknologi eller noe.
  • Språkuavhengig: Algoritmen som er utformet må være språkuavhengig, det vil si at den bare må være enkle instruksjoner som kan implementeres på et hvilket som helst språk, og likevel vil utgangen være den samme, som forventet.
  • Inndata : En algoritme har null eller flere innganger. Hver som inneholder en grunnleggende operator må godta null eller flere innganger.
  • Produksjon : En algoritme produserer minst én utgang. Hver instruksjon som inneholder en grunnleggende operatør må godta null eller flere innganger.
  • Bestemmelse: Alle instruksjoner i en algoritme må være entydige, presise og enkle å tolke. Ved å referere til en av instruksjonene i en algoritme kan man tydelig forstå hva som skal gjøres. Hver grunnleggende operatør i instruksjon må defineres uten tvetydighet.
  • Begrensethet: En algoritme må avsluttes etter et begrenset antall trinn i alle testtilfeller. Hver instruksjon som inneholder en grunnleggende operatør må avsluttes innen en begrenset tidsperiode. Uendelige løkker eller rekursive funksjoner uten basisbetingelser har ikke endelighet.
  • Effektivitet: En algoritme må utvikles ved å bruke veldig grunnleggende, enkle og gjennomførbare operasjoner slik at man kan spore den ut ved å bruke bare papir og blyant.

Egenskaper for algoritme:

  • Den bør avsluttes etter en begrenset tid.
  • Den skal produsere minst én utgang.
  • Det bør ta null eller flere input.
  • Det bør være deterministiske betyr å gi samme utgang for samme inngangstilfelle.
  • Hvert trinn i algoritmen må være effektivt, det vil si at hvert trinn skal gjøre noe arbeid.

Typer algoritmer:

Det finnes flere typer algoritmer tilgjengelig. Noen viktige algoritmer er:

1. Brute Force Algorithm :

Det er den enkleste tilnærmingen til et problem. En brute force-algoritme er den første tilnærmingen som kommer til å finne når vi ser et problem.

2. Rekursiv algoritme :

En rekursiv algoritme er basert på rekursjon . I dette tilfellet deles et problem inn i flere underdeler og kalles den samme funksjonen igjen og igjen.

3. Tilbakesporingsalgoritme :

Tilbakesporingsalgoritmen bygger løsningen ved å søke blant alle mulige løsninger. Ved å bruke denne algoritmen fortsetter vi å bygge løsningen etter kriterier. Når en løsning mislykkes, sporer vi tilbake til feilpunktet og bygger på neste løsning og fortsetter denne prosessen til vi finner løsningen eller alle mulige løsninger er tatt vare på.

4. Søkealgoritme :

Søkealgoritmer er de som brukes til å søke i elementer eller grupper av elementer fra en bestemt datastruktur. De kan være av forskjellige typer basert på deres tilnærming eller datastrukturen som elementet skal finnes i.

5. Sorteringsalgoritme :

Sortering er å ordne en gruppe data på en bestemt måte i henhold til kravet. Algoritmene som hjelper til med å utføre denne funksjonen kalles sorteringsalgoritmer. Generelt brukes sorteringsalgoritmer for å sortere grupper av data på en økende eller minkende måte.

6. Hashing-algoritme :

Hashing-algoritmer fungerer på samme måte som søkealgoritmen. Men de inneholder en indeks med nøkkel-ID. I hashing tilordnes en nøkkel til spesifikke data.

7. Divide and Conquer-algoritmen :

Denne algoritmen deler opp et problem i delproblemer, løser et enkelt delproblem og slår sammen løsningene for å få den endelige løsningen. Den består av følgende tre trinn:

  • Dele opp
  • Løse
  • Kombinere

8. Grådig algoritme :

I denne typen algoritmer bygges løsningen del for del. Løsningen for neste del bygges ut fra den umiddelbare nytten av neste del. Den ene løsningen som gir mest nytte vil bli valgt som løsning for neste del.

9. Dynamisk programmeringsalgoritme :

Denne algoritmen bruker konseptet med å bruke den allerede funnet løsningen for å unngå repeterende beregning av den samme delen av problemet. Den deler opp problemet i mindre overlappende delproblemer og løser dem.

10. Randomisert algoritme :

I den randomiserte algoritmen bruker vi et tilfeldig tall så det gir umiddelbar fordel. Det tilfeldige tallet hjelper til med å bestemme det forventede resultatet.

For å lære mer om typene algoritmer, se artikkelen om Typer algoritmer .

Fordeler med algoritmer:

  • Det er lett å forstå.
  • En algoritme er en trinnvis representasjon av en løsning på et gitt problem.
  • I en algoritme er problemet brutt ned i mindre biter eller trinn, derfor er det lettere for programmereren å konvertere det til et faktisk program.

Ulemper med algoritmer:

  • Å skrive en algoritme tar lang tid, så det er tidkrevende.
  • Å forstå kompleks logikk gjennom algoritmer kan være svært vanskelig.
  • Forgrenings- og sløyfeutsagn er vanskelig å vise i algoritmer (imp) .

Hvordan designe en algoritme?

For å skrive en algoritme er følgende ting nødvendig som en forutsetning:

imessage-spill med Android
  1. De problem som skal løses med denne algoritmen, dvs. klar problemdefinisjon.
  2. De begrensninger av problemet må vurderes mens du løser problemet.
  3. De input som skal tas for å løse problemet.
  4. De produksjon er å forvente når problemet er løst.
  5. De løsning til dette problemet er innenfor de gitte begrensningene.

Deretter skrives algoritmen ved hjelp av parametrene ovenfor slik at den løser problemet.

Eksempel: Tenk på eksempelet for å legge til tre tall og skrive ut summen.

Trinn 1: Oppfylle forutsetningene

Som diskutert ovenfor, for å skrive en algoritme, må dens forutsetninger være oppfylt.

  1. Problemet som skal løses med denne algoritmen : Legg til 3 tall og skriv ut summen deres.
  2. Begrensningene til problemet som må vurderes mens du løser problemet : Tallene må kun inneholde sifre og ingen andre tegn.
  3. Innspillet som skal tas for å løse problemet: De tre tallene som skal legges til.
  4. Utgangen som kan forventes når problemet er løst: Summen av de tre tallene tatt som inngang, dvs. en enkelt heltallsverdi.
  5. Løsningen på dette problemet, i de gitte begrensningene: Løsningen består i å legge sammen de 3 tallene. Det kan gjøres ved hjelp av '+'-operatøren, eller bitvis, eller en hvilken som helst annen metode.


Trinn 2: Utforming av algoritmen

La oss nå designe algoritmen ved hjelp av de ovennevnte forutsetningene:

Algoritme for å legge til 3 tall og skrive ut summen deres:

  1. START
  2. Deklarer 3 heltallsvariabler num1, num2 og num3.
  3. Ta de tre tallene, som skal legges til, som input i henholdsvis variablene num1, num2 og num3.
  4. Deklarer en heltallsvariabel sum for å lagre den resulterende summen av de 3 tallene.
  5. Legg til de 3 tallene og lagre resultatet i variabelsummen.
  6. Skriv ut verdien av den variable summen
  7. SLUTT


Trinn 3: Testing av algoritmen ved å implementere den.

For å teste algoritmen, la oss implementere den i C-språk.

Program:

C++ // C++ program to add three numbers // with the help of above designed // algorithm #include using namespace std; int main() { // Variables to take the input of // the 3 numbers int num1, num2, num3; // Variable to store the resultant sum int sum; // Take the 3 numbers as input cout << 'Enter the 1st number: '; cin>> num1; cout<< ' ' << num1 << endl; cout << 'Enter the 2nd number: '; cin>> num2; cout<< ' ' << num2 << endl; cout << 'Enter the 3rd number: '; cin>> num3; cout<< ' ' << num3; // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3; // Print the sum cout << ' Sum of the 3 numbers is: ' << sum; return 0; } // This code is contributed by shivanisinghss2110>C // C program to add three numbers // with the help of above designed algorithm #include int main() { // Variables to take the input of the 3 numbers int num1, num2, num3; // Variable to store the resultant sum int sum; // Take the 3 numbers as input printf('Enter the 1st number: '); scanf('%d', &num1); printf('%d ', num1); printf('Enter the 2nd number: '); scanf('%d', &num2); printf('%d ', num2); printf('Enter the 3rd number: '); scanf('%d', &num3); printf('%d ', num3); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3; // Print the sum printf(' Sum of the 3 numbers is: %d', sum); return 0; }>Java // Java program to add the three numbers // with the help of above designed // algorithm import java.util.*; class GFG { public static void main(String[] args) { // Variable to store the resultant sum int sum = 0; // Declare the object and initialize with // predefined standard input object Scanner sc = new Scanner(System.in); // Scanner definition // Variables to take the input of // the 3 numbers System.out.println('Enter the 1st number: '); int num1 = sc.nextInt(); // input is an Integer // read by nextInt() function System.out.println(' ' + num1); System.out.println('Enter the 2nd number: '); int num2 = sc.nextInt(); System.out.println(' ' + num2); System.out.println('Enter the 3rd number: '); int num3 = sc.nextInt(); System.out.println(' ' + num3); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3; System.out.println('Sum of the 3 numbers is = ' + sum); } } /*This code is contributed by Rishab Dugar*/>Python # Python3 program to add three numbers # with the help of above designed # algorithm if __name__ == '__main__': # Variables to take the input of # the 3 numbers num1 = num2 = num3 = 0 # Variable to store the resultant sum sum = 0 # Take the 3 numbers as input num1 = int(input('Enter the 1st number: ')) num2 = int(input('Enter the 2nd number: ')) num3 = int(input('Enter the 3rd number: ')) # Calculate the sum using + operator # and store it in variable sum sum = num1 + num2 + num3 # Print the sum print(' Sum of the 3 numbers is:', sum)>C# // C# program to add the three numbers // with the help of above designed // algorithm using System; class GFG { static public void Main () { // Variable to store the resultant sum int sum = 0; // Variables to take the input of // the 3 numbers Console.Write('Enter the 1st number: '); int num1 = int.Parse(Console.ReadLine()); Console.WriteLine(' ' + num1); Console.Write('Enter the 2nd number: '); int num2 = int.Parse(Console.ReadLine()); Console.WriteLine(' ' + num2); Console.Write('Enter the 3rd number: '); int num3 = int.Parse(Console.ReadLine()); Console.WriteLine(' ' + num3); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3; Console.WriteLine('Sum of the 3 numbers is = ' + sum); } } /*This code is contributed by Pushpesh Raj*/>Javascript // Javascript program to add three numbers // with the help of above designed // algorithm // Variables to take the input of // the 3 numbers let num1 = 0, num2 = 0, num3 = 0; // Variable to store the resultant sum let sum = 0; // Take the 3 numbers as input console.log('Enter the 1st number: '); num1 = parseInt(prompt()); console.log(' ' + num1 + ' '); console.log('Enter the 2nd number: '); num2=parseInt(prompt()); console.log(' ' + num2 + ' '); console.log('Enter the 3rd number: '); num3=parseInt(prompt()); console.log(' ' + num3); // Calculate the sum using + operator // and store it in variable sum sum = num1 + num2 + num3; // Print the sum console.log(' Sum of the 3 numbers is: ' + sum); // This code is contributed by Aman Kumar>
Produksjon

Tast inn det første tallet: 0 Tast inn det andre tallet: 0 Tast inn det tredje tallet: -1577141152 Summen av de 3 tallene er: -1577141152

Her er trinn-for-trinn-algoritmen til koden:

  1. Deklarer tre variabler num1, num2 og num3 for å lagre de tre tallene som skal legges til.
  2. Deklarer en variabel sum for å lagre summen av de tre tallene.
  3. Bruk cout-setningen for å be brukeren om å skrive inn det første tallet.
  4. Bruk cin-setningen til å lese det første tallet og lagre det i num1.
  5. Bruk cout-setningen for å be brukeren om å angi det andre tallet.
  6. Bruk cin-setningen til å lese det andre tallet og lagre det i num2.
  7. Bruk cout-setningen for å be brukeren om å angi det tredje tallet.
  8. Bruk cin-setningen til å lese og lagre det tredje tallet i num3.
  9. Beregn summen av de tre tallene ved å bruke +-operatoren og lagre den i sumvariabelen.
  10. Bruk cout-setningen til å skrive ut summen av de tre tallene.
  11. Hovedfunksjonen returnerer 0, som indikerer vellykket kjøring av programmet.

Tidskompleksitet: O(1)
Hjelpeplass: O(1)

Ett problem, mange løsninger: Løsningen til en algoritme kan være eller kan ikke være mer enn én. Det betyr at mens du implementerer algoritmen, kan det være mer enn én metode for å implementere den. For eksempel, i problemet ovenfor med å legge til 3 tall, kan summen beregnes på mange måter:

  • + operatør
  • Bitvise operatører
  • . . etc

Hvordan analysere en algoritme?

For at en standardalgoritme skal være god, må den være effektiv. Derfor må effektiviteten til en algoritme kontrolleres og vedlikeholdes. Det kan være i to stadier:

1. Prioriteringsanalyse:

Priori betyr før. Derfor betyr Priori-analyse å sjekke algoritmen før den implementeres. I denne sjekkes algoritmen når den skrives i form av teoretiske trinn. Denne effektiviteten til en algoritme måles ved å anta at alle andre faktorer, for eksempel prosessorhastighet, er konstante og ikke har noen effekt på implementeringen. Dette gjøres vanligvis av algoritmedesigneren. Denne analysen er uavhengig av type maskinvare og språk til kompilatoren. Den gir omtrentlige svar for kompleksiteten til programmet.

2. Posterior analyse:

Posterior betyr etter. Derfor betyr posterior analyse å sjekke algoritmen etter implementeringen. I denne sjekkes algoritmen ved å implementere den i et hvilket som helst programmeringsspråk og utføre den. Denne analysen hjelper til med å få den faktiske og reelle analyserapporten om korrekthet (for alle mulige input/er om den viser/returnerer riktig utgang eller ikke), plasskrevende, tidsbrukt osv. Det vil si at den er avhengig av språket til kompilator og type maskinvare som brukes.

Hva er algoritmekompleksitet og hvordan finner jeg den?

En algoritme er definert som kompleks basert på hvor mye plass og tid den bruker. Derfor refererer kompleksiteten til en algoritme til målet for tiden den trenger for å utføre og få forventet utgang, og plassen den trenger for å lagre alle dataene (inndata, midlertidige data og utdata). Derfor definerer disse to faktorene effektiviteten til en algoritme.
De to faktorene for algoritmekompleksitet er:

  • Tidsfaktor : Tid måles ved å telle antall nøkkeloperasjoner som sammenligninger i sorteringsalgoritmen.
  • Plassfaktor : Plass måles ved å telle den maksimale minneplassen som kreves av algoritmen for å kjøre/utføre.

Derfor kompleksiteten til en algoritme kan deles inn i to typer :

1. Plass kompleksitet : Plasskompleksiteten til en algoritme refererer til mengden minne som kreves av algoritmen for å lagre variablene og få resultatet. Dette kan være for innganger, midlertidige operasjoner eller utganger.

prioritert kø java

Hvordan beregne romkompleksitet?
Romkompleksiteten til en algoritme beregnes ved å bestemme følgende 2 komponenter:

  • Fast del: Dette refererer til plassen som kreves av algoritmen. For eksempel inngangsvariabler, utdatavariabler, programstørrelse osv.
  • Variabel del: Dette refererer til rommet som kan være forskjellig basert på implementeringen av algoritmen. For eksempel midlertidige variabler, dynamisk minneallokering, rekursjonsstabelplass, etc.
    Derfor Space kompleksitet S(P) av enhver algoritme P er S(P) = C + SP(I) , hvor C er den faste delen og S(I) er den variable delen av algoritmen, som avhenger av instanskarakteristikk I.

Eksempel: Tenk på algoritmen nedenfor for lineært søk

Trinn 1: START
Trinn 2: Få n elementer av matrisen i arr og tallet som skal søkes i x
Trinn 3: Start fra elementet lengst til venstre i arr[] og en etter en sammenlign x med hvert element i arr[]
Trinn 4: Hvis x samsvarer med et element, skriv ut sant.
Trinn 5: Hvis x ikke samsvarer med noen av elementene, skriv ut usann.
Trinn 6: AVSLUTT
Her er det 2 variabler arr[], og x, der arr[] er den variable delen av n elementer og x er den faste delen. Derfor S(P) = 1+n. Så romkompleksiteten avhenger av n(antall elementer). Nå avhenger plass av datatyper for gitte variabler og konstanttyper, og det vil multipliseres tilsvarende.

2. Tidskompleksitet : Tidskompleksiteten til en algoritme refererer til hvor lang tid som kreves av algoritmen for å utføre og få resultatet. Dette kan være for vanlige operasjoner, betingede if-else-setninger, loop-setninger, etc.

Hvordan regne ut , Tidskompleksitet?
Tidskompleksiteten til en algoritme beregnes også ved å bestemme følgende 2 komponenter:

  • Konstant tidsdel: Enhver instruksjon som utføres bare én gang kommer i denne delen. For eksempel input, output, if-else, switch, aritmetiske operasjoner, etc.
  • Variabel tidsdel: Enhver instruksjon som utføres mer enn én gang, for eksempel n ganger, kommer i denne delen. For eksempel loops, rekursjon osv.
    Derfor TidskompleksitetT(P) av enhver algoritme P er T(P) = C + TP(I) , hvor C er konstanttidsdelen og TP(I) er den variable delen av algoritmen, som avhenger av instanskarakteristikken I.

Eksempel: I algoritmen til Lineært søk ovenfor beregnes tidskompleksiteten som følger:

Trinn 1: – Konstant tid
Trinn 2: — Variabel tid (tar n innganger)
Trinn 3: – Variabel tid (Til lengden på Arrayen (n) eller indeksen til det funnet elementet)
Trinn 4: – Konstant tid
Trinn 5: – Konstant tid
Trinn 6: – Konstant tid
Derfor er T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, som kan sies som T(n).

Hvordan uttrykke en algoritme?

  1. Naturlig språk:- Her uttrykker vi Algoritmen på det naturlige engelske språket. Det er for vanskelig å forstå algoritmen fra det.
  2. Flytskjema :- Her uttrykker vi algoritmen ved å lage en grafisk/bildefremstilling av det. Det er lettere å forstå enn naturlig språk.
  3. Pseudokode :- Her uttrykker vi algoritmen i form av merknader og informativ tekst skrevet på vanlig engelsk som er veldig lik den virkelige koden, men siden den ikke har noen syntaks som noen av programmeringsspråkene, kan den ikke kompileres eller tolkes av datamaskinen . Det er den beste måten å uttrykke en algoritme på fordi den kan forstås av til og med en lekmann med noe kunnskap på skolenivå.