suuruusluokka

Suuruusluokka on käsite, jota käytetään kuvaamaan suureen koon tai kasvun luokkaa ilman tarkkaa arvoa. Se auttaa vertailemaan esimerkiksi algoritmien aikavaativuutta, suuria lukumääriä tai fysiikan mittakaavoja siten, että huomio kiinnittyy vain kasvun nopeuteen ja johtavan termin vaikutukseen.

Kaksi funktiota f(n) ja g(n) sanotaan kuuluvan samaan suuruusluokkaan, jos niiden suhde lähestyy vakioarvoa n kasvaessa kohti rajatonta tai kuuluu rajoihin. Yleisiä merkintöjä ovat O-merkintä (suurusluokka), Θ-merkintä (tarkka suurusluokka) ja o-merkintä (pikku-o). Esimerkiksi 3n ja n kuuluvat samaan suuruusluokkaan O(n) ja Θ(n). Saman suuruusluokan omaavia ovat myös 2n^2 ja n^2, kun taas 2^n kasvaa nopeammin kuin mikään polynominen, joten se ei ole samaa suuruusluokkaa polynomien kanssa.

Käytännössä suuruusluokkia käytetään erityisesti algoritmien aikakompleksisuuden analyysissä: voidaan sanoa, että algoritmin aikakaava on esimerkiksi O(n), O(n log n) tai Θ(n^2), jolloin pienemmät yksityiskohdat arvoista jätetään pois. Suuruusluokat auttavat myös asettamaan arviot mittakaavaan suhteessa toisiin suureisiin ja helpottavat vertailua eri tilanteiden välillä.

Huomioita: suuruusluokka kuvaa kasvun luonnetta eikä tarkkaa arvoa; se on väline, jolla voidaan arvioida, kuinka nopeasti jokin suure kasvaa suurissa syöteko’oissa tai pitkällä aikavälillä. Se ei määrity yksittäistä tarkkaa lukua vaan antaa yleisen käsityksen suhteellisesta koosta ja kehityksestä.