Forklaring av Big O-notasjon
Datateknikk problemer involverer ofte mer enn en løsning, og hver oppløsning blir oppnådd ved å følge et sett med regler, også kjent som en algoritme. Big O notasjon tilveiebringer en metode for å beskrive effektiviteten av en algoritme - med andre ord, den tid det tar for en algoritme for å kjøre som en funksjon av størrelsen av inngangs 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 beregnet til å måle ytelsen til en algoritme i seg selv, snarere enn maskinvaren som algoritmen kjøres. Ett stykke av maskinvare kan være raskere eller langsommere enn en annen med en konstant faktor, slik at alle konstante faktorer er fjernet fra Big O notasjon.
Konstant spilletid
En algoritme som tar alltid omtrent samme tid å kjøre, uavhengig av størrelsen av inngangs, sies å ha "konstant" driftstid. I Big O notasjon, blir denne type algoritme kjent som en "ordre 1" algoritme, og er betegnet med O (1). Eksempler på O (1) algoritmer inkluderer skyve eller dukker data til og fra en programmering stabelen, og hente en enkelt dataelement fra en rekke når du vet sin posisjon. Disse algoritmene bare utføre et visst antall trinn, uansett hvor stor inngangs blir.
Lineær spilletid
En algoritme som kjører tiden øker proporsjonalt, eller i lineær måte, med størrelsen på inngangs sies å ha "lineær" kjøretid. I Big O notasjon, blir denne type algoritme kjent som en "ordre n" algoritme, og er betegnet med O (n), noe som indikerer at tiden det tar for algoritmen å løpe øker lineært når antall dataelementer, "n, "øker. Et enkelt eksempel på en O (n) algoritme er en algoritme som beregner summen av en liste med tall; en tilsetning er nødvendig for hvert element i listen, slik at antallet av tilleggene er det samme som antallet elementer.
Kvadratisk spilletid
En algoritme som løper tiden øker med en faktor på n ^ 2 når størrelsen på sin inngang øker med en faktor på "n" er sagt å ha "kvadratisk" driftstid. I Big O notasjon, blir denne type algoritme kjent som en orden n ^ 2 algoritme, eller ganske enkelt en kvadratisk algoritme, og er betegnet med O (n ^ 2). Eksempler på O (n ^ 2) algoritmer inkluderer sortering algoritmer, som for eksempel innsetting sortere og boblesortering, der doble størrelsen på inngangs firemannsrom løpende tid.