logo

TechCodeview

Kaj je algoritem | Uvod v algoritme

Opredelitev algoritma

Beseda Algoritem pomeni Niz končnih pravil ali navodil, ki jih je treba upoštevati pri izračunih ali drugih operacijah reševanja problemov
oz
Postopek za reševanje matematičnega problema v končnem številu korakov, ki pogosto vključuje rekurzivne operacije .

Zato se algoritem nanaša na zaporedje končnih korakov za rešitev določenega problema.

Kaj je algoritem

Uporaba algoritmov:

Algoritmi igrajo ključno vlogo na različnih področjih in imajo veliko aplikacij. Nekatera ključna področja, kjer se uporabljajo algoritmi, vključujejo:



  1. Računalništvo: Algoritmi so osnova računalniškega programiranja in se uporabljajo za reševanje problemov, ki segajo od preprostega razvrščanja in iskanja do kompleksnih nalog, kot sta umetna inteligenca in strojno učenje.
  2. matematika: Algoritmi se uporabljajo za reševanje matematičnih problemov, kot je iskanje optimalne rešitve sistema linearnih enačb ali iskanje najkrajše poti v grafu.
  3. Operacijske raziskave : Algoritmi se uporabljajo za optimizacijo in sprejemanje odločitev na področjih, kot so transport, logistika in dodeljevanje virov.
  4. Umetna inteligenca: Algoritmi so temelj umetne inteligence in strojnega učenja ter se uporabljajo za razvoj inteligentnih sistemov, ki lahko izvajajo naloge, kot so prepoznavanje slik, obdelava naravnega jezika in sprejemanje odločitev.
  5. Podatkovna znanost: Algoritmi se uporabljajo za analizo, obdelavo in pridobivanje vpogledov iz velikih količin podatkov na področjih, kot so trženje, finance in zdravstvo.

To je le nekaj primerov številnih aplikacij algoritmov. Uporaba algoritmov se nenehno širi, ko se pojavljajo nove tehnologije in področja, zaradi česar je pomembna sestavina sodobne družbe.

Algoritmi so lahko preprosti in zapleteni, odvisno od tega, kaj želite doseči.

To je mogoče razumeti, če vzamemo primer kuhanja po novem receptu. Za kuhanje po novem receptu preberete navodila in korake ter jih izvedete enega za drugim v danem zaporedju. Tako dobljen rezultat je, da je nova jed odlično pečena. Vsakič, ko uporabljate telefon, računalnik, prenosni računalnik ali kalkulator, uporabljate algoritme. Podobno algoritmi pomagajo opraviti nalogo v programiranju, da dobimo pričakovan rezultat.

umetna inteligenca in inteligentni agenti

Zasnovani algoritem je neodvisen od jezika, kar pomeni, da so preprosta navodila, ki jih je mogoče implementirati v katerem koli jeziku, vendar bo rezultat enak, kot je bilo pričakovano.

Kakšna je potreba po algoritmih?

  1. Algoritmi so potrebni za učinkovito in uspešno reševanje kompleksnih problemov.
  2. Pomagajo avtomatizirati procese in jih naredijo bolj zanesljive, hitrejše in enostavnejše za izvedbo.
  3. Algoritmi računalnikom omogočajo tudi izvajanje nalog, ki bi jih ljudje težko ali nemogoče opravili ročno.
  4. Uporabljajo se na različnih področjih, kot so matematika, računalništvo, inženiring, finance in mnoga druga, za optimizacijo procesov, analizo podatkov, napovedovanje in zagotavljanje rešitev za težave.

Kakšne so značilnosti algoritma?

Značilnosti algoritma

Ker ne bi sledili nobenim pisnim navodilom za kuhanje po receptu, ampak samo standardnemu. Podobno niso vsa pisna navodila za programiranje algoritem. Da so nekatera navodila algoritem, morajo imeti naslednje značilnosti:

  • Jasno in nedvoumno : Algoritem naj bo nedvoumen. Vsak njen korak naj bo jasen v vseh pogledih in vodi do enega samega pomena.
  • Dobro definirani vnosi : Če algoritem zahteva sprejemanje vhodnih podatkov, morajo biti to dobro definirani vhodni podatki. Lahko sprejme vnos ali pa ne.
  • Dobro definirani rezultati: Algoritem mora jasno definirati, kakšen rezultat bo prinesel, in mora biti tudi dobro definiran. Ustvariti mora vsaj 1 rezultat.
  • Končnost: Algoritem mora biti končen, to pomeni, da se mora končati po končnem času.
  • Izvedljivo: Algoritem mora biti preprost, splošen in praktičen, tako da ga je mogoče izvesti z razpoložljivimi viri. Ne sme vsebovati neke tehnologije prihodnosti ali česar koli.
  • Neodvisno od jezika: Oblikovani algoritem mora biti neodvisen od jezika, to pomeni, da morajo biti samo preprosta navodila, ki jih je mogoče implementirati v katerem koli jeziku, vendar bo rezultat enak, kot je bilo pričakovano.
  • Vnos : Algoritem ima nič ali več vnosov. Vsak, ki vsebuje temeljni operator, mora sprejeti nič ali več vnosov.
  • Izhod : algoritem proizvede vsaj en rezultat. Vsako navodilo, ki vsebuje temeljni operator, mora sprejeti nič ali več vnosov.
  • Določnost: Vsa navodila v algoritmu morajo biti nedvoumna, natančna in enostavna za interpretacijo. S sklicevanjem na katero koli navodilo v algoritmu lahko jasno razumemo, kaj je treba narediti. Vsak temeljni operater v navodilih mora biti opredeljen brez kakršnih koli dvoumnosti.
  • Končnost: Algoritem se mora končati po končnem številu korakov v vseh testnih primerih. Vsako navodilo, ki vsebuje temeljni operator, je treba zaključiti v končnem času. Neskončne zanke ali rekurzivne funkcije brez osnovnih pogojev nimajo končnosti.
  • Učinkovitost: Algoritem je treba razviti z uporabo zelo osnovnih, preprostih in izvedljivih operacij, tako da ga lahko izsledimo samo s papirjem in svinčnikom.

Lastnosti algoritma:

  • Po končnem času se mora končati.
  • Ustvariti mora vsaj en rezultat.
  • Zahtevati mora nič ali več vnosa.
  • Moral bi biti determinističen, kar pomeni, da daje enak izhod za isti vhodni primer.
  • Vsak korak v algoritmu mora biti učinkovit, tj. vsak korak mora opraviti nekaj dela.

Vrste algoritmov:

Na voljo je več vrst algoritmov. Nekateri pomembni algoritmi so:

1. Algoritem surove sile :

To je najenostavnejši pristop k problemu. Algoritem surove sile je prvi pristop k iskanju, ko opazimo težavo.

2. Rekurzivni algoritem :

Rekurzivni algoritem temelji na rekurzija . V tem primeru se problem razdeli na več poddelov in vedno znova kliče isto funkcijo.

3. Algoritem za povratno sledenje :

Algoritem povratnega sledenja gradi rešitev z iskanjem med vsemi možnimi rešitvami. Z uporabo tega algoritma še naprej gradimo rešitev po kriterijih. Kadar koli rešitev ne uspe, sledimo nazaj do točke napake, gradimo na naslednji rešitvi in ​​nadaljujemo s tem postopkom, dokler ne najdemo rešitve ali dokler ne preučimo vseh možnih rešitev.

4. Algoritem iskanja :

Iskalni algoritmi so tisti, ki se uporabljajo za iskanje elementov ali skupin elementov iz določene podatkovne strukture. Lahko so različnih vrst glede na njihov pristop ali podatkovno strukturo, v kateri naj bi bil element najden.

5. Algoritem za razvrščanje :

Razvrščanje je urejanje skupine podatkov na določen način glede na zahtevo. Algoritmi, ki pomagajo pri izvajanju te funkcije, se imenujejo algoritmi za razvrščanje. Na splošno se algoritmi za razvrščanje uporabljajo za razvrščanje skupin podatkov v naraščajočem ali padajočem načinu.

6. Algoritem zgoščevanja :

Algoritmi zgoščevanja delujejo podobno kot iskalni algoritem. Vsebujejo pa indeks z ID-jem ključa. Pri zgoščevanju je določenim podatkom dodeljen ključ.

7. Algoritem deli in vladaj :

Ta algoritem razdeli problem na podprobleme, reši en sam podproblem in združi rešitve, da dobi končno rešitev. Sestavljen je iz naslednjih treh korakov:

  • Razdeli
  • Rešiti
  • Združite

8. Pohlepni algoritem :

Pri tej vrsti algoritma se rešitev gradi del za delom. Rešitev za naslednji del je zgrajena na podlagi takojšnje koristi naslednjega dela. Ena rešitev, ki prinaša največ koristi, bo izbrana kot rešitev za naslednji del.

9. Algoritem dinamičnega programiranja :

Ta algoritem uporablja koncept uporabe že najdene rešitve, da se izogne ​​ponavljajočemu se izračunu istega dela problema. Problem razdeli na manjše prekrivajoče se podprobleme in jih reši.

10. Naključni algoritem :

V randomiziranem algoritmu uporabljamo naključno število, tako da daje takojšnjo korist. Naključno število pomaga pri odločanju o pričakovanem rezultatu.

Če želite izvedeti več o vrstah algoritmov, glejte članek o Vrste algoritmov .

Prednosti algoritmov:

  • To je enostavno razumeti.
  • Algoritem je postopna predstavitev rešitve danega problema.
  • V algoritmu je problem razdeljen na manjše dele ali korake, zato ga programer lažje pretvori v dejanski program.

Slabosti algoritmov:

  • Pisanje algoritma traja dolgo, zato je zamudno.
  • Razumevanje kompleksne logike prek algoritmov je lahko zelo težko.
  • Stavke razvejanja in zanke je težko prikazati v algoritmih (vrag) .

Kako oblikovati algoritem?

Za pisanje algoritma so kot predpogoj potrebni naslednji elementi:

  1. The problem ki naj bi ga rešil ta algoritem, tj. jasna definicija problema.
  2. The omejitve problema je treba upoštevati pri reševanju problema.
  3. The vnos sprejeti za rešitev problema.
  4. The izhod je pričakovati, ko bo problem rešen.
  5. The rešitev tega problema znotraj danih omejitev.

Nato se algoritem s pomočjo zgornjih parametrov zapiše tako, da reši problem.

primer: Razmislite o primeru seštevanja treh števil in izpisa vsote.

1. korak: izpolnjevanje predpogojev

Kot je razloženo zgoraj, morajo biti za pisanje algoritma izpolnjeni njegovi predpogoji.

  1. Problem, ki naj bi ga rešil ta algoritem : Seštej 3 števila in izpiši njihovo vsoto.
  2. Omejitve problema, ki jih je treba upoštevati pri reševanju problema : Številke morajo vsebovati samo števke in nobenih drugih znakov.
  3. Vnos, ki ga je treba uporabiti za rešitev težave: Tri številke, ki jih je treba dodati.
  4. Rezultat, ki se pričakuje, ko je težava rešena: Vsota treh števil, vzetih kot vhod, tj. ena cela vrednost.
  5. Rešitev tega problema v danih omejitvah: Rešitev je sestavljena iz seštevanja treh števil. To je mogoče storiti s pomočjo operatorja '+', bitno ali na katero koli drugo metodo.


2. korak: Oblikovanje algoritma

Zdaj pa oblikujmo algoritem s pomočjo zgornjih predpogojev:

Algoritem za seštevanje 3 števil in izpis njihove vsote:

  1. START
  2. Deklarirajte 3 cele spremenljivke num1, num2 in num3.
  3. Vzemite tri števila, ki jih želite sešteti, kot vnose v spremenljivkah num1, num2 in num3.
  4. Deklarirajte celoštevilsko spremenljivko sum, da shranite rezultanto vsote treh števil.
  5. Seštejte 3 števila in rezultat shranite v spremenljivko vsota.
  6. Izpiši vrednost spremenljivke vsota
  7. KONEC


3. korak: Testiranje algoritma z njegovo implementacijo.

Da preizkusimo algoritem, ga implementirajmo v jezik 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>> št1; cout<< ' ' << num1 << endl; cout << 'Enter the 2nd number: '; cin>> št.2; cout<< ' ' << num2 << endl; cout << 'Enter the 3rd number: '; cin>> št.3; 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>
Izhod

Vnesite 1. številko: 0 Vnesite 2. številko: 0 Vnesite 3. številko: -1577141152 Vsota 3 številk je: -1577141152

Tukaj je algoritem kode po korakih:

  1. Navedite tri spremenljivke num1, num2 in num3, da shranite tri števila, ki jih želite dodati.
  2. Za shranjevanje vsote treh števil deklarirajte spremenljivko sum.
  3. Uporabite stavek cout, da uporabnika pozovete k vnosu prve številke.
  4. Uporabite stavek cin, da preberete prvo številko in jo shranite v num1.
  5. Uporabite stavek cout, da uporabnika pozovete k vnosu druge številke.
  6. Uporabite stavek cin, da preberete drugo številko in jo shranite v num2.
  7. Uporabite stavek cout, da uporabnika pozovete k vnosu tretje številke.
  8. Uporabite stavek cin za branje in shranjevanje tretje številke v num3.
  9. Z operatorjem + izračunajte vsoto treh števil in jo shranite v spremenljivko vsota.
  10. Uporabite stavek cout, da natisnete vsoto treh števil.
  11. Glavna funkcija vrne 0, kar pomeni uspešno izvedbo programa.

Časovna zahtevnost: O(1)
Pomožni prostor: O(1)

En problem, veliko rešitev: Rešitev algoritma je lahko ali ne more biti več kot ena. To pomeni, da med implementacijo algoritma obstaja več kot ena metoda za njegovo implementacijo. Na primer, pri zgornjem problemu seštevanja 3 števil je vsoto mogoče izračunati na več načinov:

  • + operater
  • Bitni operatorji
  • . . itd

Kako analizirati algoritem?

Da je standardni algoritem dober, mora biti učinkovit. Zato je treba učinkovitost algoritma preverjati in vzdrževati. Lahko poteka v dveh fazah:

1. Predhodna analiza:

Priori pomeni prej. Priorna analiza torej pomeni preverjanje algoritma pred njegovo implementacijo. Pri tem je algoritem preverjen, ko je zapisan v obliki teoretičnih korakov. Ta učinkovitost algoritma se meri ob predpostavki, da so vsi drugi dejavniki, na primer hitrost procesorja, konstantni in ne vplivajo na izvedbo. To običajno naredi oblikovalec algoritma. Ta analiza je neodvisna od vrste strojne opreme in jezika prevajalnika. Daje približne odgovore za zahtevnost programa.

2. Posteriorna analiza:

Posterior pomeni po. Posteriorna analiza torej pomeni preverjanje algoritma po njegovi izvedbi. Pri tem se algoritem preveri tako, da se implementira v katerikoli programski jezik in izvede. Ta analiza pomaga pridobiti dejansko in resnično poročilo analize o pravilnosti (za vse možne vnose, če prikazuje/vrne pravilen izhod ali ne), potrebnem prostoru, porabljenem času itd. To pomeni, da je odvisno od jezika prevajalnik in vrsto uporabljene strojne opreme.

Kaj je kompleksnost algoritma in kako jo najti?

Algoritem je opredeljen kot kompleksen glede na količino prostora in časa, ki ga porabi. Zato se kompleksnost algoritma nanaša na merilo časa, ki ga bo potreboval za izvedbo in pridobitev pričakovanega izhoda, in prostora, ki ga bo potreboval za shranjevanje vseh podatkov (vnos, začasni podatki in izhod). Zato ta dva dejavnika določata učinkovitost algoritma.
Dva dejavnika kompleksnosti algoritma sta:

  • Časovni faktor : Čas se meri s štetjem števila ključnih operacij, kot so primerjave v algoritmu za razvrščanje.
  • Faktor prostora : Prostor se meri s štetjem največjega pomnilniškega prostora, ki ga algoritem potrebuje za zagon/izvedbo.

Zato je Kompleksnost algoritma lahko razdelimo na dve vrsti :

1. Kompleksnost prostora : Prostorska kompleksnost algoritma se nanaša na količino pomnilnika, ki ga algoritem potrebuje za shranjevanje spremenljivk in pridobitev rezultata. To je lahko za vhode, začasne operacije ali izhode.

Kako izračunati kompleksnost prostora?
Prostorska kompleksnost algoritma se izračuna z določitvijo naslednjih dveh komponent:

  • Fiksni del: To se nanaša na prostor, ki ga zahteva algoritem. Na primer vhodne spremenljivke, izhodne spremenljivke, velikost programa itd.
  • Spremenljivi del: To se nanaša na prostor, ki se lahko razlikuje glede na implementacijo algoritma. Na primer začasne spremenljivke, dinamično dodeljevanje pomnilnika, prostor sklada rekurzije itd.
    Zato kompleksnost prostora S(P) katerega koli algoritma P je S(P) = C + SP(I) , kjer je C fiksni del in S(I) variabilni del algoritma, ki je odvisen od karakteristike primerka I.

primer: Razmislite o spodnjem algoritmu za linearno iskanje

1. korak: ZAČNITE
2. korak: Pridobite n elementov matrike v arr in število za iskanje v x
3. korak: Začnite od skrajno levega elementa arr[] in enega za drugim primerjajte x z vsakim elementom arr[]
4. korak: če se x ujema z elementom, Natisni True.
5. korak: Če se x ne ujema z nobenim od elementov, Natisni False.
6. korak: KONEC
Tu sta 2 spremenljivki arr[] in x, kjer je arr[] spremenljivi del n elementov, x pa fiksni del. Zato je S(P) = 1+n. Torej je kompleksnost prostora odvisna od n (število elementov). Zdaj je prostor odvisen od tipov podatkov danih spremenljivk in tipov konstant in se bo ustrezno pomnožil.

2. Časovna zapletenost : Časovna kompleksnost algoritma se nanaša na količino časa, ki ga algoritem potrebuje za izvedbo in pridobitev rezultata. To je lahko za običajne operacije, pogojne stavke if-else, stavke zanke itd.

Kako izračunati , Časovna zapletenost?
Časovna kompleksnost algoritma se izračuna tudi z določitvijo naslednjih dveh komponent:

  • Stalni časovni del: Vsako navodilo, ki se izvede samo enkrat, pride v ta del. Na primer vnos, izhod, if-else, switch, aritmetične operacije itd.
  • Spremenljivi časovni del: Vsako navodilo, ki se izvede več kot enkrat, recimo n-krat, pride v ta del. Na primer zanke, rekurzija itd.
    Zato časovna kompleksnostT(P) katerega koli algoritma P je T(P) = C + TP(I) , kjer je C konstantni časovni del in TP(I) spremenljivi del algoritma, ki je odvisen od karakteristike primerka I.

primer: V zgornjem algoritmu linearnega iskanja se časovna kompleksnost izračuna na naslednji način:

1. korak: – Konstanten čas
2. korak: — spremenljivi čas (ob n vnosih)
3. korak: – spremenljivi čas (do dolžine niza (n) ali indeksa najdenega elementa)
4. korak: – Konstanten čas
5. korak: – Konstanten čas
6. korak: – Konstanten čas
Zato je T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, kar lahko rečemo kot T(n).

Kako izraziti algoritem?

  1. Naravni jezik: - Tukaj izrazimo algoritem v naravnem angleškem jeziku. Iz tega je pretežko razumeti algoritem.
  2. Diagram poteka :- Tukaj izrazimo algoritem tako, da naredimo a grafični/slikovni prikaz tega. Lažje ga je razumeti kot naravni jezik.
  3. Psevdo koda :- Tukaj izražamo algoritem v obliki opomb in informativnega besedila, napisanega v navadni angleščini, ki je zelo podobna pravi kodi, a ker nima sintakse kot kateri koli programski jezik, ga računalnik ne more prevesti ali interpretirati . To je najboljši način za izražanje algoritma, saj ga lahko razume tudi laik z nekaj šolskega znanja.