logo

TechCodeview

Hvad er algoritme | Introduktion til algoritmer

Definition af algoritme

Ordet Algoritme midler Et sæt af begrænsede regler eller instruktioner, der skal følges ved beregninger eller andre problemløsningsoperationer
Eller
En procedure til at løse et matematisk problem i et begrænset antal trin, der ofte involverer rekursive operationer .

Derfor refererer Algoritme til en sekvens af endelige trin til at løse et bestemt problem.

java stakke
Hvad er algoritme

Brug af algoritmerne:

Algoritmer spiller en afgørende rolle på forskellige områder og har mange anvendelsesmuligheder. Nogle af nøgleområderne, hvor algoritmer bruges, omfatter:



  1. Computer videnskab: Algoritmer danner grundlaget for computerprogrammering og bruges til at løse problemer lige fra simpel sortering og søgning til komplekse opgaver såsom kunstig intelligens og maskinlæring.
  2. Matematik: Algoritmer bruges til at løse matematiske problemer, såsom at finde den optimale løsning på et system af lineære ligninger eller finde den korteste vej i en graf.
  3. Operationsforskning : Algoritmer bruges til at optimere og træffe beslutninger inden for områder som transport, logistik og ressourceallokering.
  4. Kunstig intelligens: Algoritmer er grundlaget for kunstig intelligens og maskinlæring og bruges til at udvikle intelligente systemer, der kan udføre opgaver som billedgenkendelse, naturlig sprogbehandling og beslutningstagning.
  5. Datavidenskab: Algoritmer bruges til at analysere, behandle og udtrække indsigt fra store mængder data inden for områder som marketing, økonomi og sundhedspleje.

Dette er blot nogle få eksempler på de mange anvendelser af algoritmer. Brugen af ​​algoritmer udvides løbende, efterhånden som nye teknologier og områder dukker op, hvilket gør det til en vital komponent i det moderne samfund.

Algoritmer kan være enkle og komplekse afhængigt af, hvad du ønsker at opnå.

Det kan forstås ved at tage eksemplet med at lave en ny opskrift. For at tilberede en ny opskrift læser man instruktionerne og trinene og udfører dem én efter én i den givne rækkefølge. Det opnåede resultat er, at den nye ret er perfekt tilberedt. Hver gang du bruger din telefon, computer, bærbare computer eller lommeregner, bruger du algoritmer. På samme måde hjælper algoritmer med at udføre en opgave i programmering for at få det forventede output.

Algoritmen, der er designet, er sproguafhængig, dvs. de er blot almindelige instruktioner, der kan implementeres på ethvert sprog, og alligevel vil outputtet være det samme, som forventet.

Hvad er behovet for algoritmer?

  1. Algoritmer er nødvendige for at løse komplekse problemer effektivt og effektivt.
  2. De hjælper med at automatisere processer og gøre dem mere pålidelige, hurtigere og nemmere at udføre.
  3. Algoritmer gør det også muligt for computere at udføre opgaver, som ville være vanskelige eller umulige for mennesker at udføre manuelt.
  4. De bruges inden for forskellige områder såsom matematik, datalogi, teknik, økonomi og mange andre til at optimere processer, analysere data, lave forudsigelser og give løsninger på problemer.

Hvad er kendetegnene ved en algoritme?

Egenskaber for en algoritme

Da man ikke ville følge nogen skriftlige instruktioner for at tilberede opskriften, men kun standarden. På samme måde er ikke alle skriftlige instruktioner til programmering en algoritme. For at nogle instruktioner skal være en algoritme, skal den have følgende egenskaber:

  • Klart og utvetydigt : Algoritmen skal være utvetydig. Hvert af dets trin skal være klart i alle aspekter og skal kun føre til én mening.
  • Veldefinerede input : Hvis en algoritme siger, at man skal tage input, skal det være veldefinerede input. Det kan tage input eller ikke.
  • Veldefinerede output: Algoritmen skal klart definere, hvilket output der vil blive givet, og det skal også være veldefineret. Det skal producere mindst 1 output.
  • Endelighed: Algoritmen skal være endelig, dvs. den skal afsluttes efter en begrænset tid.
  • Gennemførlig: Algoritmen skal være enkel, generisk og praktisk, således at den kan udføres med de tilgængelige ressourcer. Det må ikke indeholde en eller anden fremtidig teknologi eller noget.
  • Sproguafhængig: Algoritmen, der er designet, skal være sproguafhængig, dvs. den skal blot være almindelige instruktioner, der kan implementeres på ethvert sprog, og alligevel vil outputtet være det samme, som forventet.
  • Input : En algoritme har nul eller flere input. Hver, der indeholder en grundlæggende operator, skal acceptere nul eller flere input.
  • Produktion : En algoritme producerer mindst ét ​​output. Enhver instruktion, der indeholder en grundlæggende operator, skal acceptere nul eller flere input.
  • Bestemthed: Alle instruktioner i en algoritme skal være entydige, præcise og lette at fortolke. Ved at henvise til en hvilken som helst af instruktionerne i en algoritme kan man tydeligt forstå, hvad der skal gøres. Enhver grundlæggende operatør i instruktion skal defineres uden nogen tvetydighed.
  • Endelighed: En algoritme skal afsluttes efter et begrænset antal trin i alle testtilfælde. Enhver instruktion, der indeholder en fundamental operator, skal afsluttes inden for en begrænset tid. Uendelige sløjfer eller rekursive funktioner uden basisbetingelser besidder ikke endelighed.
  • Effektivitet: En algoritme skal udvikles ved at bruge meget grundlæggende, enkle og gennemførlige operationer, så man kan spore den ud ved kun at bruge papir og blyant.

Egenskaber for algoritme:

  • Det bør afsluttes efter en begrænset tid.
  • Det skal producere mindst ét ​​output.
  • Det bør tage nul eller mere input.
  • Det bør være deterministiske midler, der giver det samme output for det samme inputtilfælde.
  • Hvert trin i algoritmen skal være effektivt, dvs. hvert trin skal gøre noget arbejde.

Typer af algoritmer:

Der findes flere typer algoritmer. Nogle vigtige algoritmer er:

1. Brute Force Algoritme :

Det er den enkleste tilgang til et problem. En brute force-algoritme er den første tilgang, der kommer til at finde, når vi ser et problem.

2. Rekursiv algoritme :

En rekursiv algoritme er baseret på rekursion . I dette tilfælde er et problem opdelt i flere underdele og kaldes den samme funktion igen og igen.

3. Tilbagesporingsalgoritme :

Backtracking-algoritmen bygger løsningen ved at søge blandt alle mulige løsninger. Ved at bruge denne algoritme fortsætter vi med at bygge løsningen efter kriterier. Når en løsning mislykkes, sporer vi tilbage til fejlpunktet og bygger videre på den næste løsning og fortsætter denne proces, indtil vi finder løsningen, eller alle mulige løsninger er passet.

4. Søgealgoritme :

Søgealgoritmer er dem, der bruges til at søge i elementer eller grupper af elementer fra en bestemt datastruktur. De kan være af forskellige typer baseret på deres tilgang eller den datastruktur, som elementet skal findes i.

5. Sorteringsalgoritme :

Sortering er at arrangere en gruppe af data på en bestemt måde i henhold til kravet. Algoritmerne, der hjælper med at udføre denne funktion, kaldes sorteringsalgoritmer. Generelt bruges sorteringsalgoritmer til at sortere grupper af data på en stigende eller faldende måde.

6. Hashing-algoritme :

Hashing-algoritmer fungerer på samme måde som søgealgoritmen. Men de indeholder et indeks med et nøgle-id. Ved hashing tildeles en nøgle til specifikke data.

7. Divide and Conquer-algoritme :

Denne algoritme opdeler et problem i underproblemer, løser et enkelt underproblem og slår løsningerne sammen for at få den endelige løsning. Den består af følgende tre trin:

  • Dele
  • Løse
  • Forene

8. Grådig algoritme :

I denne type algoritme bygges løsningen del for del. Løsningen til næste del er bygget ud fra den umiddelbare fordel af den næste del. Den løsning, der giver mest udbytte, vil blive valgt som løsning til næste del.

9. Dynamisk programmeringsalgoritme :

Denne algoritme bruger konceptet med at bruge den allerede fundne løsning for at undgå gentagne beregninger af den samme del af problemet. Det opdeler problemet i mindre overlappende delproblemer og løser dem.

10. Randomiseret algoritme :

I den randomiserede algoritme bruger vi et tilfældigt tal, så det giver øjeblikkelig fordel. Det tilfældige tal hjælper med at bestemme det forventede resultat.

For at lære mere om typerne af algoritmer henvises til artiklen om Typer af algoritmer .

Fordele ved algoritmer:

  • Det er let at forstå.
  • En algoritme er en trinvis repræsentation af en løsning på et givet problem.
  • I en algoritme er problemet opdelt i mindre stykker eller trin, så det er lettere for programmøren at konvertere det til et egentligt program.

Ulemper ved algoritmer:

  • At skrive en algoritme tager lang tid, så det er tidskrævende.
  • Det kan være meget svært at forstå kompleks logik gennem algoritmer.
  • Forgrenings- og løkkeudsagn er svære at vise i algoritmer (imp) .

Hvordan designer man en algoritme?

For at skrive en algoritme er følgende ting nødvendige som en forudsætning:

imessage spil med Android
  1. Det problem det skal løses med denne algoritme, dvs. klar problemdefinition.
  2. Det begrænsninger af problemet skal overvejes, mens problemet løses.
  3. Det input skal tages for at løse problemet.
  4. Det produktion kan forventes, når problemet er løst.
  5. Det løsning til dette problem er inden for de givne begrænsninger.

Derefter skrives algoritmen ved hjælp af ovenstående parametre, så den løser problemet.

Eksempel: Overvej eksemplet for at tilføje tre tal og udskrive summen.

Trin 1: Opfyldelse af forudsætningerne

Som diskuteret ovenfor, for at skrive en algoritme, skal dens forudsætninger være opfyldt.

  1. Problemet, der skal løses med denne algoritme : Tilføj 3 tal og udskriv deres sum.
  2. Problemets begrænsninger, der skal overvejes, mens problemet løses : Tallene må kun indeholde cifre og ingen andre tegn.
  3. De input, der skal tages for at løse problemet: De tre tal skal tilføjes.
  4. Det output, der kan forventes, når problemet er løst: Summen af ​​de tre tal taget som input, dvs. en enkelt heltalsværdi.
  5. Løsningen på dette problem, i de givne begrænsninger: Løsningen består i at lægge de 3 tal sammen. Det kan gøres ved hjælp af '+'-operatoren, eller bit-wise eller en hvilken som helst anden metode.


Trin 2: Design af algoritmen

Lad os nu designe algoritmen ved hjælp af ovenstående forudsætninger:

Algoritme til at tilføje 3 tal og udskrive deres sum:

  1. START
  2. Deklarer 3 heltalsvariable num1, num2 og num3.
  3. Tag de tre tal, der skal tilføjes, som input i variablerne henholdsvis num1, num2 og num3.
  4. Deklarer en heltalsvariabel sum for at gemme den resulterende sum af de 3 tal.
  5. Tilføj de 3 tal og gem resultatet i den variable sum.
  6. Udskriv værdien af ​​den variable sum
  7. ENDE


Trin 3: Test af algoritmen ved at implementere den.

For at teste algoritmen, lad os implementere den i C-sprog.

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>
Produktion

Indtast 1. tal: 0 Indtast 2. tal: 0 Indtast 3. tal: -1577141152 Summen af ​​de 3 tal er: -1577141152

Her er kodens trin-for-trin algoritme:

  1. Deklarer tre variable num1, num2 og num3 for at gemme de tre tal, der skal tilføjes.
  2. Deklarer en variabel sum for at gemme summen af ​​de tre tal.
  3. Brug cout-sætningen til at bede brugeren om at indtaste det første tal.
  4. Brug cin-sætningen til at læse det første tal og gemme det i num1.
  5. Brug cout-sætningen til at bede brugeren om at indtaste det andet tal.
  6. Brug cin-sætningen til at læse det andet tal og gemme det i num2.
  7. Brug cout-sætningen til at bede brugeren om at indtaste det tredje tal.
  8. Brug cin-sætningen til at læse og gemme det tredje tal i num3.
  9. Beregn summen af ​​de tre tal ved hjælp af +-operatoren og gem den i sumvariablen.
  10. Brug cout-sætningen til at udskrive summen af ​​de tre tal.
  11. Hovedfunktionen returnerer 0, hvilket indikerer den succesfulde udførelse af programmet.

Tidskompleksitet: O(1)
Hjælpeplads: O(1)

Et problem, mange løsninger: Løsningen til en algoritme kan være eller kan ikke være mere end én. Det betyder, at mens du implementerer algoritmen, kan der være mere end én metode til at implementere den. For eksempel, i ovenstående problem med at tilføje 3 tal, kan summen beregnes på mange måder:

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

Hvordan analyserer man en algoritme?

For at en standardalgoritme skal være god, skal den være effektiv. Derfor skal effektiviteten af ​​en algoritme kontrolleres og vedligeholdes. Det kan være i to faser:

1. Prioriteringsanalyse:

Priori betyder før. Derfor betyder Priori-analyse at kontrollere algoritmen før dens implementering. Heri tjekkes algoritmen, når den skrives i form af teoretiske trin. Denne effektivitet af en algoritme måles ved at antage, at alle andre faktorer, for eksempel processorhastighed, er konstante og ikke har nogen indflydelse på implementeringen. Dette gøres normalt af algoritmedesigneren. Denne analyse er uafhængig af typen af ​​hardware og compilerens sprog. Det giver de omtrentlige svar for programmets kompleksitet.

2. Posterior analyse:

Posterior betyder efter. Derfor betyder posterior analyse at kontrollere algoritmen efter dens implementering. I denne kontrolleres algoritmen ved at implementere den i et hvilket som helst programmeringssprog og udføre den. Denne analyse hjælper med at få den faktiske og reelle analyserapport om korrekthed (for alle mulige input/s, hvis det viser/returnerer korrekt output eller ej), krævet plads, tidsforbrug osv. Det vil sige, det afhænger af sproget i compiler og den anvendte type hardware.

Hvad er algoritmekompleksitet, og hvordan finder man den?

En algoritme er defineret som kompleks baseret på mængden af ​​plads og tid, den bruger. Derfor refererer kompleksiteten af ​​en algoritme til målet for den tid, den skal bruge til at udføre og få det forventede output, og det rum, det skal bruge til at gemme alle data (input, midlertidige data og output). Derfor definerer disse to faktorer effektiviteten af ​​en algoritme.
De to faktorer af algoritmekompleksitet er:

  • Tidsfaktor : Tid måles ved at tælle antallet af nøgleoperationer såsom sammenligninger i sorteringsalgoritmen.
  • Rumfaktor : Plads måles ved at tælle den maksimale hukommelsesplads, der kræves af algoritmen for at køre/udføre.

Derfor kompleksiteten af ​​en algoritme kan opdeles i to typer :

1. Rumkompleksitet : Rumkompleksiteten af ​​en algoritme refererer til mængden af ​​hukommelse, der kræves af algoritmen for at gemme variablerne og få resultatet. Dette kan være til input, midlertidige operationer eller output.

prioriteret kø java

Hvordan beregner man rumkompleksitet?
Rumkompleksiteten af ​​en algoritme beregnes ved at bestemme følgende 2 komponenter:

  • Fast del: Dette refererer til den plads, der kræves af algoritmen. For eksempel inputvariabler, outputvariabler, programstørrelse osv.
  • Variabel del: Dette refererer til det rum, der kan være anderledes baseret på implementeringen af ​​algoritmen. For eksempel midlertidige variabler, dynamisk hukommelsesallokering, rekursionsstackplads osv.
    Derfor Space kompleksitet S(P) af enhver algoritme P er S(P) = C + SP(I) , hvor C er den faste del og S(I) er den variable del af algoritmen, som afhænger af instanskarakteristik I.

Eksempel: Overvej nedenstående algoritme for lineær søgning

Trin 1: START
Trin 2: Hent n elementer af arrayet i arr og nummeret, der skal søges i, i x
Trin 3: Start fra elementet længst til venstre i arr[] og en efter en sammenlign x med hvert element i arr[]
Trin 4: Hvis x matcher et element, skal du udskrive sandt.
Trin 5: Hvis x ikke stemmer overens med nogen af ​​elementerne, udskriv falsk.
Trin 6: AFSLUT
Her er der 2 variabler arr[], og x, hvor arr[] er den variable del af n elementer og x er den faste del. Derfor er S(P) = 1+n. Så rummets kompleksitet afhænger af n (antal elementer). Nu afhænger plads af datatyper af givne variable og konstanttyper, og det vil blive multipliceret i overensstemmelse hermed.

2. Tidskompleksitet : Tidskompleksiteten af ​​en algoritme refererer til mængden af ​​tid, der kræves af algoritmen for at udføre og få resultatet. Dette kan være til normale operationer, betingede if-else-sætninger, loop-sætninger osv.

Sådan beregnes , Tidskompleksitet?
Tidskompleksiteten af ​​en algoritme beregnes også ved at bestemme følgende 2 komponenter:

  • Konstant tidsdel: Enhver instruktion, der kun udføres én gang, kommer i denne del. For eksempel input, output, if-else, switch, aritmetiske operationer osv.
  • Variabel tidsdel: Enhver instruktion, der udføres mere end én gang, f.eks. n gange, kommer i denne del. Fx loops, rekursion mv.
    Derfor TidskompleksitetT(P) af enhver algoritme P er T(P) = C + TP(I) , hvor C er den konstante tidsdel og TP(I) er den variable del af algoritmen, som afhænger af instanskarakteristikken I.

Eksempel: I algoritmen til Lineær søgning ovenfor beregnes tidskompleksiteten som følger:

Trin 1: – Konstant tid
Trin 2: — Variabel tid (tager n input)
Trin 3: – Variabel tid (indtil længden af ​​arrayet (n) eller indekset for det fundne element)
Trin 4: – Konstant tid
Trin 5: – Konstant tid
Trin 6: – Konstant tid
Derfor er T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, hvilket kan siges som T(n).

Hvordan udtrykker man en algoritme?

  1. Naturligt sprog:- Her udtrykker vi Algoritmen på det naturlige engelske sprog. Det er for svært at forstå algoritmen ud fra det.
  2. Flowchart :- Her udtrykker vi Algoritmen ved at lave en grafisk/billedlig fremstilling af det. Det er lettere at forstå end naturligt sprog.
  3. Pseudo kode :- Her udtrykker vi algoritmen i form af anmærkninger og informativ tekst skrevet på almindeligt engelsk, som er meget lig den rigtige kode, men da den ikke har nogen syntaks som nogen af ​​programmeringssprogene, kan den ikke kompileres eller fortolkes af computeren . Det er den bedste måde at udtrykke en algoritme på, fordi den kan forstås af selv en lægmand med en vis viden på skoleniveau.