funksjonsrangering

Funksjonsrangering er en måte å ordne funksjoner etter et gitt kriterium, vanligvis etter hvordan de vokser når argumentet blir stort. Innen matematikk og informatikk brukes denne rangeringen spesielt for å sammenligne funksjoner med hensyn til vekst eller kompleksitet.

Den vanligste måten å rangere funksjoner på er ved hjelp av størrelsesnotasjoner som Big-O (O-notation), liten-o (o-notation) og Theta (Θ). For to funksjoner f og g definert for store verdier av n, sier man for eksempel at f(n) = O(g(n)) hvis det finnes en konstant c og et tall N slik at for alle n ≥ N, |f(n)| ≤ c|g(n)|. Man sier også at f(n) = Θ(g(n)) hvis f(n) og g(n) vokser med samme hastighet innen faktorer, og at f(n) = o(g(n)) hvis f er strikt mindre vokser enn g(n).

Eksempler: La f(n) = 3n^2 + 2n og g(n) = n log n. Da er f(n) Θ(n^2), og g(n) = o(n^2). Dermed vokser g langsomt sammenlignet med f. Et annet eksempel: 2^n vokser raskere enn enhver polynomisk funksjon n^k, så n^k = o(2^n).

Bruksområder inkluderer rangering av tidskostnader for algoritmer, analyser av numeriske metoder og generell sammenligning av funksjonskompleksitet. Rangering er ofte en asymptotisk betraktning og gir bare et bilde for store n; små forskjeller i konstantledd kan gjøre at én funksjon virker bedre enn en annen for praktiske inngangsverdier. Rangering kan også være delvis eller en preorden, siden det ikke alltid er mulig å sammenligne alle par av funksjoner under et felles kriterium.