Datalogi problemer ofte involverer mere end én løsning , og hver løsning er nået ved at følge et sæt regler , også kendt som en algoritme. Big O notation tilvejebringer en fremgangsmåde til at beskrive effektiviteten af ​​en algoritme - med andre ord , den tid det tager for en algoritme til at køre som en funktion af størrelsen af input til denne algoritme . Baggrund

Big O notation - også kendt som Landau symbol , efter den tyske jødiske matematiker Edmund Landau - beskriver vækstraten for en funktion , også kendt som dens " orden ", dermed bogstavet "O. " Big O notation er beregnet til at måle effektiviteten af en algoritme selv , snarere end den hardware , som algoritmen køres . Et stykke hardware kan være hurtigere eller langsommere end en anden med en konstant faktor , så alle konstante faktorer fjernet fra Big O notation.
Konstant spilletid

En algoritme der altid tager omtrent samme tid at løbe , uanset størrelsen af input , siges at have " konstant " køretid . I Big O notation , er denne form for algoritme kaldet en "ordre 1" algoritme og er angivet ved O ( 1). Eksempler på O (1 ) algoritmer omfatter skubbe eller popping data til og fra et programmeringssprog stack , og hente en enkelt data element fra et array , når du kender dens position. Disse algoritmer kun udføre et bestemt antal skridt , uanset hvor stor input bliver .
Linear spilletid

En algoritme , hvis køretid stiger proportionalt eller lineært , er med størrelsen af ​​sit input siges at have " lineære" kører tid. I Big O notation er denne type algoritme er kendt som en " orden n " algoritme og betegnes med O ( n ) , hvilket indikerer, at den tid, det tager for algoritmen at køre stiger lineært som antallet af dataelementer , " n " stiger . Et simpelt eksempel på en O ( n ) algoritme er en algoritme , der beregner summen af ​​en liste over numre , en tilføjelse er påkrævet for hvert element i listen , så antallet af tilsætninger er det samme som antallet af elementer < br . >
Kvadratisk spilletid

en algoritme , hvis kører forøges med en faktor n ^ 2 , når størrelsen af dens input stiger med en faktor på " n" siges at have " kvadratisk " kører tid. I Big O notation er denne type algoritme er kendt som en orden n ^ 2 algoritme , eller blot en kvadratisk algoritme , og er betegnet med O (n ^ 2 ) . Eksempler på O ( n ^ 2 ) algoritmer omfatter sortering algoritmer , såsom indsættelse sortere og boble sortere, hvor en fordobling af størrelsen af input firedobler køretiden .