Algoritmin määritelmä
sana Algoritmi tarkoittaa Joukko äärellisiä sääntöjä tai ohjeita, joita on noudatettava laskelmissa tai muissa ongelmanratkaisuoperaatioissa
Tai
Proseduuri matemaattisen ongelman ratkaisemiseksi äärellisessä määrässä vaiheita, joka sisältää usein rekursiivisia operaatioita .
Siksi algoritmi viittaa rajallisten vaiheiden sarjaan tietyn ongelman ratkaisemiseksi.
Algoritmien käyttö:
Algoritmeilla on ratkaiseva rooli eri aloilla ja niillä on monia sovelluksia. Joitakin avainalueita, joilla algoritmeja käytetään, ovat:
- Tietokone Tiede: Algoritmit muodostavat tietokoneohjelmoinnin perustan ja niitä käytetään ratkaisemaan ongelmia yksinkertaisesta lajittelusta ja etsimisestä monimutkaisiin tehtäviin, kuten tekoälyyn ja koneoppimiseen.
- Matematiikka: Algoritmeja käytetään matemaattisten ongelmien ratkaisemiseen, kuten optimaalisen ratkaisun löytämiseen lineaariyhtälöjärjestelmälle tai lyhimmän polun löytämiseen kuvaajasta.
- Toimintatutkimus : Algoritmeja käytetään optimoimaan ja tekemään päätöksiä sellaisilla aloilla kuin kuljetus, logistiikka ja resurssien allokointi.
- Tekoäly: Algoritmit ovat tekoälyn ja koneoppimisen perusta, ja niitä käytetään älykkäiden järjestelmien kehittämiseen, jotka voivat suorittaa tehtäviä, kuten kuvantunnistusta, luonnollisen kielen käsittelyä ja päätöksentekoa.
- Tietotiede: Algoritmeja käytetään analysoimaan, käsittelemään ja poimimaan oivalluksia suurista tietomääristä esimerkiksi markkinoinnin, rahoituksen ja terveydenhuollon aloilla.
Nämä ovat vain muutamia esimerkkejä algoritmien monista sovelluksista. Algoritmien käyttö laajenee jatkuvasti uusien teknologioiden ja alojen ilmaantuessa, mikä tekee niistä tärkeän osan modernissa yhteiskunnassa.
Algoritmit voivat olla yksinkertaisia ja monimutkaisia riippuen siitä, mitä haluat saavuttaa.
Se voidaan ymmärtää ottamalla esimerkkiä uuden reseptin keittämisestä. Uuden reseptin valmistamista varten luetaan ohjeet ja vaiheet ja suoritetaan ne yksitellen, annetussa järjestyksessä. Näin saatu tulos on, että uusi ruokalaji on kypsennetty täydellisesti. Aina kun käytät puhelinta, tietokonetta, kannettavaa tietokonetta tai laskinta, käytät algoritmeja. Samoin algoritmit auttavat suorittamaan ohjelmointitehtävän, jotta saadaan odotettu tulos.
Suunnitellut algoritmit ovat kieliriippumattomia, eli ne ovat pelkkiä ohjeita, jotka voidaan toteuttaa millä tahansa kielellä, ja silti tulos on odotetusti sama.
Mihin algoritmeja tarvitaan?
- Algoritmit ovat välttämättömiä monimutkaisten ongelmien ratkaisemiseksi tehokkaasti ja tehokkaasti.
- Ne auttavat automatisoimaan prosesseja ja tekemään niistä luotettavampia, nopeampia ja helpompia suorittaa.
- Algoritmien avulla tietokoneet voivat myös suorittaa tehtäviä, joita ihmisten olisi vaikea tai mahdoton tehdä manuaalisesti.
- Niitä käytetään eri aloilla, kuten matematiikassa, tietojenkäsittelytieteessä, tekniikassa, rahoituksessa ja monilla muilla prosessien optimointiin, tietojen analysointiin, ennusteiden tekemiseen ja ratkaisujen tarjoamiseen ongelmiin.
Mitkä ovat algoritmin ominaisuudet?
Kuten reseptin keittämiseen ei noudatettaisi mitään kirjallisia ohjeita, vaan vain tavallista. Samoin kaikki ohjelmoinnin kirjalliset ohjeet eivät ole algoritmeja. Jotta jotkin ohjeet olisivat algoritmeja, niillä on oltava seuraavat ominaisuudet:
- Selkeä ja yksiselitteinen : Algoritmin tulee olla yksiselitteinen. Jokaisen sen vaiheen tulee olla selkeä kaikilta osin ja johtaa vain yhteen tarkoitukseen.
- Hyvin määritellyt tulot : Jos algoritmi käskee ottaa syötteitä, sen tulee olla hyvin määriteltyjä syötteitä. Se voi ottaa syötteitä tai ei.
- Hyvin määritellyt lähdöt: Algoritmin on määriteltävä selkeästi, mitä tuotos saadaan, ja sen tulee myös olla hyvin määritelty. Sen pitäisi tuottaa vähintään 1 tulos.
- rajallisuus: Algoritmin tulee olla äärellinen, eli sen tulee päättyä äärellisen ajan kuluttua.
- Mahdollinen: Algoritmin on oltava yksinkertainen, yleinen ja käytännöllinen, jotta se voidaan suorittaa käytettävissä olevilla resursseilla. Se ei saa sisältää tulevaisuuden teknologiaa tai mitään.
- Kielestä riippumaton: Suunnitellun algoritmin tulee olla kielestä riippumaton, eli sen on oltava pelkkiä ohjeita, jotka voidaan toteuttaa millä tahansa kielellä, ja silti tulos on odotetusti sama.
- Syöte : Algoritmilla on nolla tai useampi syöte. Jokaisen, joka sisältää perusoperaattorin, on hyväksyttävä nolla tai useampi syöte.
- Lähtö : Algoritmi tuottaa vähintään yhden tulosteen. Jokaisen perusoperaattorin sisältävän käskyn on hyväksyttävä nolla tai useampi syöte.
- Määritelmä: Kaikkien algoritmin ohjeiden on oltava yksiselitteisiä, tarkkoja ja helposti tulkittavia. Viitamalla mihin tahansa algoritmin ohjeeseen voi selvästi ymmärtää, mitä on tehtävä. Jokainen perusoperaattori ohjeessa on määriteltävä ilman epäselvyyttä.
- Rajallisuus: Algoritmin on lopetettava rajallisen määrän vaiheita kaikissa testitapauksissa. Jokainen käsky, joka sisältää perusoperaattorin, on lopetettava rajallisen ajan sisällä. Äärettömät silmukat tai rekursiiviset funktiot ilman perusehtoja eivät ole äärellisiä.
- Tehokkuus: Algoritmi on kehitettävä käyttämällä hyvin yksinkertaisia, yksinkertaisia ja toteutettavissa olevia operaatioita, jotta se voidaan jäljittää pelkällä paperilla ja kynällä.
Algoritmin ominaisuudet:
- Sen pitäisi päättyä rajallisen ajan kuluttua.
- Sen pitäisi tuottaa vähintään yksi tulos.
- Sen pitäisi kestää nolla tai enemmän syöttöä.
- Sen pitäisi olla deterministinen tarkoittaa saman lähdön antamista samalle tulotapaukselle.
- Algoritmin jokaisen vaiheen on oltava tehokas, eli jokaisen vaiheen tulee tehdä työtä.
Algoritmien tyypit:
Saatavilla on useita erilaisia algoritmeja. Jotkut tärkeät algoritmit ovat:
1. Brute Force -algoritmi :
Se on yksinkertaisin tapa ratkaista ongelma. Raaka voima-algoritmi on ensimmäinen tapa löytää ongelma, kun näemme ongelman.
2. Rekursiivinen algoritmi :
Rekursiivinen algoritmi perustuu rekursio . Tässä tapauksessa ongelma jaetaan useisiin alaosiin ja kutsutaan samaksi funktioksi uudestaan ja uudestaan.
3. Peruutusalgoritmi :
Backtracking-algoritmi rakentaa ratkaisun etsimällä kaikista mahdollisista ratkaisuista. Käyttämällä tätä algoritmia jatkamme ratkaisun rakentamista kriteerien mukaisesti. Aina kun ratkaisu epäonnistuu, palaamme vikakohtaan seuraavan ratkaisun pohjalta ja jatkamme tätä prosessia, kunnes löydämme ratkaisun tai kaikki mahdolliset ratkaisut on hoidettu.
4. Hakualgoritmi :
Hakualgoritmit ovat niitä, joita käytetään elementtien tai elementtiryhmien etsimiseen tietystä tietorakenteesta. Ne voivat olla erityyppisiä lähestymistavan tai tietorakenteen mukaan, josta elementti tulisi löytää.
5. Lajittelualgoritmi :
Lajittelu on tietoryhmän järjestämistä tietyllä tavalla vaatimuksen mukaan. Algoritmeja, jotka auttavat tämän toiminnon suorittamisessa, kutsutaan lajittelualgoritmeiksi. Yleensä lajittelualgoritmeja käytetään lajittelemaan tietoryhmiä kasvavalla tai laskevalla tavalla.
6. Hajautusalgoritmi :
Hashing-algoritmit toimivat samalla tavalla kuin hakualgoritmi. Mutta ne sisältävät indeksin avaintunnuksella. Hashingissa tietylle tiedolle määrätään avain.
7. hajota ja hallitse -algoritmi :
Tämä algoritmi jakaa ongelman osaongelmiin, ratkaisee yhden aliongelman ja yhdistää ratkaisut lopullisen ratkaisun saamiseksi. Se koostuu seuraavista kolmesta vaiheesta:
- Jakaa
- Ratkaista
- Yhdistää
8. Ahne algoritmi :
Tämän tyyppisessä algoritmissa ratkaisu rakennetaan osa osalta. Seuraavan osan ratkaisu on rakennettu seuraavan osan välittömän hyödyn perusteella. Se ratkaisu, joka tuottaa eniten hyötyä, valitaan seuraavan osan ratkaisuksi.
9. Dynaaminen ohjelmointialgoritmi :
Tämä algoritmi käyttää jo löydettyä ratkaisua, jotta ongelman saman osan toistuva laskenta vältetään. Se jakaa ongelman pienempiin päällekkäisiin aliongelmiin ja ratkaisee ne.
10. Satunnaistettu algoritmi :
Satunnaistetussa algoritmissa käytämme satunnaislukua, joten siitä on välitöntä hyötyä. Satunnaisluku auttaa päättämään odotetun tuloksen.
Lisätietoja algoritmien tyypeistä on artikkelissa Algoritmien tyypit .
Algoritmien edut:
- Se on helppo ymmärtää.
- Algoritmi on vaiheittainen esitys tietyn ongelman ratkaisusta.
- Algoritmissa ongelma on jaettu pienempiin osiin tai vaiheisiin, joten ohjelmoijan on helpompi muuntaa se todelliseksi ohjelmaksi.
Algoritmien haitat:
- Algoritmin kirjoittaminen vie paljon aikaa, joten se vie aikaa.
- Monimutkaisen logiikan ymmärtäminen algoritmien avulla voi olla hyvin vaikeaa.
- Haarautumis- ja silmukkalausekkeita on vaikea näyttää algoritmeissa (imp) .
Kuinka suunnitella algoritmi?
Algoritmin kirjoittaminen edellyttää seuraavat asiat:
- The ongelma joka on ratkaistava tällä algoritmilla eli selkeällä ongelmanmäärittelyllä.
- The rajoituksia ongelma on otettava huomioon ongelmaa ratkaistaessa.
- The syöttö otettava ongelman ratkaisemiseksi.
- The ulostulo on odotettavissa, kun ongelma on ratkaistu.
- The ratkaisu tämä ongelma on annettujen rajoitusten sisällä.
Sitten algoritmi kirjoitetaan yllä olevien parametrien avulla siten, että se ratkaisee ongelman.
Esimerkki: Harkitse esimerkkiä kolmen numeron lisäämisestä ja tulosta summasta.
java do while -silmukka
Vaihe 1: Edellytysten täyttäminen
Kuten edellä todettiin, algoritmin kirjoittaminen edellyttää, että sen edellytykset täyttyvät.
- Ongelma, joka on ratkaistava tällä algoritmilla : Lisää 3 numeroa ja tulosta niiden summa.
- Ongelman rajoitteet, jotka on otettava huomioon ongelmaa ratkaistaessa : Numeroissa saa olla vain numeroita, ei muita merkkejä.
- Syöte, joka on otettava ongelman ratkaisemiseksi: Kolme lisättävää numeroa.
- Odotettava tulos, kun ongelma on ratkaistu: Kolmen syötteeksi otetun luvun summa eli yksi kokonaislukuarvo.
- Ratkaisu tähän ongelmaan annetuissa rajoituksissa: Ratkaisu koostuu 3 numeron lisäämisestä. Se voidaan tehdä +-operaattorin avulla, bittikohtaisesti tai millä tahansa muulla menetelmällä.
Vaihe 2: Algoritmin suunnittelu
Suunnitellaan nyt algoritmi yllä olevien edellytysten avulla:
Algoritmi lisätä 3 numeroa ja tulostaa niiden summa:
- ALKAA
- Määritä 3 kokonaislukumuuttujaa num1, num2 ja num3.
- Ota kolme lisättävää numeroa syötteinä muuttujiin num1, num2 ja num3.
- Ilmoita kokonaislukumuuttujan summa tallentaaksesi kolmen luvun tuloksena olevan summan.
- Lisää 3 numeroa ja tallenna tulos muuttujan summaan.
- Tulosta muuttujan summan arvo
- LOPPU
Vaihe 3: Testaa algoritmia toteuttamalla se.
Algoritmin testaamiseksi toteutetaan se C-kielellä.
Ohjelmoida:
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>> numero1; cout<< ' ' << num1 << endl; cout << 'Enter the 2nd number: '; cin>> numero2; cout<< ' ' << num2 << endl; cout << 'Enter the 3rd number: '; cin>> numero3; 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> Lähtö
Syötä ensimmäinen numero: 0 Syötä 2. numero: 0 Syötä kolmas numero: -1577141152 Kolmen numeron summa on: -1577141152
Tässä on koodin vaiheittainen algoritmi:
- Ilmoita kolme muuttujaa num1, num2 ja num3 tallentaaksesi kolme lisättävää numeroa.
- Ilmoita muuttuva summa kolmen luvun summan tallentamiseksi.
- Käytä cout-lausetta pyytääksesi käyttäjää syöttämään ensimmäinen numero.
- Käytä cin-lausetta ensimmäisen numeron lukemiseen ja tallenna se numeroon1.
- Käytä cout-lausetta pyytääksesi käyttäjää antamaan toinen numero.
- Käytä cin-lausetta toisen luvun lukemiseen ja tallenna se numeroon2.
- Käytä cout-lausetta pyytääksesi käyttäjää syöttämään kolmannen numeron.
- Käytä cin-lausetta lukeaksesi ja tallentaaksesi kolmannen numeron numerossa3.
- Laske kolmen luvun summa +-operaattorilla ja tallenna se summamuuttujaan.
- Käytä cout-lausetta tulostaaksesi kolmen luvun summa.
- Pääfunktio palauttaa arvon 0, mikä osoittaa ohjelman onnistuneen suorituksen.
Aika monimutkaisuus: O(1)
Aputila: O(1)
Yksi ongelma, monta ratkaisua: Algoritmin ratkaisu voi olla tai ei voi olla enemmän kuin yksi. Se tarkoittaa, että algoritmia toteutettaessa voi olla useampi kuin yksi menetelmä sen toteuttamiseksi. Esimerkiksi yllä olevassa 3 luvun lisäämistehtävässä summa voidaan laskea monella tavalla:
- + operaattori
- Bittiviisaat operaattorit
- . . jne
Kuinka analysoida algoritmia?
Jotta standardialgoritmi olisi hyvä, sen on oltava tehokas. Siksi algoritmin tehokkuus on tarkistettava ja ylläpidettävä. Se voi olla kahdessa vaiheessa:
1. Ennakkoanalyysi:
Priori tarkoittaa ennen. Tästä syystä Priori-analyysi tarkoittaa algoritmin tarkistamista ennen sen toteuttamista. Tässä algoritmi tarkistetaan, kun se kirjoitetaan teoreettisten vaiheiden muodossa. Tämä algoritmin tehokkuus mitataan olettamalla, että kaikki muut tekijät, esimerkiksi prosessorin nopeus, ovat vakioita eivätkä vaikuta toteutukseen. Tämän tekee yleensä algoritmin suunnittelija. Tämä analyysi on riippumaton kääntäjän laitteistotyypistä ja kielestä. Se antaa likimääräiset vastaukset ohjelman monimutkaisuuteen.
2. Jälkimmäinen analyysi:
Posterior tarkoittaa jälkeen. Siten jälkianalyysi tarkoittaa algoritmin tarkistamista sen toteuttamisen jälkeen. Tässä algoritmi tarkistetaan toteuttamalla se millä tahansa ohjelmointikielellä ja suorittamalla se. Tämä analyysi auttaa saamaan todellisen ja todellisen analyysiraportin oikeellisuudesta (jokaiselle mahdolliselle syötteelle, jos se näyttää/palauttaa oikean lähdön), tilatarpeesta, kulutetusta ajasta jne. Eli se riippuu järjestelmän kielestä. kääntäjä ja käytetyn laitteiston tyyppi.
Mikä on algoritmin monimutkaisuus ja miten se löydetään?
Algoritmi määritellään kompleksiseksi sen kuluttaman tilan ja ajan määrän perusteella. Tästä syystä algoritmin monimutkaisuus viittaa ajan mittaan, jonka se tarvitsee suorittaakseen ja saadakseen odotetun lähdön, ja tilaa, jonka se tarvitsee tallentaakseen kaiken datan (syöte, väliaikaiset tiedot ja lähtö). Näin ollen nämä kaksi tekijää määrittävät algoritmin tehokkuuden.
Algoritmin monimutkaisuuden kaksi tekijää ovat:
- Aikatekijä : Aika mitataan laskemalla avaintoimintojen, kuten vertailujen, lukumäärä lajittelualgoritmissa.
- Avaruustekijä : Tila mitataan laskemalla algoritmin suorittamiseen/suoritukseen vaatima enimmäismuistitila.
Siksi Algoritmin monimutkaisuus voidaan jakaa kahteen tyyppiin :
1. Avaruuden monimutkaisuus : Algoritmin tilan monimutkaisuus viittaa muistin määrään, jonka algoritmi tarvitsee muuttujien tallentamiseen ja tuloksen saamiseen. Tämä voi olla tuloja, tilapäisiä toimintoja tai lähtöjä.
Kuinka laskea tilan monimutkaisuus?
Algoritmin tilamonimutkaisuus lasketaan määrittämällä seuraavat kaksi komponenttia:
- Kiinteä osa: Tämä tarkoittaa tilaa, jonka algoritmi vaatii. Esimerkiksi syöttömuuttujat, lähtömuuttujat, ohjelman koko jne.
- Muuttuva osa: Tämä viittaa tilaan, joka voi olla erilainen algoritmin toteutuksen mukaan. Esimerkiksi väliaikaiset muuttujat, dynaaminen muistin varaus, rekursiopinotila jne.
Siksi tilan monimutkaisuus S(P) minkä tahansa algoritmin P on S(P) = C + SP(I) , jossa C on kiinteä osa ja S(I) on algoritmin muuttuva osa, joka riippuu ilmentymän ominaisuudesta I.
Esimerkki: Harkitse alla olevaa lineaarihaun algoritmia
Vaihe 1: ALOITA
Vaihe 2: Hanki taulukon n elementtiä arr:sta ja haettava numero x:stä
Vaihe 3: Aloita arr[]:n vasemmanpuoleisesta elementistä ja vertaa x:ää yksitellen jokaiseen arr[]-elementtiin
Vaihe 4: Jos x vastaa elementtiä, tulosta True.
Vaihe 5: Jos x ei vastaa mitään elementtejä, tulosta false.
Vaihe 6: LOPETA
Tässä on 2 muuttujaa arr[] ja x, joissa arr[] on n elementin muuttuva osa ja x on kiinteä osa. Siten S(P) = 1+n. Avaruuden monimutkaisuus riippuu siis n:stä (elementtien lukumäärästä). Nyt tila riippuu annettujen muuttujien ja vakiotyyppien tietotyypeistä ja se kerrotaan vastaavasti.
2. Aika monimutkaisuus : Algoritmin aikamonimutkaisuus tarkoittaa aikaa, jonka algoritmi tarvitsee suorittaakseen ja saadakseen tuloksen. Tämä voi koskea normaaleja operaatioita, ehdollisia if-else-lauseita, silmukkakäskyjä jne.
Kuinka laskea , Aika monimutkaisuus?
Algoritmin aikamonimutkaisuus lasketaan myös määrittämällä seuraavat kaksi komponenttia:
- Jatkuva osa: Kaikki käskyt, jotka suoritetaan vain kerran, tulevat tähän osaan. Esimerkiksi tulo, lähtö, jos-else, kytkin, aritmeettiset operaatiot jne.
- Vaihtuva aikaosa: Kaikki käskyt, jotka suoritetaan useammin kuin kerran, esimerkiksi n kertaa, tulevat tähän osaan. Esimerkiksi silmukat, rekursio jne.
Siksi aika monimutkaisuusT(P) minkä tahansa algoritmin P on T(P) = C + TP(I) , jossa C on vakioaikaosa ja TP(I) on algoritmin muuttuva osa, joka riippuu ilmentymän ominaispiirteestä I.
Esimerkki: Yllä olevassa Lineaarisen haun algoritmissa aikamonimutkaisuus lasketaan seuraavasti:
Vaihe 1: – Jatkuva aika
Vaihe 2: — Vaihtuva aika (n syöttöä)
Vaihe 3: – Muuttuva aika (taulukon pituuteen (n) tai löydetyn elementin indeksiin asti)
Vaihe 4: – Jatkuva aika
Vaihe 5: – Jatkuva aika
Vaihe 6: – Vakioaika
Siten T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, joka voidaan sanoa muodossa T(n).
Kuinka ilmaista algoritmi?
- Luonnollinen kieli: - Tässä ilmaisemme algoritmin luonnollisella englannin kielellä. Algoritmia on liian vaikea ymmärtää sen perusteella.
- Vuokaavio :- Tässä ilmaisemme algoritmin tekemällä a graafinen/kuvallinen esitys siitä. Se on helpompi ymmärtää kuin luonnollinen kieli.
- Pseudokoodi :- Tässä ilmaistamme algoritmin merkintöjen ja informatiivisen tekstin muodossa, joka on kirjoitettu selkeällä englanniksi, joka on hyvin samanlainen kuin oikea koodi, mutta koska sillä ei ole syntaksia kuten millään ohjelmointikielellä, tietokone ei voi kääntää tai tulkita sitä. . Se on paras tapa ilmaista algoritmi, koska sen voi ymmärtää jopa koulutason tietämystä omaava maallikko.