Definition av Algoritm
Ordet Algoritm betyder En uppsättning ändliga regler eller instruktioner som ska följas vid beräkningar eller andra problemlösningsoperationer
Eller
En procedur för att lösa ett matematiskt problem i ett begränsat antal steg som ofta involverar rekursiva operationer .
Därför hänvisar Algoritm till en sekvens av ändliga steg för att lösa ett visst problem.
Användning av algoritmerna:
Algoritmer spelar en avgörande roll inom olika områden och har många tillämpningar. Några av nyckelområdena där algoritmer används inkluderar:
- Datavetenskap: Algoritmer utgör grunden för datorprogrammering och används för att lösa problem som sträcker sig från enkel sortering och sökning till komplexa uppgifter som artificiell intelligens och maskininlärning.
- Matematik: Algoritmer används för att lösa matematiska problem, som att hitta den optimala lösningen på ett system av linjära ekvationer eller att hitta den kortaste vägen i en graf.
- Operationsforskning : Algoritmer används för att optimera och fatta beslut inom områden som transport, logistik och resursallokering.
- Artificiell intelligens: Algoritmer är grunden för artificiell intelligens och maskininlärning och används för att utveckla intelligenta system som kan utföra uppgifter som bildigenkänning, naturlig språkbehandling och beslutsfattande.
- Datavetenskap: Algoritmer används för att analysera, bearbeta och extrahera insikter från stora mängder data inom områden som marknadsföring, ekonomi och hälsovård.
Detta är bara några exempel på många tillämpningar av algoritmer. Användningen av algoritmer expanderar kontinuerligt i takt med att nya tekniker och fält dyker upp, vilket gör det till en viktig komponent i det moderna samhället.
java färger
Algoritmer kan vara enkla och komplexa beroende på vad du vill uppnå.
Det kan förstås genom att ta exemplet med att laga ett nytt recept. För att laga ett nytt recept läser man instruktionerna och stegen och utför dem en efter en, i den givna sekvensen. Resultatet som erhålls på detta sätt är att den nya rätten är perfekt tillagad. Varje gång du använder din telefon, dator, bärbara dator eller miniräknare använder du algoritmer. På liknande sätt hjälper algoritmer till att göra en uppgift i programmering för att få den förväntade utdata.
Algoritmen som är designad är språkoberoende, det vill säga de är bara vanliga instruktioner som kan implementeras på vilket språk som helst, och ändå blir resultatet detsamma, som förväntat.
Vad är behovet av algoritmer?
- Algoritmer är nödvändiga för att lösa komplexa problem effektivt och effektivt.
- De hjälper till att automatisera processer och göra dem mer tillförlitliga, snabbare och enklare att utföra.
- Algoritmer gör det också möjligt för datorer att utföra uppgifter som skulle vara svåra eller omöjliga för människor att utföra manuellt.
- De används inom olika områden som matematik, datavetenskap, teknik, ekonomi och många andra för att optimera processer, analysera data, göra förutsägelser och ge lösningar på problem.
Vad är egenskaperna hos en algoritm?
Då man inte skulle följa några skriftliga instruktioner för att laga receptet, utan bara det vanliga. På samma sätt är inte alla skrivna instruktioner för programmering en algoritm. För att vissa instruktioner ska vara en algoritm måste den ha följande egenskaper:
- Tydligt och otvetydigt : Algoritmen ska vara entydig. Vart och ett av dess steg bör vara tydligt i alla aspekter och måste leda till endast en mening.
- Väldefinierade ingångar : Om en algoritm säger att man ska ta indata bör det vara väldefinierade ingångar. Det kan ta input eller inte.
- Väldefinierade utgångar: Algoritmen måste tydligt definiera vilken utdata som kommer att ge och den bör också vara väldefinierad. Den bör producera minst 1 utgång.
- ändlighet: Algoritmen måste vara ändlig, dvs den ska avslutas efter en ändlig tid.
- Möjlig: Algoritmen måste vara enkel, generisk och praktisk, så att den kan exekveras med tillgängliga resurser. Den får inte innehålla någon framtida teknik eller något.
- Språkoberoende: Den designade algoritmen måste vara språkoberoende, d.v.s. den måste bara vara enkla instruktioner som kan implementeras på vilket språk som helst, och ändå blir resultatet detsamma, som förväntat.
- Inmatning : En algoritm har noll eller fler ingångar. Var och en som innehåller en grundläggande operator måste acceptera noll eller fler indata.
- Produktion : En algoritm producerar minst en utdata. Varje instruktion som innehåller en grundläggande operator måste acceptera noll eller fler indata.
- Bestämdhet: Alla instruktioner i en algoritm måste vara entydiga, exakta och lätta att tolka. Genom att hänvisa till någon av instruktionerna i en algoritm kan man tydligt förstå vad som ska göras. Varje grundläggande operatör i instruktion måste definieras utan någon tvetydighet.
- Finitet: En algoritm måste avslutas efter ett ändligt antal steg i alla testfall. Varje instruktion som innehåller en fundamental operator måste avslutas inom en begränsad tid. Oändliga loopar eller rekursiva funktioner utan basvillkor har inte finitet.
- Effektivitet: En algoritm måste utvecklas genom att använda mycket grundläggande, enkla och genomförbara operationer så att man kan spåra den med bara papper och penna.
Algoritmens egenskaper:
- Den bör avslutas efter en begränsad tid.
- Det bör producera minst en utgång.
- Det bör ta noll eller mer input.
- Det bör vara deterministiska medel som ger samma utdata för samma ingångsfall.
- Varje steg i algoritmen måste vara effektivt, det vill säga varje steg bör göra en del arbete.
Typer av algoritmer:
Det finns flera typer av algoritmer tillgängliga. Några viktiga algoritmer är:
funktioner i java
1. Brute Force Algorithm :
Det är den enklaste lösningen på ett problem. En brute force-algoritm är det första sättet att hitta när vi ser ett problem.
2. Rekursiv algoritm :
En rekursiv algoritm är baserad på rekursion . I det här fallet är ett problem uppdelat i flera underdelar och kallas samma funktion om och om igen.
3. Backtracking-algoritm :
Backtracking-algoritmen bygger lösningen genom att söka bland alla möjliga lösningar. Med den här algoritmen fortsätter vi att bygga lösningen enligt kriterier. Närhelst en lösning misslyckas spårar vi tillbaka till felpunkten och bygger vidare på nästa lösning och fortsätter denna process tills vi hittar lösningen eller tills alla möjliga lösningar tas om hand.
4. Sökalgoritm :
Sökalgoritmer är de som används för att söka i element eller grupper av element från en viss datastruktur. De kan vara av olika slag beroende på deras tillvägagångssätt eller den datastruktur som elementet ska finnas i.
5. Sorteringsalgoritm :
Sortering är att ordna en grupp av data på ett visst sätt enligt kravet. Algoritmerna som hjälper till att utföra denna funktion kallas sorteringsalgoritmer. Generellt används sorteringsalgoritmer för att sortera grupper av data på ett ökande eller minskande sätt.
6. Hashing-algoritm :
Hashingalgoritmer fungerar på samma sätt som sökalgoritmen. Men de innehåller ett index med ett nyckel-ID. I hashing tilldelas en nyckel till specifik data.
7. Dela och erövra algoritm :
Denna algoritm delar upp ett problem i delproblem, löser ett enda delproblem och slår samman lösningarna för att få den slutliga lösningen. Den består av följande tre steg:
- Dela upp
- Lösa
- Kombinera
8. Girig algoritm :
I denna typ av algoritm byggs lösningen del för del. Lösningen för nästa del är byggd utifrån den omedelbara nyttan av nästa del. Den lösning som ger mest nytta kommer att väljas som lösning för nästa del.
9. Dynamisk programmeringsalgoritm :
Denna algoritm använder konceptet att använda den redan hittade lösningen för att undvika upprepade beräkningar av samma del av problemet. Den delar upp problemet i mindre överlappande delproblem och löser dem.
10. Randomiserad algoritm :
I den randomiserade algoritmen använder vi ett slumptal så det ger omedelbar nytta. Slumptalet hjälper till att avgöra det förväntade resultatet.
spring initializr
För att lära dig mer om typerna av algoritmer, se artikeln om Typer av algoritmer .
Fördelar med algoritmer:
- Det är lätt att förstå.
- En algoritm är en stegvis representation av en lösning på ett givet problem.
- I en algoritm är problemet uppdelat i mindre bitar eller steg och därför är det lättare för programmeraren att konvertera det till ett verkligt program.
Nackdelar med algoritmer:
- Att skriva en algoritm tar lång tid så det är tidskrävande.
- Att förstå komplex logik genom algoritmer kan vara mycket svårt.
- Förgrenings- och loop-påståenden är svåra att visa i Algoritmer (imp) .
Hur designar man en algoritm?
För att skriva en algoritm krävs följande som en förutsättning:
- De problem som ska lösas med denna algoritm, dvs tydlig problemdefinition.
- De begränsningar av problemet måste beaktas när man löser problemet.
- De inmatning ska vidtas för att lösa problemet.
- De produktion är att vänta när problemet är löst.
- De lösning till detta problem ligger inom de givna begränsningarna.
Sedan skrivs algoritmen med hjälp av ovanstående parametrar så att den löser problemet.
Exempel: Betrakta exemplet för att lägga till tre siffror och skriva ut summan.
Steg 1: Uppfylla förutsättningarna
Som diskuterats ovan, för att skriva en algoritm, måste dess förutsättningar vara uppfyllda.
- Problemet som ska lösas med denna algoritm : Lägg till 3 siffror och skriv ut deras summa.
- Problemets begränsningar som måste beaktas när man löser problemet : Siffrorna får endast innehålla siffror och inga andra tecken.
- Input som ska tas för att lösa problemet: De tre siffrorna som ska läggas till.
- Resultatet som kan förväntas när problemet är löst: Summan av de tre talen som tas som indata, dvs ett enstaka heltalsvärde.
- Lösningen på detta problem, i de givna begränsningarna: Lösningen består i att lägga till de 3 siffrorna. Det kan göras med hjälp av '+'-operatorn, eller bitvis eller någon annan metod.
Steg 2: Designa algoritmen
Låt oss nu designa algoritmen med hjälp av ovanstående förutsättningar:
Algoritm för att lägga till 3 siffror och skriva ut deras summa:
- START
- Deklarera 3 heltalsvariabler num1, num2 och num3.
- Ta de tre talen som ska läggas till som indata i variablerna num1, num2 respektive num3.
- Deklarera en heltalsvariabel summa för att lagra den resulterande summan av de 3 talen.
- Lägg till de 3 siffrorna och lagra resultatet i variabelsumman.
- Skriv ut värdet på variabelsumman
- SLUTET
ficklampa installera
Steg 3: Testa algoritmen genom att implementera den.
För att testa algoritmen, låt oss implementera 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*/>Pytonorm # 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
Ange det 1:a numret: 0 Ange det 2:a numret: 0 Ange det 3:e numret: -1577141152 Summan av de 3 siffrorna är: -1577141152
Här är steg-för-steg-algoritmen för koden:
- Deklarera tre variabler num1, num2 och num3 för att lagra de tre talen som ska läggas till.
- Deklarera en variabel summa för att lagra summan av de tre talen.
- Använd cout-satsen för att uppmana användaren att ange den första siffran.
- Använd cin-satsen för att läsa den första siffran och lagra den i num1.
- Använd cout-satsen för att uppmana användaren att ange den andra siffran.
- Använd cin-satsen för att läsa det andra numret och lagra det i num2.
- Använd cout-satsen för att uppmana användaren att ange det tredje numret.
- Använd cin-satsen för att läsa och lagra den tredje siffran i num3.
- Beräkna summan av de tre talen med +-operatorn och lagra den i summavariabeln.
- Använd cout-satsen för att skriva ut summan av de tre siffrorna.
- Huvudfunktionen returnerar 0, vilket indikerar framgångsrik exekvering av programmet.
Tidskomplexitet: O(1)
Hjälputrymme: O(1)
Ett problem, många lösningar: Lösningen på en algoritm kan vara eller kan inte vara mer än en. Det betyder att när du implementerar algoritmen kan det finnas mer än en metod för att implementera den. Till exempel, i ovanstående problem med att lägga till 3 siffror, kan summan beräknas på många sätt:
- + operatör
- Bitvisa operatörer
- . . etc
Hur analyserar man en algoritm?
För att en standardalgoritm ska vara bra måste den vara effektiv. Därför måste effektiviteten hos en algoritm kontrolleras och underhållas. Det kan vara i två steg:
1. Prioriterad analys:
Priori betyder före. Därför innebär Priori-analys att kontrollera algoritmen innan den implementeras. I denna kontrolleras algoritmen när den skrivs i form av teoretiska steg. Denna effektivitet hos en algoritm mäts genom att anta att alla andra faktorer, till exempel processorhastighet, är konstanta och inte har någon effekt på implementeringen. Detta görs vanligtvis av algoritmdesignern. Denna analys är oberoende av typen av hårdvara och kompilatorns språk. Den ger de ungefärliga svaren för programmets komplexitet.
2. Bakre analys:
Posterior betyder efter. Därför innebär posterior analys att kontrollera algoritmen efter dess implementering. I detta kontrolleras algoritmen genom att implementera den i valfritt programmeringsspråk och exekvera den. Denna analys hjälper till att få fram den faktiska och verkliga analysrapporten om korrekthet (för varje möjlig ingång/er om den visar/returnerar korrekt utdata eller inte), utrymme som krävs, tid som går åt, etc. Det vill säga, det är beroende av språket i kompilatorn och vilken typ av hårdvara som används.
Vad är algoritmkomplexitet och hur hittar man den?
En algoritm definieras som komplex baserat på mängden utrymme och tid den förbrukar. Därför hänvisar komplexiteten för en algoritm till måttet på den tid som den kommer att behöva för att exekvera och få den förväntade utdata, och det utrymme som den kommer att behöva för att lagra all data (indata, temporär data och utdata). Därför definierar dessa två faktorer effektiviteten hos en algoritm.
De två faktorerna för algoritmkomplexitet är:
- Tidsfaktor : Tid mäts genom att räkna antalet nyckeloperationer som jämförelser i sorteringsalgoritmen.
- Rymdfaktor : Utrymmet mäts genom att räkna det maximala minnesutrymme som krävs av algoritmen för att köra/köras.
Därför komplexiteten hos en algoritm kan delas in i två typer :
1. Rymdkomplexitet : Utrymmeskomplexiteten hos en algoritm hänvisar till mängden minne som krävs av algoritmen för att lagra variablerna och få resultatet. Detta kan vara för ingångar, tillfälliga operationer eller utgångar.
vad är linux-filsystemet
Hur beräknar man rymdkomplexitet?
Rymdkomplexiteten för en algoritm beräknas genom att bestämma följande två komponenter:
- Fast del: Detta hänvisar till det utrymme som krävs av algoritmen. Till exempel indatavariabler, utdatavariabler, programstorlek osv.
- Variabel del: Detta hänvisar till det utrymme som kan vara annorlunda baserat på implementeringen av algoritmen. Till exempel temporära variabler, dynamisk minnesallokering, rekursionsstackutrymme, etc.
Därför rymdkomplexitet 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å instanskaraktäristik I.
Exempel: Tänk på nedanstående algoritm för linjär sökning
Steg 1: STARTA
Steg 2: Hämta n element av arrayen i arr och numret som ska sökas i x
Steg 3: Börja från elementet längst till vänster i arr[] och en efter en jämför x med varje element i arr[]
Steg 4: Om x matchar ett element, Skriv ut True.
Steg 5: Om x inte matchar något av elementen, Skriv ut Falskt.
Steg 6: AVSLUTA
Här finns det 2 variabler arr[], och x, där arr[] är den variabla delen av n element och x är den fasta delen. Därför S(P) = 1+n. Så rymdkomplexiteten beror på n(antal element). Nu beror utrymmet på datatyper för givna variabler och konstanttyper och det kommer att multipliceras därefter.
2. Tidskomplexitet : Tidskomplexiteten för en algoritm hänvisar till hur lång tid som krävs av algoritmen för att exekvera och få resultatet. Detta kan vara för normala operationer, villkorade if-else-satser, loop-satser, etc.
Hur man beräknar , Tidskomplexitet?
Tidskomplexiteten för en algoritm beräknas också genom att bestämma följande två komponenter:
- Konstant tidsdel: Alla instruktioner som exekveras bara en gång kommer i den här delen. Till exempel input, output, if-else, switch, aritmetiska operationer, etc.
- Variabel tidsdel: Varje instruktion som exekveras mer än en gång, säg n gånger, kommer i den här delen. Till exempel loopar, rekursion osv.
Därför TidskomplexitetT(P) av någon algoritm P är T(P) = C + TP(I) , där C är den konstanta tidsdelen och TP(I) är den variabla delen av algoritmen, vilket beror på instanskaraktäristiken I.
Exempel: I algoritmen för linjär sökning ovan beräknas tidskomplexiteten enligt följande:
Steg 1: – Konstant tid
Steg 2: — Variabel tid (tar n ingångar)
Steg 3: – Variabel tid (till längden på Arrayen (n) eller indexet för det hittade elementet)
Steg 4: – Konstant tid
Steg 5: – Konstant tid
Steg 6: – Konstant tid
Därför är T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, vilket kan sägas som T(n).
Hur uttrycker man en algoritm?
- Naturligt språk:- Här uttrycker vi Algoritmen på det naturliga engelska språket. Det är för svårt att förstå algoritmen utifrån det.
- Flödesschema :- Här uttrycker vi algoritmen genom att göra en grafisk/bildlig representation av den. Det är lättare att förstå än naturligt språk.
- Pseudokod :- Här uttrycker vi algoritmen i form av anteckningar och informativ text skriven på vanlig engelska som är mycket lik den verkliga koden men eftersom den inte har någon syntax som något av programmeringsspråken, kan den inte kompileras eller tolkas av datorn . Det är det bästa sättet att uttrycka en algoritm eftersom den kan förstås av även en lekman med viss kunskap på skolnivå.