Big O Notation er en | en måde at sammenligne vækstrater for forskellige funktioner på

I matematik og datalogi er Big O-notationen en måde at sammenligne vækstrater for forskellige funktioner på. Det bruges ofte til at sammenligne effektiviteten af forskellige algoritmer, hvilket gøres ved at beregne, hvor meget hukommelse der er brug for, og hvor lang tid det tager at gennemføre.

Big O-notationen bruges ofte til at identificere, hvor komplekst et problem er, også kendt som problemets kompleksitetsklasse. Matematikeren Paul Bachmann (1837-1920) var den første til at bruge denne notation i anden udgave af sin bog "Analytische Zahlentheorie" i 1896. Edmund Landau (1877-1938) gjorde notationen populær. Når man taler om Landau-symboler, henviser man derfor til denne notation.

Big O-notationen er opkaldt efter udtrykket "funktionens orden", som henviser til funktionernes vækst. Big O notation bruges til at finde den øvre grænse (det højest mulige beløb) for funktionens vækstrate, hvilket betyder, at den beregner den længste tid, det vil tage at omdanne input til output. Det betyder, at en algoritme kan grupperes efter, hvor lang tid den kan tage i et worst-case-scenarie, hvor den længste vej vil blive taget hver gang.

Mere specifikt, givet to positive funktioner f ( x ) {\displaystyle f(x)} f(x) og g ( x ) {\displaystyle g(x)} $g(x)$ , siger vi, at f {\displaystyle f} er i det store O af g {\displaystyle g} (skrevet f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ), hvis for stort nok x {\displaystyle x} , f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ for en vis konstant k {\displaystyle k} .

Big O er et udtryk, der finder den værst tænkelige kørselstid og viser, hvor effektiv en algoritme er uden at skulle køre programmet på en computer. Dette er også nyttigt på grund af det faktum, at forskellige computere kan have forskellig hardware og derfor har brug for forskellig tid til at gennemføre det. Da Big O altid tager udgangspunkt i det værst tænkelige tilfælde, kan den vise en konsekvent måling af hastigheden: Uanset hardwaren vil O ( 1 ) {\displaystyle O(1)} $O(1)$ altid være hurtigere færdig end O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , fordi de har forskellige grader af effektivitet.

Eksempler

I de følgende eksempler anvendes kode skrevet i Python. Bemærk, at dette ikke er en komplet liste over Big O-typer.

Konstant

O ( 1 ) {\displaystyle O(1)} $O(1)$ tager altid lige lang tid uanset input. Tag f.eks. en funktion, der accepterer et heltal (kaldet x) og returnerer det dobbelte af dets værdi:

def double(x): return x * 2 #Returnerer værdien af x gange 2

Efter at have accepteret input vil denne funktion altid tage et skridt for at returnere et output. Det er konstant, fordi det altid vil tage den samme tid, så det er O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineær

O ( n ) {\displaystyle O(n)} $O(n)$ øges i takt med størrelsen af input, repræsenteret ved n {\displaystyle n} . For eksempel for følgende funktion, der accepterer n og returnerer alle tal fra 1 til n:

def count(n): i = 1 #Opret en tæller kaldet "i" med værdien 1 while i <= n: # Mens i er mindre end eller lig med n print(i) #Udskriv værdien af i i i = i + 1 #Redefiner i som "værdien af i + 1"

Hvis vi indtaster værdien 5, ville dette output $1,2,3,4,5$ , hvilket kræver 5 sløjfer for at gennemføre. På samme måde, hvis vi indtaster 100, vil der blive udstedt $1,2,3...98,99,100$ , hvilket kræver 100 sløjfer at gennemføre. Hvis input er n {\displaystyle n} , så er algoritmens løbetid præcis n {\displaystyle n} løkker hver gang, og derfor er den O ( n ) {\displaystyle O(n)} $O(n)$ .

Factorial

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ stiger i faktorielt omfang, hvilket betyder, at den tid, der bruges, stiger voldsomt med input. Lad os f.eks. sige, at vi ønsker at besøge fem byer rundt om i verden og ønsker at se alle mulige rækkefølger (permutationer). En algoritme vi kunne skrive ved hjælp af Pythons itertools-bibliotek er som følger:

import itertools #Import itertools-biblioteket cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rom'] #En array af vores udvalgte byer def permutations(cities): #Tager et array af byer som input: for i in itertools.permutations(cities): #For hver permutation af vores emner (tildelt variablen "i") print(i) #Output i

Denne algoritme beregner hver unik permutation af vores byer og udsender den derefter. Eksempler på output vil omfatte:

("London", "Paris", "Berlin", "Amsterdam", "Rom") ("London", "Paris", "Berlin", "Rom", "Amsterdam") ("London", "Paris", "Amsterdam", "Berlin", "Rom") ... ("Rom", "Amsterdam", "Paris", "Berlin", "London") ("Rom", "Amsterdam", "Berlin", "London", "Paris") ("Rom", "Amsterdam", "Berlin", "London", "Paris", "London") ("Rom", "Amsterdam", "Berlin", "Paris", "London")

Her er vores inputliste på 5 emner, og for hvert valg reduceres de resterende muligheder med 1. Med andre ord vælger vores 5 input $5\times 4\times 3\times 2\times 1$ emner (eller 5 ! {\displaystyle 5!} $5!$ ). Hvis vores input er n {\displaystyle n} byer langt, er antallet af output n ! {\displaystyle n!} $n!$ ; hvis vi generelt antager, at vi gennemgår alle permutationer, vil det kræve O ( n ! ) {\displaystyle O(n!)} $O(n!)$ sløjfer at gennemføre den.

Little-o notation

Et beslægtet begreb til big-O notation er little-o notation. Big-O bruges til at sige, at en funktion ikke vokser hurtigere end en anden funktion, mens little-o bruges til at sige, at en funktion vokser langsommere end en anden funktion. Hvis to funktioner vokser med samme hastighed, kan big-O anvendes, men little-o ikke. Forskellen mellem big-O og little-o svarer til forskellen mellem ≤ {\displaystyle \leq } $\leq$ og < {\displaystyle <} $<$ .

Hvis f ( x ) {\displaystyle f(x)} vokser langsommere end g ( x ) {\displaystyle g(x)} $g(x)$ , så er f ( x ) ∈ $f(x)\in O(g(x))$ og f ( x ) ∈ $f(x)\in o(g(x))$ .
Hvis f ( x ) {\displaystyle f(x)} vokser med samme hastighed som g ( x ) {\displaystyle g(x)} $g(x)$ , så er f ( x ) ∈ $f(x)\in O(g(x))$ men f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Hvis f ( x ) {\displaystyle f(x)} vokser hurtigere end g ( x ) {\displaystyle g(x)} $g(x)$ , så er f ( x ) ∉ $f(x)\not \in O(g(x))$ og f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Spørgsmål og svar

Spørgsmål: Hvad er Big O notation?

A: Big O-notation er en måde at sammenligne vækstrater for forskellige funktioner på, og bruges ofte til at sammenligne effektiviteten af forskellige algoritmer ved at beregne, hvor meget hukommelse og tid det tager at gennemføre. Det kan også bruges til at identificere, hvor komplekst et problem er.

Spørgsmål: Hvem var den første til at bruge denne notation?

Svar: Matematikeren Paul Bachmann (1837-1920) var den første til at bruge denne notation i sin bog "Analytische Zahlentheorie" i 1896.

Spørgsmål: Hvad står Big O for?

A: Big O står for "funktionens orden", som henviser til funktionernes væksthastighed.

Spørgsmål: Hvordan bruges Big O?

A: Big O-notationen bruges til at finde en øvre grænse (det højest mulige beløb) for funktionens vækstrate, hvilket betyder, at den udregner den længste tid, det vil tage at omdanne et input til et output. Det betyder, at algoritmer kan grupperes efter, hvor lang tid de tager i værste tilfælde, hvor den længste vej vil blive taget hver gang.

Spørgsmål: Hvad er Landau-symboler?

Svar: Landau-symboler henviser til Big O-notationen, der er opkaldt efter Edmund Landau (1877-1938), som gjorde denne notation populær.

Spørgsmål: Hvorfor er Big O nyttigt?

Svar: Big O giver os mulighed for at måle hastighed uden at skulle køre programmer på computere, da det altid antager worst-case-scenarier, hvilket gør det konsistent uanset hardwareforskelle mellem computere. Det viser også, hvor effektiv en algoritme er, uden at man behøver at køre den på en computer.