Datavetenskap problem innebär ofta mer än en lösning , och varje lösning nås genom att följa en uppsättning regler , även känd som en algoritm . Big O notation tillhandahåller en metod att beskriva effektiviteten hos en algoritm - med andra ord , den tid det tar för en algoritm för att köras som en funktion av storleken för insignalen till samma algoritm. Bakgrund
Big O notation - även känd som Landau s symbol , efter den tyska judiska matematiker , Edmund Landau - beskriver tillväxten av en funktion , även känd som sin " ordning ", därav bokstaven " O. " Big O notation är avsedd att mäta prestanda hos en algoritm i sig , snarare än hårdvara som algoritmen körs . En del av maskinvaran kan vara snabbare eller långsammare än en annan med en konstant faktor , så alla konstanta faktorer avlägsnas från Big O notation . En algoritm
Constant tidsåtgång
som alltid tar ungefär samma tid att köra , oavsett storleken av insignalen , sägs ha " konstant " gångtid . I Big O notation , är denna typ av algoritm som kallas en " order 1 " algoritm och betecknas med O ( 1 ) . Exempel på O ( 1 ) algoritmer inkluderar skjuta eller poppar data till och från en programperiod stack , och hämta en enskild datapost från en array när du vet sin position . Dessa algoritmer utför endast ett visst antal steg , oavsett hur stora ingången blir .
Linear tidsåtgång
En algoritm vars gångtid ökar proportionellt , eller linjärt , är med storleken på dess ingång sägs ha " linjär " gångtid . I Big O notation , är denna typ av algoritm som kallas en " ordning n " algoritm och betecknas med O ( n ) , vilket indikerar att den tid det tar för algoritmen att köra ökar linjärt som antalet dataposter , " n , " ökar . Ett enkelt exempel på en O ( n ) algoritm är en algoritm som beräknar summan av en lista med tal , ett tillägg krävs för varje element i listan , så att antalet tillsatser är detsamma som antalet element
Kvadratisk tidsåtgång
en algoritm vars gångtid ökar med en faktor n ^ 2 när storleken på sina insatsvaror ökar med en faktor " n " sägs ha " kvadratisk " gångtid . I Big O notation , är denna typ av algoritm som kallas en ordning n ^ 2 algoritm , eller helt enkelt en kvadratisk algoritm , och betecknas med O ( n ^ 2 ) . Exempel på O (n ^ 2 ) algoritmer inkluderar sortering algoritmer, såsom införande sort och bubble sort , där en fördubbling av storleken av den ingående fyrdubblar gångtid .
