Funktioiden summan monimutkaisuusjärjestys. Algoritminen monimutkaisuus. Hakualgoritmit. Lajittelualgoritmit. Algoritmisesti ratkaisemattomia ongelmia
Algoritmin tehokkuuden arvioimiseksi tärkeimmät indikaattorit ovat:
Algoritmin suoritusaika,
- tarvittava määrä RAM-muistia.
Nykyään puolen vuosisadan teknologisen kehityksen vuoksi ensimmäinen indikaattori (suoritusaika) on usein paljon tärkeämpi kuin toinen, joten jatkamme vain sitä yksityiskohtaisesti.
Yksinkertaistuksia algoritmien suoritusajan arvioimiseen
D. Knuthin teoksissa algoritmien suoritusajan analysointiin ehdotettiin seuraavaa lähestymistapaa: kokonaisaika koostuu kunkin perusoperaation kustannus*taajuuden arvoista. Perusoperaatioita voivat olla yhteen-, kerto- ja jakolasku, elementin saaminen taulukosta indeksin mukaan, kokonaislukujen vertailu jne. On helppo nähdä, että tässä tapauksessa arvion laskeminen algoritmin suoritusajasta on melko työlästä. Siksi A. Turing sanoi, että on kätevää käyttää jopa karkeita approksimaatioita algoritmien suoritusajan arvioista: voit antaa painotuksia erilaisille operaatioille riippuen niiden esiintymistiheydestä algoritmin toiminnan aikana ja ottaa huomioon vain ne toiminnot. joilla on suurimmat painot. Esimerkiksi matriiseja kerrottaessa tulee huomioida vain operaatiot, kuten kertominen ja lukujen kirjoittaminen, koska Nämä ovat yleisimpiä operaatioita.Ottaen huomioon vain enitenusein esiintyviä operaatioita - ensimmäinen yksinkertaistus, jota ehdotetaan algoritmien suoritusajan likimääräiseen laskemiseen.
Toinen yksinkertaistus on hylätä alemman kertaluvun termit (eli termit), jotka vaikuttavat vain vähän algoritmin kokonaisajoaikaan. Esimerkiksi (tässä numero N kuvaa syöttötietojen kokoa),
\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),
\(1/6N^3\) sijaan he kirjoittavat "tämän algoritmin monimutkaisuus \(O(N^3)\", \(3N^4\) sijaan he kirjoittavat "tällä algoritmilla on monimutkaisuus \(O(N) ^4)\ )".
Suuren O:n määritelmä
Sanotaan, että \(f\) on "O iso" arvosta \(g\) arvolle \(x \to x_0\), jos on vakio \(C>0\) siten, että kaikille \(x\) pisteen \(x_0\) läheisyydestä, epäyhtälö \(|f(x)| \leq C|g(x)|\) pätee. Alla on kuva määritelmästä (\(x\)-akseli on syötetietojen koko, \(y\)-akseli on algoritmin suoritusaika). Näemme, että alkaen tietystä pisteestä, koska syötetietojen koko yleensä \(\propto\) \(f(n)\) kasvaa hitaammin kuin \(g(n)\) ja yleensä \(g (n)\) ikään kuin rajoittaisi sitä ylhäältä.
Esimerkkejä. \(1 = O(N), N = O(N^2).\)
Muodon \(O(N)\) estimaattien lisäksi käytetään estimaattia \(\Omega(N)\) (omega large). Se ilmaisee funktion kasvun alarajaa. Oletetaan esimerkiksi, että algoritmin operaatioiden lukumäärä kuvataan funktiolla \(f(N)=\Omega(N^2)\). Tämä tarkoittaa, että jopa onnistuneimmassa tapauksessa suoritetaan vähintään \(N^2\) toimintoa. Vaikka arvio \(O(N^3)\) takaa, että pahin tapaus on vain järjestyksessä \(N^3\) toimia. Käytetään myös arviota \(\Theta(N)\), joka on ylempi ja alempi asymptoottinen arvio, kun\(O(N)\) ja \(\Omega(N)\) ovat samat.Joten \(O(N)\) on likimääräinen arvio algoritmista huonoimmalla syöttödatalla,\(\Omega(N)\) - parhaimmilla syöttötiedoilla,\(\Theta(N)\) - identtinen lyhenne\(O(N)\) ja \(\Omega(N)\).
Ajoaika-arviot eri algoritmeille
Merkitään algoritmin suoritusaikana T(N). Olkoon tutkittavalla algoritmilla muoto:
1. joukko ohjeita, jotka sisältävät vain perustoiminnot:
Lausuma 1;
...
lause k;
Sitten T(N) = T(lause 1) + ... + T(lause k).
Koska Jokainen käsky sisältää vain perusoperaatioita, jolloin tämän koodinpalan suoritusaika ei riipu syötetyn tiedon koosta (ei kasva syöttötietojen koon mukaan), ts. on vakio. Tämän algoritmin monimutkaisuus on O(1).
2. if-else lausunnot
Jos (ehto) (
lausesarja 1
}
muu(
lausesarja 2
}
Tässä suoritetaan joko lausekkeiden sarja 1 tai lauseiden sarja 2, joten koska Haluamme estimoida pahimman tapauksen suoritusajan, T(N) = max(T(lauseiden sekvenssi 1), T(lauseiden sekvenssi 2)). Jos esimerkiksi lausesarjan 1 suoritusaika on O(N) ja lauseiden sarja on O(1), niin T(N) = O(N).
Sille (i = 0; i< N; i++) {
lauseiden sarja
}
Koska silmukka suoritetaan N kertaa, sitten lausesarja suoritetaan myös N kertaa. Jos T(lausesarja) = O(1), niin T(N) = O(N)*O(1) = O(N).
4. Sisäkkäiset silmukat.
Sille (i = 0; i< N; i++) {
for (j = 0; j< M; j ++){
...
}
}
Ulompi silmukka suoritetaan N kertaa. Joka kerta kun ulompi silmukka suoritetaan, sisempi silmukka M suoritetaan Harkitse nyt tätä koodia: Sille (i = 0; i< N; i++) { Katsotaanpa muutosta sisäisen silmukan iteraatioiden lukumäärässä ulkoisen silmukan iteraatiosta riippuen. I sykli j (suorituskertojen lukumäärä) Sitten lausesarja suoritetaan N + N-1 + ... + 1 kertaa. Tällaisten määrien laskemiseksi nopeasti matemaattisen analyysin kaavat, tässä tapauksessa kaava, ovat hyödyllisiä
Ja tässä on muita useimmin tarvittavia kaavoja, jotka ovat hyödyllisiä tällaisissa tapauksissa: 4. Kun väite sisältää menetelmäkutsun, väitteen suoritusaikaarvio lasketaan ottaen huomioon menetelmän suoritusaikaestimaatti. Esimerkiksi: for (j = 0; j< N; j ++){ 5. Binäärihaku (binäärihaku). Int l = 0; Binäärihaku mahdollistaa luvun k indeksin löytämisen järjestetyssä taulukossa, jos tämä luku ei ole siinä, palautetaan -1. Ensin verrataan k:tä taulukon keskellä olevaan numeroon. Jos k on pienempi kuin tämä luku, meidän on etsittävä sitä edelleen taulukon vasemmasta puoliskosta, jos enemmän, niin oikeasta puoliskosta. Seuraavaksi k:ta verrataan edellisessä vaiheessa valitun taulukon puolikkaan keskellä olevaan numeroon jne. Jokaisella iteraatiolla hakutila pienenee puoleen. Herää kysymys: kuinka monta iteraatiota joudutaan tekemään pahimmassa tapauksessa (eli kun taulukosta ei koskaan löydy k:n suuruista lukua eikä vertailuun jää dataa). Näemme, että 1 iteraation jälkeen on jäljellä \(N/2\) dataa indeksin \(k\) etsimiseen, 2 iteraation jälkeen \(N/4\) dataa jäljellä, 3 iteroinnin jälkeen - \( N/8\) ja jne. Tiedämme iteraatioiden lukumäärän pahimmassa tapauksessa, jos ratkaisemme yhtälön \(\frac(N)(2^x)=1\). Tämä yhtälö vastaa yhtälöä \(2^x=N\), joten \(x=log_(2)(N)\) tai \(x=log(N)\) (katso logaritmin määritelmä). Siksi binäärihakualgoritmin monimutkaisuusarvio on \(O(logN)\). Hyvä uutinen on, että useimpien algoritmien suoritusajan luonnehtimiseen riittää muutama funktio: \(1, logN, N, NlogN, N^2, N^3, 2^N\). Kaavio havainnollistaa algoritmin suoritusajan eri kasvunopeuksia syöttötietojen koosta riippuen: Etenkin tästä kaaviosta käy selvästi ilmi, että jos algoritmin suoritusaika on "logaritminen", ts. algoritmin monimutkaisuus on \(O(logN)\), niin tämä on erittäin siistiä, koska sen suoritusaika kasvaa hyvin hitaasti syötetietojen kasvaessa, jos suoritusaika riippuu lineaarisesti syötetyn datan koosta, niin tämäkään ei ole huono asia, mutta on parempi olla käyttämättä algoritmeja, joilla on eksponentiaalinen ajoaika (\( O(2^N)\)) tai käytä vain hyvin pienissä tietokokoissa. luokkiin P ja NP Todellinen ei-negatiivinen funktio \(f(m)\), joka on määritetty argumentin positiivisille kokonaislukuarvoille, kutsutaan polynomirajoitetuksi, jos on polynomi \(P(m)\), jolla on todelliset kertoimet siten, että \( f(m) \leq P( m)\) kaikille \(m \in N^+\). Tehtävät, joille on olemassa algoritmeja "polynomisella" ajoajalla, kuuluvat luokkaan P (nämä ongelmat ratkaistaan yleensä nopeasti ja ilman ongelmia). Muodollinen määritelmä. Kieli L kuuluu luokkaan P silloin ja vain, jos on olemassa deterministinen Turingin kone M, joka: Kaikille syötetyille tiedoille M lopettaa työnsä polynomiajassa, NP-luokan ongelmia- tehtävät, jotka täyttävät ehdon: jos on vastaus (mahdollinen ratkaisu), niin se on helppo tarkistaa - tarkista onko se ratkaisu vai ei. Tarkastellaan esimerkkiä NP-luokan ongelmasta. Olkoon joukko kokonaislukuja annettu esimerkiksi (-7, -3, -2, 5, 8). Sinun on selvitettävä, onko näiden lukujen joukossa 3 numeroa, joiden summa on nolla. Tässä tapauksessa vastaus on "kyllä" (esim. tällainen kolmo on numerot (-3,-2,5). kokonaislukujoukkojen koko kasvaa, 3 alkiosta koostuvien osajoukkojen määrä kasvaa eksponentiaalisesti. Sillä välin, jos meille annetaan yksi tällainen osajoukko (jota kutsutaan myös sertifikaatiksi), niin voimme helposti tarkistaa, onko sen elementtien summa. yhtä suuri kuin 0. Muodollinen määritelmä: Kieli L kuuluu luokkaan NP, jos ja vain jos on olemassa polynomit \(p\) ja \(q\) sekä deterministinen Turingin kone M siten, että: Minkä tahansa \(x,y\) koneen M syötetiedoissa \((x,y)\) suorittaa ajassa \(p(|x|)\), Polynominen pelkistyvyys tai Karpin vähennettävyyttä. Funktio \(f_1\) pelkistyy funktioksi \(f_2\), jos P:ssä on funktio \(f \) siten, että mille tahansa \(x\) \(f_(1)(x)=f_( 2 )(f(x))\). Tehtävää T kutsutaan NP-kovaa, jos sille on olemassa NP-täydellinen ongelma, joka pelkistyy T:ksi polynomiajassa. Tarkoitamme tässä Cookin vähennettävyyttä. Cookin pelkistys tehtävästä \(R_1\) arvoon \(R_2\) on polynominen aikaalgoritmi, joka ratkaisee ongelman \(R_1\) edellyttäen, että tehtävään \(R_2\) ratkaisun löytävä funktio annetaan sille oraakkelina , eli sen käyttö vie vain yhden askeleen. Tässä ovat mahdolliset suhteet yllä olevien ongelmaluokkien välillä (tutkijat eivät vieläkään ole varmoja, ovatko P ja NP samat). Muiden projektin osallistujien ei tule muokata artikkelia ennen määritettyä määräaikaa. verkkosivusto. Kun se on valmis, jokaisella osallistujalla on oikeus korjata tämä artikkeli oman harkintansa mukaan ja poistaa tämä varoitus, joka näytetään mallin ((Tehtävä)) avulla. Katso myös ohjeita Resurssin käytöstä verkkosivusto koulutusprosessissa. Laskennallinen monimutkaisuusteoria- laskennallisen teorian ala, joka tutkii laskennallisen ongelman ratkaisemiseen tarvittavan työn määrää. Ongelma katsotaan vaikeaksi, jos ongelman ratkaiseminen vaatii paljon resursseja riippumatta siitä, millä algoritmilla se ratkaistaan. Teoria formalisoi tämän intuitiivisen käsitteen ottamalla käyttöön matemaattisia laskentamalleja näiden ongelmien tutkimiseksi ja niiden ratkaisemiseen tarvittavien resurssien määrän, kuten käytetyn ajan ja muistin, määrittämiseksi. Myös muut monimutkaisuusmitat ovat mahdollisia, kuten: viestien lukumäärä (viestinnän monimutkaisuus), elementtien lukumäärä toiminnallisten elementtien piirissä (piirin monimutkaisuus) ja prosessorien lukumäärä. Erityisesti laskennalliset monimutkaisuusteoriat määrittelevät käytännön rajat sille, mitä tietokoneet voivat tehdä ja mitä eivät. Laskennallisen monimutkaisuuden teorioihin liittyvät läheisesti algoritmien analyysi ja laskettavuuden teoria. Suurin ero laskennallisen monimutkaisuusteorian ja algoritmianalyysin välillä on se, että jälkimmäisessä analysoidaan tietyn algoritmin tarvitsemien resurssien määrää ongelman ratkaisemiseksi, kun taas edellinen kysyy yleisemmän kysymyksen kaikista mahdollisista algoritmeista, joita voitaisiin käyttää ratkaise sama ongelma. Tarkemmin sanottuna laskennallinen monimutkaisuusteoria yrittää luokitella ongelmia, jotka voidaan tai ei voida ratkaista sopivalla määrällä rajoitettuja resursseja. Käytettävissä olevien resurssien rajoitusten käyttöönotto on puolestaan se, mikä erottaa laskennallisen kompleksisuusteorian laskettavuusteoriasta: jälkimmäinen kysyy, mitä ongelmia voidaan periaatteessa ratkaista algoritmisesti rajoittamatta laskentaresursseja. Laskennalliset ongelmat voidaan nähdä äärettömänä joukkona pareja: (tehtävän esiintymä, ratkaisu tietylle esiintymälle). Laskennallisen ongelman syötemerkkijono on merkkijono, joka kuvaa ongelman ilmentymää. Laskennallisen ongelman lähtömerkkijono on kuvaus syötemerkkijonon kuvaaman ongelman ilmentymän ratkaisusta. Esimerkiksi luvun alkuluvun tunnistamisongelma: ongelman esiintymä on luku, jolle on tarpeen määrittää, onko se alkuluku vai ei, ratkaisu on merkkijono "kyllä", jos tämä luku on alkuluku ja " ei” muuten. Laskennallisen monimutkaisuuden teoria ottaa huomioon vain massiiviset ongelmat, ts. vaatimus äärettömästä tehtäväinstanssien joukosta on pakollinen. Laskennallisia ongelmia tarkasteltaessa ongelma-ilmentymän kuvaus on aakkosten yläpuolella oleva rivi. Pääsääntöisesti aakkoset otetaan binäärisiksi (eli joukko (0,1)). Erilaiset matemaattiset objektit on koodattava vastaavasti. Joten esimerkiksi kokonaisluvut voidaan esittää binäärimuodossa, ja graafit voidaan koodata suoraan niiden vierekkäisyysmatriisien tai vierekkäisyysluetteloiden binäärikoodauksen kautta. Tunnistusongelmat ovat yksi laskennallisen monimutkaisuuden teorian keskeisistä tutkimuskohteista. Tunnistusongelma on erityinen laskennallinen ongelma, johon vastaus on joko "kyllä" tai "ei" (1 tai 0). Tunnistusongelma voidaan muotoilla ongelmaksi siitä, kuuluuko syötemerkkijono kaikkien syötemerkkijonojen joukon tiettyyn osajoukkoon (kieleen). Syöttötehtävämerkkijono kuuluu vastaavaan kieleen silloin ja vain, jos vastaus tähän merkkijonoon on "kyllä". Tunnistustehtävä on siis tehtävä tunnistaa, kuuluuko syötemerkkijono tiettyyn kieleen. Esimerkki tunnistustehtävästä. Tulorivi: mielivaltaisen graafin kuvaus. Ongelmana on päättää, onko tietty graafi yhdistetty vai ei. Yhdistettyjen graafien kieli on joukko kaikkien yhdistettyjen graafien kuvauksia. Tämän kielen tarkan määritelmän saamiseksi on päätettävä, kuinka graafit koodataan binäärimerkkijonoiksi. Hakutehtävä on laskennallinen tehtävä, jonka tulosarvo on monimutkaisempi kuin tunnistustehtävässä (eli se ei ole vain "kyllä" tai "ei"). Esimerkki hakuongelmasta on matkustavan myyjän ongelma. Matkamyyjä-ongelma (matkustava myyjä - matkustava kauppias) on yksi tunnetuimmista kombinatorisista optimointiongelmista. Tehtävänä on löytää kannattavin reitti, joka kulkee määritettyjen kaupunkien läpi vähintään kerran ja palaa sitten alkuperäiseen kaupunkiin. Ongelman ehdot osoittavat reitin kannattavuuskriteerin (lyhyin, halvin, kokonaiskriteeri jne.) ja vastaavat etäisyyksien, kustannusten jne. matriisit. Pääsääntöisesti reitin tulee kulkea jokaisen reitin läpi. kaupunki vain kerran - tällä tavalla Tässä tapauksessa valinta tehdään Hamiltonin syklien joukosta. Syöttömerkkijono: painotetun (eli numeromerkit reunoissa) graafin kuvaus. Tulostusrivi on kuvaus matkustavan myyjän optimaalisesta reitistä. Tunnistustehtävien ja hakutehtävien välillä on parisuhde. Hakuongelma voidaan muotoilla tunnistusongelmaksi. Esimerkiksi hakutehtävässä "kahden luvun kertominen" vastaava parillinen tunnistustehtävä voidaan esittää kolmoisjoukona (A, B, C) siten, että suhde A × B = C pätee. Laskennallisen monimutkaisuuden teoria syntyi tarpeesta verrata algoritmien suorituskykyä ja kuvata selkeästi niiden käyttäytymistä (suoritusaika, tarvittavan muistin määrä jne.) tulon ja lähdön koosta riippuen. Algoritmin käyttämien perusoperaatioiden määrä tietyn ongelman ilmentymän ratkaisemiseen ei riipu vain syötetietojen koosta, vaan myös itse tiedosta. Esimerkiksi lisäyslajittelualgoritmin operaatioiden määrä on paljon pienempi, jos syötetiedot on jo lajiteltu. Tällaisten vaikeuksien välttämiseksi harkitse algoritmin pahimman mahdollisen aikamonimutkaisuuden käsitettä. Algoritmin aikamonimutkaisuus (pahimmassa tapauksessa) on tulo- ja lähtötietojen koon funktio, joka on yhtä suuri kuin algoritmin suorittamien atomioperaatioiden enimmäismäärä tietyn kokoisen ongelman ratkaisemiseksi. Ongelmissa, joissa lähdön koko ei ole suurempi tai verrannollinen syötteen kokoon, voidaan aikamonimutkaisuutta tarkastella vain tulon koon funktiona. Samoin kuin pahimmassa tapauksessa aikamonimutkaisuuden käsite, määritellään parhaassa tapauksessa algoritmin aikamonimutkaisuuden käsite. Tarkastellaan myös algoritmin keskimääräisen toiminta-ajan käsitettä, eli algoritmin toiminta-ajan matemaattista odotusta. Joskus he sanovat yksinkertaisesti: "Algoritmin aika monimutkaisuus" tai "Algoritmin ajoaika", mikä tarkoittaa algoritmin ajallista monimutkaisuutta pahimmassa, parhaassa tai keskimääräisessä tapauksessa (riippuen kontekstista). Analogisesti aikamonimutkaisuuden kanssa määritetään algoritmin spatiaalinen monimutkaisuus, mutta tässä ei puhuta alkeisoperaatioiden määrästä, vaan käytetyn muistin määrästä. Huolimatta siitä, että algoritmin aikamonimutkaisuusfunktio voidaan joissain tapauksissa määrittää tarkasti, on useimmiten turha etsiä sen tarkkaa arvoa. Asia on siinä, että ensinnäkin aikamonimutkaisuuden tarkka arvo riippuu alkeisoperaatioiden määrittelystä (monimutkaisuus voidaan mitata esimerkiksi aritmeettisten operaatioiden tai Turingin koneoperaatioiden lukumäärällä) ja toiseksi syöttötietojen koosta. kasvaa, vakiotekijöiden ja termien alempien kertalukujen osuus tarkan käyttöajan lausekkeessa tulee erittäin merkityksettömäksi. Suuren syöttödatan huomioon ottaminen ja algoritmin käyntiajan kasvujärjestyksen arviointi johtaa algoritmin asymptoottisen kompleksisuuden käsitykseen. Lisäksi algoritmi, jonka asymptoottinen kompleksisuus on pienempi, on tehokkaampi kaikille syöttötiedoille, lukuun ottamatta mahdollisesti pientä dataa. Monimutkaisuus määritetään laskennallisen mallin perusteella, jossa laskelmat suoritetaan. Laskentamalleja on monia erilaisia: Post-kone, Minsky-kone, lambda-laskenta, osittain rekursiiviset funktiot, normaalit Markov-algoritmit, hajasaantimuistikoneet (RAM-koneet) jne. Mainitsemme vain suosituimman laskentamallin - Turingin kone. Turingin kone (MT) on abstrakti laskentakone (abstrakti laskentakone). Alan Turing ehdotti vuonna 1936 algoritmin käsitteen formalisoimista. Turingin kone on äärellisen tilakoneen jatke, ja se pystyy Church-Turingin teesin mukaan simuloimaan kaikkia muita toteuttajia (määrittämällä siirtymäsääntöjä), jotka jollakin tavalla toteuttavat vaiheittaisen laskennan prosessin, jossa jokainen laskentavaihe on melko alkeellinen. Turingin kone koostuu nauhasta, joka on molempiin suuntiin ääretön (Turingin koneet ovat mahdollisia, joissa on useita äärettömiä nauhoja), jaettuna soluihin, ja ohjauslaitteesta, joka voi olla jossakin monista tiloista. Ohjauslaitteen mahdollisten tilojen määrä on rajallinen ja tarkasti määritelty. Ohjauslaite voi liikkua nauhaa pitkin vasemmalle ja oikealle, lukea ja kirjoittaa joidenkin äärellisten aakkosten symboleja nauhan soluihin. Erityinen tyhjä symboli on varattu, joka täyttää kaikki nauhan solut lukuun ottamatta niitä (lopullinen numero), joille syötetiedot on kirjoitettu. Ohjauslaite toimii siirtymäsääntöjen mukaisesti, jotka edustavat tietyn Turingin koneen toteuttamaa algoritmia. Jokainen siirtymäsääntö ohjaa konetta nykyisestä tilasta ja nykyisessä solussa havaitusta symbolista riippuen kirjoittamaan uusi symboli tähän soluun, siirtymään uuteen tilaan ja siirtämään yhden solun vasemmalle tai oikealle. Jotkut Turingin koneen tilat voidaan merkitä terminaaleiksi, ja siirtyminen mihin tahansa niistä tarkoittaa työn loppua, algoritmin pysähtymistä. Turingin koneen sanotaan olevan deterministinen, jos taulukossa on korkeintaan yksi sääntö, joka vastaa kutakin tilan ja nauhasymbolin yhdistelmää. Jos on olemassa pari (nauhasymboli - tila), jolle on 2 tai useampi käsky, tällaista Turingin konetta kutsutaan ei-deterministiseksi. Turingin koneen malli mahdollistaa erilaisia laajennuksia. Voidaan harkita Turingin koneita mielivaltaisella määrällä nauhoja ja moniulotteisia nauhoja erilaisin rajoituksin; koneita, jotka käyttävät satunnaisuuden lähdettä. Turingin kone on yksi tärkeimmistä laskentamalleista monimutkaisuusteoriassa. Monimutkaisuusluokat ovat laskennallisia ongelmia, joiden laskennallinen monimutkaisuus on suunnilleen yhtä suuri. On kielen monimutkaisuusluokkia ja toiminnallisia monimutkaisuusluokkia. Kielten monimutkaisuusluokka on joukko predikaatteja (funktioita, jotka ottavat syötteeksi sanan ja palauttavat vastauksen 0 tai 1), jotka käyttävät suunnilleen saman määrän resursseja laskemiseen. Funktionaalisen kompleksisuusluokan käsite on samanlainen, paitsi että se ei ole joukko predikaatteja, vaan joukko funktioita. Monimutkaisuusteoriassa oletusmonimutkaisuusluokka on kielten monimutkaisuusluokka. Tyypillinen monimutkaisuusluokan määritelmä näyttää tältä: Monimutkaisuusluokka X on joukko predikaatteja P(x), joka voidaan laskea Turingin koneilla ja käyttää laskennassa O(f(n))-resursseja, missä n on sanan x pituus. Resursseiksi otetaan yleensä laskenta-aika (Turingin koneen työjaksojen määrä) tai työalue (käytetyt solut nauhalla käytön aikana). Myös joidenkin luokkien predikaattien (eli sanajoukon, jossa predikaatti palauttaa 1) tunnistamien kielten sanotaan kuuluvan samaan luokkaan. Lisäksi monia luokkia voidaan kuvata myös matemaattisen logiikan tai peliteorian avulla. Luokat merkitään yleensä isoilla kirjaimilla. Luokan C komplementti (eli luokka, jonka komplementit kuuluvat C:hen) merkitään co-C:ksi. Jokaiselle luokalle on luokka tehtäviä, jotka ovat "vaikeimpia". Tämä tarkoittaa, että mikä tahansa tehtävä luokasta pelkistyy sellaiseksi tehtäväksi, ja lisäksi itse tehtävä on luokassa. Tällaisia ongelmia kutsutaan tietyn luokan täydellisiksi ongelmiksi. Luokka P (englannin polynomista) on joukko tunnistusongelmia, jotka voidaan ratkaista deterministisellä Turingin koneella syötteen pituuden aikapolynomissa. Vastaavasti hakuongelmia varten määritellään luokka FP (englannin funktionaalisesta polynomista). Tarkastellaan muodollisemmin deterministisiä Turingin koneita, jotka laskevat vastauksen, joka on annettu syöttönauhalla annetusta syöttöaakkosesta. Turingin koneen toiminta-aika kiinteälle syöttösanalle x on Turingin koneen työjaksojen lukumäärä koneen alusta alusta loppuun. Jonkin Turingin koneen laskeman funktion monimutkaisuus on funktio, joka riippuu syöttösanan pituudesta ja on yhtä suuri kuin koneen maksimikäyttöaika kaikille kiinteän pituisille syöttösanoille: Jos toiminto f siellä on Turingin kone M niin että jollekin numerolle c ja tarpeeksi iso n, silloin he sanovat, että se kuuluu luokkaan FP tai on ajallisesti polynomi. Luokka P on yksi laskennallisen monimutkaisuuden teorian perusluokista. NP-luokka (englanninkielisestä non-deterministisesta polynomista) on joukko tunnistusongelmia, joiden ratkaisuaika riippuu merkittävästi syötetietojen koosta; samaan aikaan on olemassa algoritmi, joka saatuaan syötearvojen kuvauksen ohella lisäinformaatiota (todistaa ratkaisulle) voi ratkaista ongelman melko nopeasti (ajassa, joka ei ylitä datan koko). Muodollisesti kielen L sanotaan kuuluvan luokkaan NP, jos luokasta P on olemassa kaksipaikkainen predikaatti R(x, y) (eli polynomiajassa laskettavissa) ja polynomi p siten, että mille tahansa sanalle x, jonka pituus on n, ehto "x kuuluu L:ään" vastaa ehtoa "on y, jonka pituus on pienempi kuin p(n), joten R(x, y) on tosi." Sanaa y kutsutaan todistajaksi, että x kuuluu kieleen L. Jos siis meillä on sana, joka kuuluu kieleen ja toinen todistajasana, jonka pituus on rajoitettu (jota voi olla vaikea löytää), voimme nopeasti varmistaa, että x todella kuuluu L:lle. Mikä tahansa NP:hen kuuluva ongelma voidaan ratkaista eksponentiaalisessa ajassa etsimällä kaikki mahdolliset p(n) pituiset todistajat. Esimerkkiongelma NP:stä: tunnistustehtävä "Lineaarisen epäyhtälöjärjestelmän kokonaislukuratkaisun olemassaolo." Todistaja on ratkaisu eriarvoisuusjärjestelmään. Todistajaratkaisun sopivuus on helppo varmistaa polynomiajassa. NP-luokka sisältää P-luokan. Laskennallisen monimutkaisuuden teoriassa on monia ratkaisemattomia ongelmia, jotka koskevat pääasiassa tiettyjen monimutkaisuusluokkien jakamista tai sisäkkäisyyttä. Yksi näistä kysymyksistä on luokkien P ja NP tasa-arvoongelma. Loppujen lopuksi luokkayhtälön P ja NP ongelma on tämä: jos myönteinen vastaus kysymykseen voidaan varmistaa nopeasti (polynomiajassa), niin onko totta, että vastaus tähän kysymykseen löytyy nopeasti (polynomiajassa)? Luokkien P ja NP määritelmästä seuraa välittömästi seuraava seuraus: . Tämän sisällyttämisen tiukkuudesta ei kuitenkaan vielä tiedetä mitään, ts. onko olemassa algoritmia, joka on NP:ssä, mutta ei P:ssä Jos tällaista algoritmia ei ole, niin kaikki luokkaan NP kuuluvat ongelmat voidaan ratkaista polynomiajassa, mikä lupaa valtavia hyötyjä laskennallisesti? Tällä hetkellä vaikeimmat NP-ongelmat (ns. NP-täydet tehtävät) voidaan ratkaista eksponentiaalisessa ajassa, mikä on lähes aina mahdotonta hyväksyä. Kysymystä näiden kahden luokan tasa-arvoisuudesta pidetään yhtenä vaikeimmista avoimista ongelmista teoreettisen tietojenkäsittelytieteen alalla. Tällä hetkellä useimmat matemaatikot uskovat, että nämä luokat eivät ole tasa-arvoisia. Clay Mathematics Institute sisällytti tämän ongelman Millennium Problems -luetteloon ja tarjosi miljoonan Yhdysvaltain dollarin palkkion sen ratkaisusta. Olet luultavasti törmännyt merkintöihin, kuten O(log n), useammin kuin kerran tai kuullut lauseita, kuten "logaritminen laskennallinen monimutkaisuus", joka on osoitettu joillekin algoritmeille. Ja jos et vieläkään ymmärrä, mitä tämä tarkoittaa, tämä artikkeli on sinua varten. Algoritmien monimutkaisuus mitataan yleensä niiden suoritusajalla tai muistinkäytöllä. Molemmissa tapauksissa monimutkaisuus riippuu syötetietojen koosta: 100 elementin ryhmä käsitellään nopeammin kuin vastaava 1000 elementti. Harva on kuitenkin kiinnostunut tarkasta ajasta: se riippuu prosessorista, tietotyypistä , ohjelmointikieli ja monet muut parametrit. Vain asymptoottinen monimutkaisuus on tärkeä, eli monimutkaisuus, kun syöttödatan koko pyrkii äärettömään. Oletetaan, että jonkin algoritmin on suoritettava 4n 3 + 7n ehdollista operaatiota käsitelläkseen n syötedatan elementtiä. Kun n kasvaa, lopulliseen käyttöaikaan vaikuttaa huomattavasti enemmän n:n nostaminen kuutioon kuin kertominen 4:llä tai 7n lisääminen. Sitten he sanovat, että tämän algoritmin aikamonimutkaisuus on O(n 3), eli se riippuu kuutioisesti syötetyn datan koosta. Ison O:n käyttö (tai ns. O-merkintä) tulee matematiikasta, jossa sitä käytetään vertailemaan funktioiden asymptoottista käyttäytymistä. Muodollisesti O(f(n)) tarkoittaa, että algoritmin ajoaika (tai varatun muistin määrä) kasvaa syötetyn datan koosta riippuen korkeintaan nopeammin kuin jokin vakio kerrottuna f(n):llä. Esimerkiksi algoritmilla lajittelemattoman taulukon suurimman elementin löytämiseksi on tämä monimutkaisuus. Meidän on käytävä läpi kaikki taulukon n elementtiä ymmärtääksemme, mikä niistä on suurin. Yksinkertaisin esimerkki on binäärihaku. Jos taulukko on lajiteltu, voimme puolittamismenetelmällä tarkistaa, sisältääkö se tietyn arvon. Tarkastetaan keskimmäinen elementti, jos se on suurempi kuin etsimämme, hylkäämme taulukon toisen puoliskon - se ei todellakaan ole siellä. Jos se on pienempi, päinvastoin - hylkäämme ensimmäisen puolikkaan. Jatkamme siis jakamista puoliksi, ja lopuksi tarkistamme log n elementtejä. Esimerkiksi lisäyslajittelualgoritmilla on tämä monimutkaisuus. Kanonisessa toteutuksessa se koostuu kahdesta sisäkkäisestä silmukasta: yksi käy läpi koko taulukon ja toinen etsii paikan seuraavalle elementille jo lajiteltusta osasta. Siten operaatioiden määrä riippuu taulukon koosta n * n, eli n 2. On muitakin vaikeusluokituksia, mutta ne kaikki perustuvat samaan periaatteeseen. Käy myös niin, että algoritmin ajoaika ei riipu lainkaan syötetyn tiedon koosta. Sitten kompleksisuutta merkitään O(1) . Esimerkiksi taulukon kolmannen elementin arvon määrittämiseksi sinun ei tarvitse muistaa elementtejä tai käydä niitä läpi monta kertaa. Sinun tarvitsee aina vain odottaa syötetietovirran kolmatta elementtiä ja tämä on tulos, jonka laskeminen vie saman verran aikaa mille tahansa datamäärälle. Sama koskee muistin arviointeja, kun tämä on tärkeää. Algoritmit voivat kuitenkin käyttää huomattavasti enemmän muistia syöttötietojen kokoa suurentaessaan kuin muut, mutta silti ne toimivat nopeammin. Ja päinvastoin. Tämä auttaa valitsemaan parhaat tavat ratkaista ongelmia nykyisten olosuhteiden ja vaatimusten perusteella. On perinteistä arvioida algoritmin monimutkaisuusaste sen käyttämien perustietokoneresurssien määrällä: prosessoriaika ja RAM. Tässä suhteessa esitellään käsitteitä, kuten algoritmin aikamonimutkaisuus ja algoritmin volyymimonimutkaisuus. Aikamonimutkaisuusparametri tulee erityisen tärkeäksi ongelmissa, joihin liittyy vuorovaikutteista ohjelman toimintaa tai reaaliaikaisia ohjausongelmia. Usein jollekin tekniselle laitteelle ohjausohjelmaa luovan ohjelmoijan on löydettävä kompromissi laskelmien tarkkuuden ja ohjelman ajoajan välillä. Yleensä tarkkuuden lisääntyminen lisää aikaa. Ohjelman monimutkaisuus tulee kriittiseksi, kun käsiteltävien tietojen määrä saavuttaa tietokoneen RAM-kapasiteetin rajan. Nykyaikaisissa tietokoneissa tämän ongelman vakavuus vähenee sekä RAM-muistin määrän kasvun että monitasoisen tallennusjärjestelmän tehokkaan käytön vuoksi. Ohjelmalla on pääsy erittäin suurelle, käytännössä rajattomalle muistialueelle (virtuaalimuisti). Päämuistin puute johtaa vain hidastumiseen levyn vaihdon vuoksi. Tekniikoita käytetään minimoimaan ajanhukkaa tällaisen vaihdon aikana. Tämä on välimuistin käyttöä ja ohjelmaohjeiden laitteiston katselua tarvittavalle siirtomäärälle, jonka avulla voit siirtää vaaditut arvot levyltä päämuistiin etukäteen. Edellä olevan perusteella voimme päätellä, että kapasitiivisen monimutkaisuuden minimointi ei ole ensisijainen tehtävä. Siksi olemme jatkossa kiinnostuneita pääasiassa algoritmien aikakompleksisuudesta. Ohjelman suoritusaika on verrannollinen suoritettujen toimintojen määrään. Tietysti aikayksiköissä (sekunnissa) se riippuu myös prosessorin nopeudesta (kellotaajuudesta). Jotta algoritmin aikamonimutkaisuuden indikaattori olisi muuttumaton tietokoneen teknisten ominaisuuksien suhteen, se mitataan suhteellisissa yksiköissä. Tyypillisesti aika monimutkaisuus mitataan suoritettujen toimintojen lukumäärällä. Tyypillisesti algoritmin aikamonimutkaisuus riippuu syöttötiedoista. Tämä voi riippua sekä alkutietojen koosta että sen määrästä. Jos merkitsemme algoritmin aikamonimutkaisuusparametrin α arvoa symbolilla Tα ja kirjaimella V jotakin lähdedataa kuvaavaa numeerista parametria, niin aikakompleksisuus voidaan esittää funktiona Tα(V). Parametrin V valinta riippuu ratkaistavasta ongelmasta tai tämän ongelman ratkaisemiseen käytetyn algoritmin tyypistä. Esimerkki 1. Arvioidaan positiivisen kokonaisluvun faktoriaalin laskentaalgoritmin aikamonimutkaisuus. Funktio Factorial(x:Integer): Kokonaisluku; Var m,i: Kokonaisluku; Kohdalle i:=2 To x Do m:=ro*i; Lasketaan ohjelman suorittamien operaatioiden kokonaismäärä tietylle x:n arvolle. Operaattori m:=1 suoritetaan kerran; silmukan runko (jossa kaksi operaatiota: kertolasku ja osoitus) suoritetaan x - 1 kertaa; Tehtävä Factorial:=m suoritetaan kerran. Jos kukin operaatioista otetaan monimutkaisuusyksiköksi, niin koko algoritmin aikamonimutkaisuus on 1 + 2 (x - 1) + 1 = 2x. Tästä syystä on selvää, että arvo x tulee ottaa parametriksi. Aikamonimutkaisuusfunktio osoittautui seuraavaksi: Tässä tapauksessa voidaan sanoa, että aika monimutkaisuus riippuu lineaarisesti dataparametrista - tekijäfunktion argumentin arvosta. Esimerkki 2. Kahden vektorin A = (a1, a2, …, ak), B = (b1, b2, …, bk) skalaaritulon laskeminen. For i:=l To k Tee AB:=AB+A[i]*B[i]; Tässä tehtävässä syötetyn datan määrä on n = 2k. Tehtyjen operaatioiden määrä on 1 + 3k = 1 + 3(n/2). Tässä voit ottaa V= k= n/2. Algoritmin monimutkaisuus ei ole riippuvainen vektorien A ja B elementtien arvoista. Kuten edellisessä esimerkissä, tässä voidaan puhua aikamonimutkaisuuden lineaarisesta riippuvuudesta dataparametrista. Algoritmin aikamonimutkaisuusparametriin liittyy yleensä kaksi teoreettista ongelmaa. Ensimmäinen on löytää vastaus kysymykseen: mihin aikarajaan voidaan päästä parantamalla ongelmanratkaisualgoritmia? Tämä raja riippuu itse ongelmasta ja on siksi sen oma ominaisuus. Toinen ongelma liittyy algoritmien luokitteluun aikamonimutkaisuuden mukaan. Funktio Tα(V) yleensä kasvaa V:n kasvaessa. Kuinka nopeasti se kasvaa? On algoritmeja, joiden Tα:n lineaarinen riippuvuus V:stä (kuten oli tarkastelemissamme esimerkeissä), joilla on neliöllinen riippuvuus ja joiden riippuvuus on suurempi. Tällaisia algoritmeja kutsutaan polynomeiksi. Ja on algoritmeja, joiden monimutkaisuus kasvaa nopeammin kuin mikään polynomi. Ongelma, jonka algoritmiteoreetikot usein ratkaisevat, on seuraava kysymys: onko polynomialgoritmi mahdollista tietylle ongelmalle? Algoritmeja analysoitaessa usein kohtaavat toiminnot: Neljällä ensimmäisellä funktiolla on alhainen kasvunopeus ja algoritmeja, joiden toiminta-aika on arvioitu näiden funktioiden avulla, voidaan pitää nopeina. Eksponentiaalisen funktion kasvunopeutta luonnehditaan joskus "räjähdysmäiseksi". Vertailun vuoksi oletetaan, että on olemassa algoritmeja, joiden monimutkaisuus (operaatioiden määrä) heijastuu melko tarkasti näissä funktioissa. Suoritetaan nämä algoritmit tietokoneella, joka toimii nopeudella 10 12 operaatiota sekunnissa. Sisäänkäynnin pituudella n≤ 100000 algoritmia, joiden nopeus on arvioitu neljällä ensimmäisellä funktiolla, saavat vastauksen sekunnin murto-osassa. Algoritmille, jonka monimutkaisuus on 2 n Käyttöaika on arvioitu seuraavasti: Kysymys 15 = 49. Sekventiaaliset, sykliset ja rekursiiviset algoritmit. Peräkkäiset algoritmit
– algoritmit, joissa lohkot suoritetaan peräkkäin peräkkäin tietyn mallin järjestyksessä. Esimerkki. Laske kolmion, jonka sivut ovat a,b,c, ympärysmitta.13 Haaroittumisrakenteen algoritmi Käytännössä on harvoin mahdollista esittää ongelman ratkaisu algoritmin muodossa lineaarinen rakenne. Usein riippuen mistä tahansa väliaineesta laskentatulokset suoritetaan joko jommankumman mukaan kaavoja, ts. riippuen jonkin loogisen ehdon täyttymisestä laskentaprosessi suoritetaan yhden tai toisen kaavan mukaan. Tällaisen laskennallisen prosessin algoritmia kutsutaan algoritmiksi haarautuva rakenne. Haarautuminen on ohjausrakenne, joka järjestää vain suorituksen toinen kahdesta määritetystä toimesta oikeudenmukaisuudesta riippuen jokin ehto. Ehto on kysymys, johon on kaksi mahdollista vastausta: kyllä tai ei. Haaroittuminen kirjataan kahdessa muodossa: täydellinen ja epätäydellinen (kuvat 1 a, b). a) täydellinen lomake b) epätäydellinen lomake Sykliset algoritmit –
algoritmit, joissa on tarpeen laskea toistuvasti arvoja käyttämällä samoja matemaattisia riippuvuuksia (lohkokaavioita) niihin sisältyvien määrien eri arvoille. Silmukoiden käyttö voi vähentää merkittävästi piirin kokoa algoritmi ja vastaavan ohjelman pituus. On sykliä annettu ja tuntematon määrä toistoja. Tietyllä määrällä toistoja - lenkki laskurilla. Tuntemattomalla määrällä toistoja - silmukka, jolla on ehto, silmukka jälkiehdoin. Itseensä suoraan tai epäsuorasti viittaavaa funktiota (tai proseduuria) kutsutaan rekursiiviseksi. Rekursio on menetelmä, jolla funktio määritellään sen aikaisempien ja aiemmin määritettyjen arvojen kautta, sekä menetelmä laskelmien järjestäminen, jossa funktio kutsuu itseään toisella argumentilla Rekursiivisia algoritmeja toteutettaessa jokainen rekursiovaihe ei ratkaise ongelmaa suoraan, vaan pelkistää sen samaksi pienemmäksi ongelmaksi. Tämän prosessin pitäisi johtaa sellaisen kokoiseen ongelmaan, että ratkaisu on melko helppo. Sitten "käänteinen liike" antaa peräkkäisiä ratkaisuja yhä suuremmalle ongelmalle alkuperäiseen ongelmaan asti. Rekursiivisen proseduurin toteutus perustuu pinoon (store-type memory), joka tallentaa kaikkiin proseduurin kutsuihin liittyvät tiedot, joissa se ei ole vielä saanut työtään valmiiksi. Rekursio on tapa järjestää laskentaprosessi, kun algoritmi viittaa itseensä. Rekursion periaate mahdollistaa monimutkaisen ongelman ratkaisemisen peräkkäin ratkaisemalla yksinkertaisemmat osaongelmat. Rekursiota pidetään yhtenä syklisen algoritmin muunnelmista. Rekursiivinen organisointimuoto mahdollistaa sen, että algoritmille saadaan kompaktimpi muoto. Siten ongelma ratkaistaan monimutkaisesta yksinkertaiseen - rekursiivisen algoritmin sisältö heijastaa monimutkaisempaa objektia yksinkertaisemman samantyyppisen kohteen kautta. Tyypillisesti rekursiivinen algoritmi sisältää seuraavat pääosat: – syklin suorittamisen ehto; – rekursion runko, joka sisältää toimenpiteet, jotka on tarkoitettu suoritus jokaisessa iteraatiossa; – rekursiovaihe, jossa rekursiivinen algoritmi kutsuu itseään. On olemassa ero suoran ja epäsuoran rekursion välillä. Ensimmäisessä tapauksessa algoritmi sisältää funktion, joka kutsuu itseään. Jos funktio kutsuu toista funktiota, joka puolestaan kutsuu ensimmäistä, niin tällainen funktio kutsutaan epäsuoraksi rekursiiviseksi. Rekursiivisten algoritmien päävaatimus on, että käännösprosessi ei ole täytyy olla ääretön. Toisin sanoen se on pantava täytäntöön puhelun valmistumisen tarkistaminen tai rekursiivisessa määritelmässä pitäisi on rajoitus, jonka mukaan alustus tehdään jatkossa rekursio pysähtyy. Esimerkki rekursiivisesta funktiosta on luvun kertoimen laskeminen. int factoria(int n) if (n) palauttaa n* factoria(n-1); muuten paluu 1; Esimerkki rekursiivisesta menettelystä: Pohditaan, mitä tapahtuu, jos pääohjelmassa tehdään kutsu esimerkiksi muotoon Rec(3). Alla on vuokaavio, joka näyttää lauseiden suoritusjärjestyksen. Vaikeustoiminto 0(1). Jatkuvan monimutkaisuuden algoritmeissa useimmat ohjelman toiminnot suoritetaan yhden tai useamman kerran. Mikä tahansa algoritmi, joka vaatii aina (tietojen koosta riippumatta) saman verran aikaa, on jatkuvasti monimutkainen. Monimutkaisuusfunktio 0(N). Ohjelman ajoaika on yleensä lineaarinen, jolloin kutakin syöttötiedon elementtiä tarvitsee käsitellä vain lineaarinen määrä kertoja. Tämä monimutkaisuusfunktio luonnehtii yksinkertaista sykliä. Monimutkaisuusfunktio 0(N 2), 0(N 3), 0(№) -
polynomin monimutkaisuusfunktio: operaatioiden määrä kasvaa neliön mukana N. Yleisessä tapauksessa se voi olla O(A^), riippuen ongelman monimutkaisuudesta. Tämä monimutkaisuusfunktio luonnehtii monimutkaista sykliä. Vaikeustoiminto O(loki 2 (A0), 0 (N log2(A0). Tämä on aika, jolloin toimivat algoritmit, jotka jakavat suuren ongelman useisiin pieniin ja sitten ne ratkaistuaan yhdistävät ratkaisuja. Monimutkaisuusfunktio 0(e N). Eksponentiaalisesti monimutkaiset algoritmit johtuvat useimmiten lähestymisestä, jota kutsutaan raakavoimaksi. Monimutkaisuusfunktio 0(M) - toimenpiteiden määrä kasvaa suhteessa faktoriaaliseen N. Ohjelmoijan tulee osata analysoida algoritmeja ja määrittää niiden monimutkaisuus. Algoritmin aikamonimutkaisuus voidaan laskea sen ohjausrakenteiden analyysin perusteella. Algoritmit ilman silmukoita ja rekursiivisia kutsuja ovat jatkuvasti monimutkaisia. Jos rekursiota ja silmukoita ei ole, kaikki ohjausrakenteet voidaan pelkistää jatkuvasti monimutkaisiksi rakenteiksi. Tästä johtuen koko algoritmille on ominaista myös jatkuva monimutkaisuus. Algoritmin monimutkaisuuden määrittäminen perustuu pääasiassa silmukoiden ja rekursiivisten kutsujen analysointiin. Harkitse esimerkiksi algoritmia taulukon elementtien käsittelyyn. /": = 1 - N tee Aloita Tämän algoritmin monimutkaisuus NOIN(A), koska silmukan runko suoritetaan A kertaa ja silmukan rungon kompleksisuus on 0(1). Jos yksi silmukka on sisäkkäinen toisen sisällä ja molemmat silmukat riippuvat saman muuttujan koosta, koko mallille on ominaista neliöllinen monimutkaisuus. For /: = 1 to N tehdä jonkun hyväksi j: = 1 - N tee Aloita Tämän ohjelman monimutkaisuus 0 (N 2). Esimerkki 1. Arvioidaan sellaisen ohjelman monimutkaisuus, joka tulee näppäimistöltä taulukkoon ja löytää siitä suurimman elementin. Algoritmi koostuu seuraavista vaiheista: Lasketaan yhteen operaatioiden määrä A + (A - 1) + 1 = 2A, ts. olemassa sellainen vakio, että minkään A:n operaatioiden määrä ei ylitä CA:ta. Siksi algoritmin monimutkaisuus on 0(A). Esimerkki 2. Arvioidaan sellaisen ohjelman monimutkaisuus, joka syöttää näppäimistöltä taulukon ja löytää siitä elementin, jolla on tietty ominaisuus (esimerkiksi tietty arvo). Algoritmi koostuu seuraavista vaiheista: Parhaassa tapauksessa määritetty algoritmi vaatii A + 2 -operaatioita (koko taulukon syöttö, yksi vertailu, lähtö), pahimmassa tapauksessa (kun sellaista elementtiä ei ole, 2A + 1 -operaatio). Jos A on suuri luku, esimerkiksi suuruusluokkaa 10 6, yksikkö voidaan jättää huomiotta. Siksi algoritmin monimutkaisuus on yhtä suuri kuin 0 (N). Esimerkki 3. Määritellään salausalgoritmin monimutkaisuusfunktio pituiselle sanalle L korvausmenetelmällä. Olkoon taulukko, johon jokaiselle aakkoston merkille kirjoitetaan se merkki, jolla se on korvattava. Merkitään aakkosten kirjainten lukumäärä S. Algoritmi koostuu seuraavista vaiheista: Leikkausten kokonaismäärä 1 + (S+)L. Jos se on riittävän suuri S Ja L yksiköt voidaan jättää huomiotta, ja käy ilmi, että annetun algoritmin kompleksisuusfunktio on O(S L). Esimerkki 4. Määritellään luonnollisen luvun muunnosalgoritmin kompleksisuusfunktio 1
V binäärilukujärjestelmään (ilman tiedonsyöttö- ja tulostustoimintoja). Algoritmi koostuu seuraavista vaiheista: Operaatioiden kokonaismäärä ei ylitä 1 + log 2 A. Siksi kuvattu algoritmi on monimutkainen 0 (og 2 N).
for (j = i + 1; j< N; j ++){
lauseiden sarja
}
}
0 N
1 N-1
2 N-2
...
N-1 1
Nuo. Tämän algoritmin monimutkaisuus on \(O(N^2)\).
Jos menetelmän suoritusaika on \(g(N)=O(N)\), niin \(T(N) = O(N)*O(N) = O(N^2)\).
int u = A. pituus - 1
int m;
kun (l<= u) {
m = l + (u - 1)/2
jos A[m]< k {
l = m +1;
}
muuten jos A[m] == k (
palauttaa m;
}
muu(
u = m - 1;
}
}
paluu -1;
- kaikille \(x \in L\) M tuottaa tuloksen 1,
- kaikille \(x\), jotka eivät kuulu \(L\), M tuottaa tuloksen 0.
- jokaiselle \(x \in L\) on merkkijono \(y\), jonka pituus on \(q(|x|)\), jolloin \(M(x,y)=1\),
- kaikille \(x\) ei \(L\) ja kaikille merkkijonoille, joiden pituus on \(q(|x|)\) \(M(x,y)=0\).
Tehtävää T kutsutaan NP-täydellinen, jos se kuuluu luokkaan NP ja mikä tahansa muu ongelma NP:stä voidaan pelkistää siihen polynomiajassa. Ehkä tunnetuin esimerkki NP-täydellisestä ongelmasta on SAT-ongelma (sanasta satisfiability). Annetaan kaava, joka sisältää Boolen muuttujat, operaattorit "AND", "OR", "NOT" ja sulkeet. Ongelmana on: onko mahdollista antaa arvoja kaikille kaavassa esiintyville muuttujille? valehdella Ja totta niin, että kaava saa arvon " totta".
Laskennalliset ongelmat
Tehtävätapaukset
Tehtävänäkymä
Tunnistustehtävät
Etsi tehtäviä
Mittausvaikeus
Laskennalliset mallit
Turingin kone
Vaikeusluokat
Luokka P
Luokka NP
Avoimet ongelmat
Luokkien P ja NP tasa-arvoongelma
Kirjallisuus
Vaikeusaste
Esimerkkejä
O(n) - lineaarinen kompleksisuus
O(log n) - logaritminen monimutkaisuus
O(n 2) - neliöllinen kompleksisuus
menettely Rec(a: kokonaisluku); alkaa jos a>0 sitten Rec(a-1); writeln(a); loppu;
