datavitenskap problemer ofte involvere mer enn én løsning , og hver løsning er nådd ved å følge et sett med regler , også kjent som en algoritme . Store o notasjon gir en metode for å beskrive effektiviteten av en algoritme - med andre ord , den tid det tar for en algoritme for å drives som en funksjon av størrelsen på den inngang til den algoritmen. Bakgrunn

Big O notasjon - også kjent som Landau symbol , etter den tyske jødiske matematikeren Edmund Landau - beskriver veksten av en funksjon , også kjent som sin " orden", derav stor bokstav " O." Big O notasjon er ment for å måle ytelsen til en algoritme i seg selv , snarere enn maskinvaren som algoritmen kjøres. Ett stykke maskinvare kan være raskere eller saktere enn en annen med en konstant faktor , så alle konstante faktorer fjernet fra Big O notasjon .
Konstant spilletid

En algoritme som alltid tar omtrent samme tid til å kjøre, uavhengig av størrelsen av input , sies å ha " konstant" kjøretid. I store o notasjon, blir denne type algoritme kjent som en "bestille en " algoritmen og er betegnet med O ( 1). Eksempler på O ( 1 ) algoritmer inkluderer skyve eller spratt data til og fra et programmeringsspråk stack, og hente en enkelt data element fra en matrise når du vet sin posisjon . Disse algoritmene bare utføre et visst antall skritt , uansett hvor stor den inngangen blir .
Linear spilletid

En algoritme som kjører øker proporsjonalt , eller lineær måte , er med størrelsen på sitt innspill sies å ha " lineære " kjøretid. I store o notasjon, blir denne type algoritme kjent som en " i n " algoritmen og er betegnet med O (n ) , som indikerer at den tid det tar for algoritmen å løpe øker lineært når antallet dataelementer "n , "øker . Et enkelt eksempel på en O (n) algoritmen er en algoritme som beregner summen av en liste med tall, ett tillegg kreves for hvert element i listen, slik at den del tillegg er det samme som antall elementer

Quadratic spilletid

en algoritme som kjører øker med en faktor på n ^ 2 når størrelsen på sine innsatsfaktorer øker med en faktor på " n" sies å har " kvadratisk " kjøretid. I Big O notasjon , er denne type algoritme kjent som en ordre n ^ 2 algoritme , eller rett og slett en kvadratisk algoritme , og er merket med O ( n ^ 2 ) . Eksempler på O ( n ^ 2 ) algoritmer inkluderer sortering algoritmer , for eksempel innsetting sortere og boble sortere, der doble størrelsen av input firedobler kjøretid.