Ordo | ett sätt att jämföra tillväxttakten för olika funktioner

Inom matematik och datavetenskap är Big O-notationen ett sätt att jämföra tillväxttakten för olika funktioner. Det används ofta för att jämföra effektiviteten hos olika algoritmer, vilket görs genom att beräkna hur mycket minne som behövs och hur lång tid det tar att slutföra.

Big O-notationen används ofta för att identifiera hur komplext ett problem är, även kallat problemets komplexitetsklass. Matematikern Paul Bachmann (1837-1920) var den förste som använde denna notation i den andra upplagan av sin bok "Analytische Zahlentheorie" år 1896. Edmund Landau (1877-1938) gjorde notationen populär. När man talar om Landau-symboler hänvisar man därför till denna notation.

Big O-notationen är uppkallad efter termen "order of the function" (funktionens ordning), som avser funktionernas tillväxt. Big O-notation används för att hitta den övre gränsen (högsta möjliga belopp) för funktionens tillväxttakt, vilket innebär att den räknar ut den längsta tid det tar att omvandla inmatningen till utmatningen. Detta innebär att en algoritm kan grupperas efter hur lång tid den kan ta i ett värsta fall, där den längsta vägen tas varje gång.

Mer specifikt, givet två positiva funktioner f ( x ) {\displaystyle f(x)} f(x) och g ( x ) {\displaystyle g(x)} $g(x)$ , säger vi att f {\displaystyle f} är i det stora O av g {\displaystyle g} (skrivet f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ) om för tillräckligt stort x {\displaystyle x} , f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ för en viss konstant k {\displaystyle k} .

Big O är ett uttryck som visar hur effektiv en algoritm är utan att programmet behöver köras på en dator. Detta är också användbart på grund av att olika datorer kan ha olika hårdvara och därför behöver olika mycket tid för att slutföra det. Eftersom Big O alltid utgår från det värsta fallet kan den visa ett konsekvent mått på hastighet: oavsett hårdvara kommer O ( 1 ) {\displaystyle O(1)} $O(1)$ alltid att slutföras snabbare än O ( n ! ) {\displaystyle O(n!)} $O(n!)$ eftersom de har olika effektivitetsnivåer.

Exempel

I följande exempel används kod som är skriven i Python. Observera att detta inte är en fullständig lista över Big O-typer.

Konstant

O ( 1 ) {\displaystyle O(1)} $O(1)$ tar alltid lika lång tid oavsett vad som används. Ta till exempel en funktion som tar emot ett heltal (kallat x) och returnerar dubbelt så mycket som dess värde:

def double(x): return x * 2 #Returnerar värdet av x gånger 2

Efter att ha tagit emot inmatningen tar denna funktion alltid ett steg för att returnera ett utdata. Det är konstant eftersom det alltid tar lika lång tid, så det är O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linjär

O ( n ) {\displaystyle O(n)} $O(n)$ ökar med storleken på inmatningen, som representeras av n {\displaystyle n} . Till exempel för följande funktion som accepterar n och returnerar alla tal från 1 till n:

def count(n): i = 1 #Skapa en räknare kallad "i" med värdet 1 while i <= n: # Medan i är mindre än eller lika med n print(i) #Skriv ut värdet av i i i = i + 1 #Redefiniera i som "värdet av i + 1"

Om vi skulle ange värdet 5 skulle detta ge ut $1,2,3,4,5$ Det krävs 5 slingor för att slutföra. På samma sätt, om vi anger 100, skulle det ge ut $1,2,3...98,99,100$ , vilket kräver 100 slingor för att slutföra. Om inmatningen är n {\displaystyle n} är algoritmens körtid exakt n {\displaystyle n} slingor varje gång, och därför är den O ( n ) {\displaystyle O(n)} $O(n)$ .

Factorial

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ ökar i faktoriella mängder, vilket innebär att den tid som krävs ökar kraftigt med mängden indata. Säg till exempel att vi vill besöka fem städer runt om i världen och vill se alla möjliga ordningar (permutationer). En algoritm som vi skulle kunna skriva med hjälp av Pythons itertools-bibliotek är följande:

import itertools #Import itertools-biblioteket cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rom'] #En array med våra valda städer def permutations(cities): #Vi tar en matris av städer som indata: for i in itertools.permutations(cities): #För varje permutation av våra objekt (tilldelas variabeln "i") print(i) #Output i

Algoritmen beräknar varje unik permutation av våra städer och ger sedan ut den. Exempel på utdata är följande:

("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") ("Rom", "Amsterdam", "Berlin", "Paris", "London")

Här är vår ingångslista 5 objekt, och för varje val minskar de återstående alternativen med 1. Med andra ord väljer våra 5 ingångar $5\times 4\times 3\times 2\times 1$ objekt (eller 5 ! {\displaystyle 5!} $5!$ ). Om vår indata är n {\displaystyle n} städer lång, är antalet utdata n ! {\displaystyle n!} $n!$ ; i allmänhet, om vi antar att vi går igenom varje permutation, krävs det O ( n ! ) {\displaystyle O(n!)} $O(n!)$ slingor för att slutföra den.

Little-o notation

Ett begrepp som är besläktat med Big-O-notation är Little-O-notation. Big-O används för att säga att en funktion inte växer snabbare än en annan funktion, medan little-o används för att säga att en funktion växer långsammare än en annan funktion. Om två funktioner växer i samma takt kan big-O användas, men inte little-o. Skillnaden mellan big-O och little-o liknar skillnaden mellan ≤ {\displaystyle \leq } $\leq$ och < {\displaystyle <} $<$ .

Om f ( x ) {\displaystyle f(x)} växer långsammare än g ( x ) {\displaystyle g(x)} $g(x)$ , så är $f(x)\in O(g(x))$ och $f(x)\in o(g(x))$ .
Om f ( x ) {\displaystyle f(x)} växer i samma takt som g ( x ) {\displaystyle g(x)} $g(x)$ , så är $f(x)\in O(g(x))$ men f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Om f ( x ) {\displaystyle f(x)} växer snabbare än g ( x ) {\displaystyle g(x)} $g(x)$ , då f ( x ) ∉ $f(x)\not \in O(g(x))$ och f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Frågor och svar

F: Vad är Big O-notation?

S: Big O-notation är ett sätt att jämföra tillväxttakten för olika funktioner, som ofta används för att jämföra effektiviteten hos olika algoritmer genom att beräkna hur mycket minne och tid det tar att genomföra. Det kan också användas för att identifiera hur komplext ett problem är.

F: Vem var den första som använde denna notation?

S: Matematikern Paul Bachmann (1837-1920) var den första som använde denna notation i sin bok "Analytische Zahlentheorie" 1896.

F: Vad står Big O för?

S: Big O står för "funktionens ordning", vilket avser funktionernas tillväxttakt.

F: Hur används Big O?

S: Big O-notationen används för att hitta en övre gräns (högsta möjliga belopp) för funktionens tillväxthastighet, vilket innebär att man räknar ut den längsta tid det tar att omvandla en inmatning till en utmatning. Detta innebär att algoritmer kan grupperas efter hur lång tid de tar i värsta fall, där den längsta vägen tas varje gång.

F: Vad är Landau-symboler?

S: Landau-symbolerna hänvisar till Big O-notationen, uppkallad efter Edmund Landau (1877-1938) som gjorde denna notation populär.

F: Varför är Big O användbart?

S: Big O gör det möjligt att mäta hastigheten utan att behöva köra program på datorer, eftersom den alltid utgår från värsta tänkbara scenarier, vilket gör den konsekvent oavsett skillnader i hårdvara mellan datorer. Det visar också hur effektiv en algoritm är utan att man behöver köra den på en dator.