Monimutkaisuusjärjestys on termi, jota käytetään tietojenkäsittelytieteessä mittaamaan algoritmin tai ohjelman tehokkuutta. Se viittaa siihen, kuinka paljon aikaa ja resursseja tarvitaan ongelman ratkaisemiseen tai tehtävän suorittamiseen. Ohjelmoinnissa monimutkaisuusjärjestys ilmaistaan yleensä termeillä Iso O merkintä, joka antaa ylärajan algoritmin aika- tai tilavaatimuksille. Tässä artikkelissa käsittelemme C-ohjelmointikielen monimutkaisuuden järjestystä ja sen merkitystä.
C-ohjelmointikielen monimutkaisuusjärjestys:
C-ohjelmoinnissa algoritmin monimutkaisuusjärjestys riippuu ohjelman suorittamien operaatioiden määrästä. Jos meillä on esimerkiksi taulukko, jonka koko on n ja haluamme etsiä taulukosta tiettyä elementtiä, algoritmin monimutkaisuusjärjestys riippuu taulukon elementtien lukumäärästä. Jos suoritamme a Lineaarinen haku taulukon kautta monimutkaisuusjärjestys on Päällä) , mikä tarkoittaa, että elementin etsimiseen kuluva aika kasvaa lineaarisesti taulukon koon mukaan. Jos käytämme a Binäärihakualgoritmi sen sijaan tulee olemaan monimutkaisuuden järjestys O(log n) , mikä tarkoittaa, että elementin etsimiseen kuluva aika kasvaa logaritmisella taulukon koon mukaan.
Samoin muiden algoritmien monimutkaisuusjärjestys, kuten Lajittelualgoritmit , Graafialgoritmit , ja Dynaamiset ohjelmointialgoritmit riippuu myös ohjelman suorittamien toimintojen määrästä. Näiden algoritmien monimutkaisuusjärjestys voidaan ilmaista käyttämällä Iso O merkintä.
susi vs kettu
Katsotaanpa joitain yleisiä monimutkaisuuden järjestyksiä ja niitä vastaavia algoritmeja:
Tämä tarkoittaa, että algoritmi vie vakioajan syötteen koosta riippumatta. Esimerkiksi taulukon elementin avaaminen kestää O(1) aika, koska elementtiin pääsee suoraan sen indeksin avulla.
Tämä tarkoittaa, että algoritmin kuluva aika kasvaa logaritmisesti syötteen koon mukaan. Tämä näkyy yleisesti mm hajota ja hallitse -algoritmit Kuten Binäärihaku , jotka jakavat syötteen pienempiin osiin ongelman ratkaisemiseksi.
Tämä tarkoittaa, että algoritmin käytetty aika kasvaa lineaarisesti syötteen koon mukaan. Esimerkkejä tällaisista algoritmeista ovat Lineaarinen haku ja Kuplalajittelu .
Tämä tarkoittaa, että algoritmin käytetty aika kasvaa n:llä kerrottuna n:n logaritmilla. Esimerkkejä tällaisista algoritmeista ovat Quicksort ja Yhdistä lajittelu .
Tämä tarkoittaa, että algoritmin käytetty aika kasvaa neliöllisesti syötteen koon mukaan. Esimerkkejä tällaisista algoritmeista ovat Kuplalajittelu ja Lisäys Lajittele .
java merkkijono
Tämä tarkoittaa, että algoritmin käytetty aika kaksinkertaistuu jokaisella syöttökoon kasvatuksella. Tämä näkyy yleisesti mm Rekursiiviset algoritmit kuin Fibonacci-sarja .
On tärkeää tietää, että monimutkaisuusjärjestys antaa vain ylärajan algoritmin käyttämälle ajalle. Todellinen kuluva aika voi olla paljon pienempi kuin tämä raja riippuen syöttötiedoista ja algoritmin toteutuksesta.
C-ohjelmoinnissa algoritmin monimutkaisuusjärjestys voidaan määrittää analysoimalla koodia ja laskemalla suoritettujen operaatioiden määrä. Jos esimerkiksi meillä on silmukka, joka iteroituu n-koon taulukon läpi, silmukan aikamonimutkaisuus on Päällä) . Vastaavasti, jos meillä on rekursiivinen funktio, joka kutsuu itseään k kertaa, funktion aikamonimutkaisuus on O(2^k) .
Ohjelman suorituskyvyn optimoimiseksi on tärkeää valita algoritmeja, joiden monimutkaisuusaste on pienempi. Jos esimerkiksi joudumme lajittelemaan taulukon, meidän tulee käyttää lajittelualgoritmia, jonka monimutkaisuus on pienempi, kuten esim. Quicksort tai Yhdistä lajittelu , mielummin kuin Kuplalajittelu , jonka monimutkaisuus on korkeampi.
Analysoinnin monimutkaisuusjärjestys:
Algoritmin monimutkaisuusjärjestyksen analysoimiseksi meidän on määritettävä, kuinka sen käyttöaika tai tilan käyttö kasvaa syötteen koon kasvaessa. Yleisin tapa tehdä tämä on laskea algoritmin suorittamien perustoimintojen määrä.
vaihda java-ohjelmointia
Perustoiminto on toiminto, jonka suorittamiseen kuluu jatkuvasti aikaa, kuten kahden luvun lisääminen tai taulukon elementin käyttö. Laskemalla algoritmin suorittamien perustoimintojen lukumäärä syötteen koon funktiona, voimme määrittää sen monimutkaisuusjärjestyksen.
Tarkastellaan esimerkiksi seuraavaa C-funktiota, joka laskee ensimmäisen n kokonaisluvun summan:
C-koodi:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>