Algoritmin monimutkaisuus

> LeekScript-opetusohjelma

Yleinen idea

Funktion tai algoritmin kuluttamien operaatioiden määrän arvioimiseksi on hyödyllistä saada käsitys sille annettujen argumenttien koon tai parametrin koon ja suoritettujen operaatioiden enimmäismäärän välisestä suhteesta. . Tätä kutsutaan algoritmiseksi monimutkaiseksi.

Aloitetaan yksinkertaisella esimerkillä: a for-silmukka.

for (var i=0; i N, meillä on f(n) < K x g(n).*

Selvä, olen saanut suuret sanat esiin. Mitä tämä määritelmä oikeastaan tarkoittaa? Että funktio f kasvaa "ei nopeammin" kuin g n kasvaessa. f voi olla suurempi kuin g, mutta näiden kahden suhde on aina pienempi kuin tietty luku (määritelmän K). Sovelletaan tätä koodiin: Otetaan (matemaattiseksi) funktioksi f maksimimäärä operaatioita, jotka tietty koodinpala suorittaa sen syötteen koon mukaan. Pyrimme löytämään yksinkertaisen funktion g siten, että f(n)=O(g(n)). Karkeasti se tarkoittaa sitä, että mitataan suurin määrä kertoja, kuinka monta kertaa peruskäskyt toistuvat koodissa (näiden ohjeiden hinta lakaistaan siis maton alle: se on määritelmän K).

Esimerkkejä

Huh huh. Siirrytään esimerkkeihin, niin näemme selvemmin. Palataan aikaisempaan for-silmukkaan:

for (var i=0; i<n; i++){ say("Olen porkkana"); }

Jos merkitsemme f tämän koodin suorittamien operaatioiden maksimimäärän, olemme nähneet, että f(n) oli suunnilleen yhtä suuri kuin 30 x n plus silmukan pieni hinta. Todellakin, sanottu käsky toistetaan n kertaa, mikä maksaa vakiona 30 operaatiota. Voidaan siis sanoa, että f:tä hallitsee funktio g(n)=n. Näin ollen meillä on f(n)=O(n). Sanomme myös, että tämä koodinpätkä on "in O(n)".

Ja n-koon taulukoiden leikkausfunktio? Olemme nähneet, että se kuluttaa karkeasti n² x (työntötoimintojen määrä + kahden elementin vertailun hinta). Olettaen, että push-kustannus on vakio (mikä on väärin, mutta en halua mennä heti yksityiskohtiin), saamme asettamalla K = (push-operaatioiden lukumäärä + kahden elementin vertailun hinta), että leikkausfunktiota hallitsee n²: sanomme, että leikkausfunktio on "in O(n²)".

Näin ollen merkintä O mahdollistaa kustannusten kasvun mittaamisen syötteen koon mukaan: leikkausfunktiolla tulee olemaan kustannus, joka kasvaa "samalla nopeudella" kuin n² (n taulukoiden koon kanssa).

Kiinnostus Leekwarsia kohtaan

Tämä käsite on mielenkiintoinen, koska voimme usein estimoida O(g(n)), ja siten tietää, alkaako funktio maksaa erittäin kalliiksi syötteen kasvaessa. Se on esimerkiksi uti