Structuri de Date – Algoritmi de Bază

Algoritm este un pas-cu-pas procedura, care definește un set de instrucțiuni pentru a fi executate într-o anumită ordine pentru a obține rezultatul dorit. Algoritmii sunt în general creați independent de limbajele de bază, adică un algoritm poate fi implementat în mai multe limbaje de programare.,din punct de vedere al structurii de date, următoarele sunt câteva categorii importante de algoritmi −

• Search − algoritm pentru a căuta un element într-o structură de date.Sort-algoritm pentru a sorta elementele într-o anumită ordine.

• Insert − algoritm pentru a insera element într-o structură de date.

• Update-algoritm pentru a actualiza un element existent într-o structură de date.

• Delete-algoritm pentru a șterge un element existent dintr-o structură de date.

caracteristicile unui algoritm

nu toate procedurile pot fi numite algoritm., Un algoritm ar trebui să aibă următoarele caracteristici −

• neechivoc − algoritmul ar trebui să fie clar și neechivoc. Fiecare dintre etapele sale (sau faze) și intrările/ieșirile lor trebuie să fie clare și trebuie să conducă la un singur sens.

• Input-un algoritm ar trebui să aibă 0 sau mai multe intrări bine definite.ieșire-un algoritm ar trebui să aibă 1 sau mai multe ieșiri bine definite și ar trebui să se potrivească cu ieșirea dorită.Finiteness-algoritmii trebuie să se termine după un număr finit de pași.,

• fezabilitate-ar trebui să fie fezabilă cu resursele disponibile.Independent-un algoritm ar trebui să aibă direcții pas cu pas, care ar trebui să fie independente de orice cod de programare.

cum se scrie un algoritm?

nu există standarde bine definite pentru scrierea algoritmilor. Mai degrabă, este dependentă de probleme și resurse. Algoritmii nu sunt niciodată scrise pentru a sprijini un anumit cod de programare.

după cum știm că toate limbajele de programare împărtășesc construcții de cod de bază precum bucle (do, for, while), control al fluxului (if-else) etc., Aceste construcții comune pot fi folosite pentru a scrie un algoritm.

scriem algoritmi într-o manieră pas cu pas, dar nu este întotdeauna cazul. Scrierea algoritmului este un proces și este executat după ce domeniul problemei este bine definit. Adică ar trebui să cunoaștem domeniul problemei, pentru care proiectăm o soluție.

exemplu

Să încercăm să învățăm scrierea algoritmului folosind un exemplu.

problemă-proiectați un algoritm pentru a adăuga două numere și a afișa rezultatul.

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

algoritmii spun programatorilor cum să codifice programul., Alternativ, algoritmul poate fi scris ca –

Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP

în proiectarea și analiza algoritmilor, de obicei a doua metodă este utilizată pentru a descrie un algoritm. Este ușor pentru analist să analizeze algoritmul ignorând toate definițiile nedorite. El poate observa ce operațiuni sunt folosite și cum curge procesul.

scrierea numerelor pas, este opțională.proiectăm un algoritm pentru a obține o soluție a unei probleme date. O problemă poate fi rezolvată în mai multe moduri.,

prin urmare, mulți algoritmi de soluție pot fi derivați pentru o anumită problemă. Următorul pas este analiza algoritmilor de soluții propuși și implementarea celei mai potrivite soluții.

analiza algoritmului

eficiența unui algoritm poate fi analizată în două etape diferite, înainte de implementare și după implementare. Acestea sunt următoarele −

• analiza A Priori-aceasta este o analiză teoretică a unui algoritm., Eficiența unui algoritm este măsurată presupunând că toți ceilalți factori, de exemplu, viteza procesorului, sunt constanți și nu au niciun efect asupra implementării.o analiză posterioară – aceasta este o analiză empirică a unui algoritm. Algoritmul selectat este implementat folosind limbajul de programare. Acest lucru este apoi executat pe masina de calculator țintă. În această analiză, sunt colectate statistici reale, cum ar fi timpul de funcționare și spațiul necesar.

vom învăța despre analiza algoritmului a priori., Analiza algoritmului se ocupă cu timpul de execuție sau de funcționare a diferitelor operațiuni implicate. Timpul de funcționare al unei operații poate fi definit ca numărul de instrucțiuni de calculator executate pe operație.

Algoritm de Complexitate

să Presupunem că X este un algoritm și n este dimensiunea datelor de intrare, timpul și spațiul folosit de algoritmul X sunt cei doi factori principali, care decide eficiența X.

• Factorul Timp − Timpul este măsurat prin numărarea numărului de operațiuni cheie, cum ar fi comparațiile în algoritmul de sortare.,factorul spațial – spațiul este măsurat prin numărarea spațiului maxim de memorie cerut de algoritm.complexitatea unui algoritm f (n) oferă timpul de funcționare și/sau spațiul de stocare necesar algoritmului în termeni de n ca dimensiunea datelor de intrare.

  complexitatea spațiului

  complexitatea spațiului unui algoritm reprezintă cantitatea de spațiu de memorie necesară algoritmului în ciclul său de viață., Spațiul cerut de un algoritm este egal cu suma următoarelor două componente −

  • o parte fixă care este un spațiu necesar pentru a stoca anumite date și variabile, care sunt independente de dimensiunea problemei. De exemplu, variabile și constante simple utilizate, dimensiunea programului etc.

  • o parte variabilă este un spațiu cerut de variabile, a căror dimensiune depinde de dimensiunea problemei. De exemplu, alocarea dinamică a memoriei, spațiul stivei de recursivitate etc.,

  Spațiu de complexitate S(P) de orice algoritm P este S(P) = C + SP(I), unde C este partea fixă și S(I) este partea variabilă a algoritmului, care depinde exemplu caracteristic I. Următoarele este un exemplu simplu care încearcă să explice conceptul −

  Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop

  Aici avem trei variabile a, B, și C și o constantă. Prin urmare, S(P) = 1 + 3. Acum, spațiul depinde de tipurile de date ale variabilelor date și de tipurile constante și va fi înmulțit în consecință.,

  complexitatea timpului

  complexitatea timpului unui algoritm reprezintă timpul necesar algoritmului pentru a rula până la finalizare. Cerințele de timp pot fi definite ca o funcție numerică T (n), unde T(n) poate fi măsurată ca număr de pași, cu condiția ca fiecare pas să consume timp constant.

  de exemplu, adăugarea a două numere întregi n-bit ia n pași. În consecință, timpul total de calcul este T (n) = C ∗ n, unde c este timpul necesar pentru adăugarea a doi biți. Aici, observăm că T (n) crește liniar pe măsură ce dimensiunea de intrare crește.,

  anunțuri