Definiția algoritmului
Cuvantul Algoritm mijloace Un set de reguli sau instrucțiuni finite care trebuie urmate în calcule sau alte operații de rezolvare a problemelor
Sau
O procedură pentru rezolvarea unei probleme matematice într-un număr finit de pași care implică frecvent operații recursive .
Prin urmare, algoritmul se referă la o secvență de pași finiți pentru a rezolva o anumită problemă.
Utilizarea algoritmilor:
Algoritmii joacă un rol crucial în diverse domenii și au multe aplicații. Unele dintre domeniile cheie în care sunt utilizați algoritmii includ:
- Informatică: Algoritmii formează baza programării computerelor și sunt utilizați pentru a rezolva probleme, de la simpla sortare și căutare la sarcini complexe, cum ar fi inteligența artificială și învățarea automată.
- Matematică: Algoritmii sunt utilizați pentru a rezolva probleme matematice, cum ar fi găsirea soluției optime pentru un sistem de ecuații liniare sau găsirea celei mai scurte căi într-un grafic.
- Cercetare operațională : Algoritmii sunt utilizați pentru a optimiza și a lua decizii în domenii precum transportul, logistica și alocarea resurselor.
- Inteligenţă artificială: Algoritmii sunt baza inteligenței artificiale și a învățării automate și sunt utilizați pentru a dezvolta sisteme inteligente care pot îndeplini sarcini precum recunoașterea imaginilor, procesarea limbajului natural și luarea deciziilor.
- Știința datelor: Algoritmii sunt utilizați pentru a analiza, procesa și extrage informații din cantități mari de date în domenii precum marketing, finanțe și asistență medicală.
Acestea sunt doar câteva exemple din numeroasele aplicații ale algoritmilor. Utilizarea algoritmilor este în continuă expansiune pe măsură ce apar noi tehnologii și domenii, făcându-l o componentă vitală a societății moderne.
Algoritmii pot fi simpli și complexi în funcție de ceea ce doriți să obțineți.
Poate fi înțeles luând exemplul gătirii unei rețete noi. Pentru a găti o nouă rețetă, citiți instrucțiunile și pașii și le executați unul câte unul, în ordinea dată. Rezultatul astfel obținut este că noul fel de mâncare este gătit perfect. De fiecare dată când folosiți telefonul, computerul, laptopul sau calculatorul, utilizați algoritmi. În mod similar, algoritmii ajută la realizarea unei sarcini în programare pentru a obține rezultatul așteptat.
Algoritmul conceput este independent de limbă, adică sunt doar instrucțiuni simple care pot fi implementate în orice limbă și totuși rezultatul va fi același, așa cum era de așteptat.
Care este nevoie de algoritmi?
- Algoritmii sunt necesari pentru rezolvarea eficienta si eficienta a problemelor complexe.
- Acestea ajută la automatizarea proceselor și le fac mai fiabile, mai rapide și mai ușor de realizat.
- Algoritmii permit, de asemenea, computerelor să efectueze sarcini care ar fi dificil sau imposibil de realizat pentru oameni manual.
- Ele sunt utilizate în diverse domenii, cum ar fi matematica, informatica, inginerie, finanțe și multe altele pentru a optimiza procesele, analiza date, face predicții și oferi soluții la probleme.
Care sunt caracteristicile unui algoritm?
Pentru că nu ar urma nicio instrucțiune scrisă pentru a găti rețeta, ci doar cea standard. În mod similar, nu toate instrucțiunile scrise pentru programare sunt un algoritm. Pentru ca unele instrucțiuni să fie un algoritm, acesta trebuie să aibă următoarele caracteristici:
- Clar și fără ambiguitate : Algoritmul ar trebui să fie clar. Fiecare dintre pașii săi ar trebui să fie clar în toate aspectele și trebuie să conducă la un singur sens.
- Intrări bine definite : Dacă un algoritm spune să se ia intrări, ar trebui să fie intrări bine definite. Poate sau nu să preia intrare.
- Ieșiri bine definite: Algoritmul trebuie să definească clar ce ieșire va fi obținută și ar trebui să fie și bine definită. Ar trebui să producă cel puțin o ieșire.
- Finalitate: Algoritmul trebuie să fie finit, adică ar trebui să se termine după un timp finit.
- Fezabil: Algoritmul trebuie să fie simplu, generic și practic, astfel încât să poată fi executat cu resursele disponibile. Nu trebuie să conțină vreo tehnologie viitoare sau ceva.
- Independent de limbă: Algoritmul proiectat trebuie să fie independent de limbă, adică trebuie să fie doar instrucțiuni simple care pot fi implementate în orice limbă și totuși rezultatul va fi același, așa cum era de așteptat.
- Intrare : Un algoritm are zero sau mai multe intrări. Fiecare care conține un operator fundamental trebuie să accepte zero sau mai multe intrări.
- Ieșire : Un algoritm produce cel puțin o ieșire. Fiecare instrucțiune care conține un operator fundamental trebuie să accepte zero sau mai multe intrări.
- Certitudine: Toate instrucțiunile dintr-un algoritm trebuie să fie clare, precise și ușor de interpretat. Prin referire la oricare dintre instrucțiunile dintr-un algoritm se poate înțelege clar ce trebuie făcut. Fiecare operator fundamental în instruire trebuie definit fără nicio ambiguitate.
- Finitudine: Un algoritm trebuie să se termine după un număr finit de pași în toate cazurile de testare. Fiecare instrucțiune care conține un operator fundamental trebuie să fie terminată într-un interval de timp finit. Buclele infinite sau funcțiile recursive fără condiții de bază nu posedă caracter de finit.
- Eficacitate: Un algoritm trebuie dezvoltat folosind operații foarte simple, simple și fezabile, astfel încât să se poată urmări folosind doar hârtie și creion.
Proprietățile algoritmului:
- Ar trebui să se încheie după un timp finit.
- Ar trebui să producă cel puțin o ieșire.
- Ar trebui să ia zero sau mai multe intrări.
- Ar trebui să fie determinist înseamnă să ofere aceeași ieșire pentru același caz de intrare.
- Fiecare pas din algoritm trebuie să fie eficient, adică fiecare pas ar trebui să lucreze.
Tipuri de algoritmi:
Există mai multe tipuri de algoritmi disponibili. Unii algoritmi importanți sunt:
1. Algoritmul de forță brută :
Este cea mai simplă abordare a unei probleme. Un algoritm de forță brută este prima abordare care vine în găsirea când vedem o problemă.
matrice în metodele java
2. Algoritm recursiv :
Un algoritm recursiv se bazează pe recursiunea . În acest caz, o problemă este împărțită în mai multe subpărți și numită aceeași funcție din nou și din nou.
3. Algoritmul de backtracking :
Algoritmul de backtracking construiește soluția căutând printre toate soluțiile posibile. Folosind acest algoritm, continuăm să construim soluția urmând criterii. Ori de câte ori o soluție eșuează, ne întoarcem la punctul de eșec, construim pe următoarea soluție și continuăm acest proces până când găsim soluția sau toate soluțiile posibile sunt îngrijite.
4. Algoritm de căutare :
Algoritmii de căutare sunt cei care sunt utilizați pentru căutarea elementelor sau a grupurilor de elemente dintr-o anumită structură de date. Ele pot fi de diferite tipuri în funcție de abordarea lor sau de structura de date în care ar trebui să se găsească elementul.
5. Algoritm de sortare :
Sortarea înseamnă aranjarea unui grup de date într-o manieră specială, în funcție de cerință. Algoritmii care ajută la îndeplinirea acestei funcții se numesc algoritmi de sortare. În general, algoritmii de sortare sunt utilizați pentru a sorta grupuri de date într-o manieră crescătoare sau descrescătoare.
6. Algoritmul de hashing :
Algoritmii de hashing funcționează similar cu algoritmul de căutare. Dar ele conțin un index cu un ID de cheie. În hashing, o cheie este atribuită unor date specifice.
7. Algoritmul Divide and Conquer :
Acest algoritm descompune o problemă în sub-probleme, rezolvă o singură sub-problemă și îmbină soluțiile pentru a obține soluția finală. Acesta constă din următorii trei pași:
- Divide
- Rezolva
- Combina
8. Algoritmul lacom :
În acest tip de algoritm, soluția este construită parte cu parte. Soluția pentru piesa următoare este construită pe baza beneficiului imediat al piesei următoare. Singura soluție care oferă cele mai multe beneficii va fi aleasă ca soluție pentru următoarea parte.
9. Algoritm de programare dinamică :
Acest algoritm folosește conceptul de utilizare a soluției deja găsite pentru a evita calculul repetitiv al aceleiași părți a problemei. Împarte problema în subprobleme mai mici care se suprapun și le rezolvă.
10. Algoritm randomizat :
În algoritmul randomizat, folosim un număr aleator, astfel încât acesta oferă beneficii imediate. Numărul aleatoriu ajută la stabilirea rezultatului așteptat.
Pentru a afla mai multe despre tipurile de algoritmi, consultați articolul despre Tipuri de algoritmi .
Avantajele algoritmilor:
- Este ușor de înțeles.
- Un algoritm este o reprezentare în etape a unei soluții la o problemă dată.
- Într-un algoritm, problema este împărțită în bucăți sau pași mai mici, prin urmare, este mai ușor pentru programator să o transforme într-un program real.
Dezavantajele algoritmilor:
- Scrierea unui algoritm durează mult timp, așa că necesită mult timp.
- Înțelegerea logicii complexe prin algoritmi poate fi foarte dificilă.
- Declarațiile de ramificare și buclă sunt greu de afișat în algoritmi (imp) .
Cum se proiectează un algoritm?
Pentru a scrie un algoritm, sunt necesare următoarele lucruri ca o condiție prealabilă:
- The problemă care trebuie rezolvat prin acest algoritm, adică definirea clară a problemei.
- The constrângeri problema trebuie luată în considerare în timpul rezolvării problemei.
- The intrare de luat pentru a rezolva problema.
- The ieșire este de așteptat când problema va fi rezolvată.
- The soluţie la această problemă se încadrează în constrângerile date.
Apoi algoritmul este scris cu ajutorul parametrilor de mai sus astfel încât să rezolve problema.
Exemplu: Luați în considerare exemplul de a adăuga trei numere și de a tipări suma.
Pasul 1: Îndeplinirea cerințelor prealabile
După cum sa discutat mai sus, pentru a scrie un algoritm, trebuie îndeplinite condițiile prealabile ale acestuia.
- Problema care urmează să fie rezolvată de acest algoritm : Adăugați 3 numere și imprimați suma lor.
- Constrângerile problemei care trebuie luate în considerare la rezolvarea problemei : Numerele trebuie să conțină numai cifre și nici un alt caracter.
- Intrarea care trebuie luată pentru a rezolva problema: Cele trei numere de adăugat.
- Rezultatul de așteptat când problema este rezolvată: Suma celor trei numere luate ca intrare, adică o singură valoare întreagă.
- Soluția acestei probleme, în constrângerile date: Soluția constă în adunarea celor 3 numere. Se poate face cu ajutorul operatorului „+”, sau pe biți sau orice altă metodă.
Pasul 2: Proiectarea algoritmului
Acum să proiectăm algoritmul cu ajutorul cerințelor prealabile de mai sus:
Algoritm pentru a adăuga 3 numere și a imprima suma lor:
- START
- Declarați 3 variabile întregi num1, num2 și num3.
- Luați cele trei numere, care urmează să fie adăugate, ca intrări în variabilele num1, num2 și, respectiv, num3.
- Declarați o sumă variabilă întreagă pentru a stoca suma rezultată a celor 3 numere.
- Adăugați cele 3 numere și stocați rezultatul în suma variabilă.
- Tipăriți valoarea sumei variabilei
- Sfârşit
Pasul 3: Testarea algoritmului prin implementarea acestuia.
Pentru a testa algoritmul, să-l implementăm în limbajul C.
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*/>Piton # 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> Ieșire
Introduceți primul număr: 0 Introduceți al 2-lea număr: 0 Introduceți al treilea număr: -1577141152 Suma celor 3 numere este: -1577141152
Iată algoritmul pas cu pas al codului:
- Declarați trei variabile num1, num2 și num3 pentru a stoca cele trei numere de adăugat.
- Declarați o sumă variabilă pentru a stoca suma celor trei numere.
- Utilizați declarația cout pentru a solicita utilizatorului să introducă primul număr.
- Utilizați instrucțiunea cin pentru a citi primul număr și stocați-l în num1.
- Utilizați declarația cout pentru a solicita utilizatorului să introducă al doilea număr.
- Utilizați instrucțiunea cin pentru a citi al doilea număr și stocați-l în num2.
- Utilizați declarația cout pentru a solicita utilizatorului să introducă al treilea număr.
- Utilizați instrucțiunea cin pentru a citi și stoca al treilea număr în num3.
- Calculați suma celor trei numere folosind operatorul + și stocați-o în variabila sumă.
- Utilizați declarația cout pentru a imprima suma celor trei numere.
- Funcția principală returnează 0, ceea ce indică execuția cu succes a programului.
Complexitatea timpului: O(1)
Spațiu auxiliar: O(1)
O problemă, multe soluții: Soluția unui algoritm poate fi sau nu poate fi mai mult de una. Înseamnă că în timpul implementării algoritmului, pot exista mai multe metode de implementare. De exemplu, în problema de mai sus a adunării a 3 numere, suma poate fi calculată în mai multe moduri:
- + operator
- Operatori pe biți
- . . etc
Cum se analizează un algoritm?
Pentru ca un algoritm standard să fie bun, trebuie să fie eficient. Prin urmare, eficiența unui algoritm trebuie verificată și menținută. Poate fi în două etape:
1. Analiza Priori:
Priori înseamnă înainte. Prin urmare, analiza Priori înseamnă verificarea algoritmului înainte de implementarea lui. În aceasta, algoritmul este verificat atunci când este scris sub formă de pași teoretici. Această eficiență a unui algoritm este măsurată presupunând că toți ceilalți factori, de exemplu, viteza procesorului, sunt constante și nu au niciun efect asupra implementării. Acest lucru este realizat de obicei de designerul algoritmului. Această analiză este independentă de tipul de hardware și limbajul compilatorului. Oferă răspunsurile aproximative pentru complexitatea programului.
2. Analiza posterioară:
Posterior înseamnă după. Prin urmare, analiza posterioară înseamnă verificarea algoritmului după implementarea acestuia. În aceasta, algoritmul este verificat prin implementarea lui în orice limbaj de programare și executarea lui. Această analiză ajută la obținerea raportului de analiză real și real despre corectitudine (pentru fiecare intrare/e posibile dacă arată/returnează o ieșire corectă sau nu), spațiul necesar, timpul consumat etc. Adică, depinde de limbajul compilator și tipul de hardware utilizat.
Ce este complexitatea algoritmului și cum să o găsiți?
Un algoritm este definit ca fiind complex pe baza cantității de spațiu și timp pe care îl consumă. Prin urmare, Complexitatea unui algoritm se referă la măsurarea timpului de care va avea nevoie pentru a executa și a obține rezultatul așteptat și la spațiul de care va avea nevoie pentru a stoca toate datele (intrare, date temporare și ieșire). Prin urmare, acești doi factori definesc eficiența unui algoritm.
Cei doi factori ai complexității algoritmului sunt:
- Factorul timp : Timpul este măsurat prin numărarea numărului de operații cheie, cum ar fi comparații în algoritmul de sortare.
- Factorul spațial : Spațiul este măsurat prin numărarea spațiului maxim de memorie necesar algoritmului pentru a rula/executa.
De aceea complexitatea unui algoritm poate fi împărțită în două tipuri :
1. Complexitatea spațială : Complexitatea spațială a unui algoritm se referă la cantitatea de memorie necesară algoritmului pentru a stoca variabilele și a obține rezultatul. Aceasta poate fi pentru intrări, operațiuni temporare sau ieșiri.
Cum se calculează complexitatea spațiului?
Complexitatea spațială a unui algoritm este calculată prin determinarea următoarelor 2 componente:
- Parte fixă: Aceasta se referă la spațiul cerut de algoritm. De exemplu, variabile de intrare, variabile de ieșire, dimensiunea programului etc.
- Parte variabilă: Aceasta se referă la spațiul care poate fi diferit în funcție de implementarea algoritmului. De exemplu, variabile temporare, alocarea dinamică a memoriei, spațiul stivei recursive etc.
Prin urmare, complexitatea spațială S(P) al oricărui algoritm P este S(P) = C + SP(I) , unde C este partea fixă și S(I) este partea variabilă a algoritmului, care depinde de caracteristica I.
Exemplu: Luați în considerare algoritmul de mai jos pentru căutarea liniară
Pasul 1: START
Pasul 2: Obțineți n elemente ale matricei în arr și numărul de căutat în x
Pasul 3: Începeți de la elementul din stânga al lui arr[] și comparați unul câte unul x cu fiecare element al lui arr[]
Pasul 4: Dacă x se potrivește cu un element, imprimați True.
Pasul 5: Dacă x nu se potrivește cu niciunul dintre elemente, imprimați False.
Pasul 6: sfârșit
Aici, există 2 variabile arr[] și x, unde arr[] este partea variabilă a n elemente și x este partea fixă. Prin urmare S(P) = 1+n. Deci, complexitatea spațiului depinde de n(numărul de elemente). Acum, spațiul depinde de tipurile de date ale variabilelor date și de tipurile constante și va fi înmulțit în consecință.
2. Complexitatea timpului : Complexitatea în timp a unui algoritm se referă la timpul necesar algoritmului pentru a executa și obține rezultatul. Aceasta poate fi pentru operațiuni normale, instrucțiuni condiționale if-else, instrucțiuni bucle etc.
Cum se calculează , Complexitatea timpului?
Complexitatea temporală a unui algoritm se calculează și prin determinarea următoarelor 2 componente:
- Parte de timp constant: Orice instrucțiune care este executată o singură dată vine în această parte. De exemplu, intrare, ieșire, if-else, comutare, operații aritmetice etc.
- Parte de timp variabilă: Orice instrucțiune care este executată de mai multe ori, să zicem de n ori, vine în această parte. De exemplu, bucle, recursivitate etc.
Prin urmare, complexitatea timpuluiT(P) al oricărui algoritm P este T(P) = C + TP(I) , unde C este partea constantă a timpului și TP(I) este partea variabilă a algoritmului, care depinde de caracteristica instanței I.
Exemplu: În algoritmul de căutare liniară de mai sus, complexitatea timpului este calculată după cum urmează:
concatenare de șiruri
Pasul 1: -Timp constant
Pasul 2: — Timp variabil (luând n intrări)
Pasul 3: -Timp variabil (Până la lungimea matricei (n) sau indexul elementului găsit)
Pasul 4: -Timp constant
Pasul 5: -Timp constant
Pasul 6: -Timp constant
Prin urmare, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, care poate fi spus ca T(n).
Cum se exprimă un algoritm?
- Limbajul natural: - Aici exprimăm algoritmul în limba engleză naturală. Este prea greu de înțeles algoritmul din el.
- Diagramă :- Aici exprimăm algoritmul făcând a reprezentarea grafică/picturală a acesteia. Este mai ușor de înțeles decât limbajul natural.
- Pseudo cod :- Aici exprimăm algoritmul sub formă de adnotări și text informativ scris în limba engleză simplă, care este foarte asemănător cu codul real, dar deoarece nu are sintaxă ca oricare dintre limbajele de programare, nu poate fi compilat sau interpretat de computer. . Este cel mai bun mod de a exprima un algoritm, deoarece poate fi înțeles chiar și de un neprofesionist cu anumite cunoștințe la nivel de școală.