big-oAan de slag met big-o


Opmerkingen

Deze sectie geeft een overzicht van wat big-o is en waarom een ontwikkelaar het misschien wil gebruiken.

Het moet ook alle grote onderwerpen binnen big-o vermelden en een link naar de gerelateerde onderwerpen bevatten. Omdat de documentatie voor big-o nieuw is, moet u mogelijk eerste versies van die gerelateerde onderwerpen maken.

Big-O berekenen voor uw code

Een manier om de Big-O-waarde van een door u geschreven procedure te berekenen, is om te bepalen welke coderegel in uw functie het vaakst wordt uitgevoerd, gezien uw invoergrootte n . Zodra je dat aantal hebt, verwijder je alle behalve de snelstgroeiende termen en raak je de coëfficiënten kwijt - dat is de Big-O-notatie van je functie.

In deze functie wordt elke regel bijvoorbeeld precies één keer uitgevoerd, en gedurende dezelfde tijd, ongeacht hoe groot a is:

int first(int[] a){
   printf("Returning the first element of a");
   return a[0];
}
 

De functie zelf kan 1 milliseconde ((1 ms) * n 0 ) of 100 milliseconden ((100 ms) * n 0 ) duren - de exacte waarde hangt af van de kracht van de betreffende computer en waarnaar printf() afdrukt. Maar omdat die factoren niet veranderen met de grootte van a , doen ze er niet toe voor Big-O-berekeningen - het zijn constante coëfficiënten, die we verwijderen. Daarom heeft deze functie een Big-O-waarde van O (1) .

In deze functie wordt regel 3 ( sum += a[i]; ) één keer uitgevoerd voor elk element in a , in totaal a.length (of n ) keer:

int sum(int[] a){
   int sum = 0;
   for (int i = 0; i < a.length; i++){
        sum += a[i];
   }
   return sum;
}
 

De statements i++ en i < a.length lopen ook allemaal n keer - we hadden die regels kunnen kiezen, maar dat hoeft niet. Ook int sum = 0; , int i = 0 en return sum; elke keer één keer, dat is minder dan n keer - we negeren die regels. Het maakt niet uit hoe lang sum += a[i] nodig heeft om te draaien - dat is een coëfficiënt die afhankelijk is van de kracht van de computer - dus verwijderen we die coëfficiënt. Daarom is deze functie O (n) .

Als er meerdere codepaden zijn, wordt big-O meestal berekend vanuit het slechtste geval. Bijvoorbeeld, hoewel deze functie misschien onmiddellijk kan afsluiten, ongeacht hoe groot a is (als a[0] 0 ), bestaat er nog steeds een geval waardoor regel 6 a.length keer wordt uitgevoerd, dus is het nog steeds O (n):

int product(int[] a){
    int product = 0;
    for (int i = 0; i < a.length; i++){
        if (a[i] == 0)
            return 0;
        else 
            product *= a[i];
    }
    return product;
}
 

Wat is Big-O-notatie?

Big-O-notatie is een notatie die wordt gebruikt om te praten over de groeipercentages op lange termijn van functies. Het wordt vaak gebruikt bij de analyse van algoritmen om te praten over de looptijd van een algoritme of gerelateerde concepten zoals ruimtecomplexiteit.

In algemeen gebruik wordt big-O-notatie gebruikt om te praten over hoe de looptijd van een algoritme wordt geschaald als een grootte van de invoer. We zouden bijvoorbeeld zeggen dat selectie sorteren een runtime heeft van O (n 2 ) omdat de runtime kwadratisch groeit als een functie van de grootte van de te sorteren array. Dat wil zeggen, als u de grootte van de invoer verdubbelt, zou de runtime van selectiesortering ruwweg moeten verdubbelen. Bij het gebruik van big-O-notatie is het gebruikelijk om coëfficiënten te laten vallen en termen van lagere orde te negeren. Hoewel het technisch gezien bijvoorbeeld niet verkeerd is om te zeggen dat binair zoeken op tijd O (2 log 2 n + 17) wordt uitgevoerd, wordt het als een slechte stijl beschouwd en is het beter om te schrijven dat binair zoeken op tijd O (log n) wordt uitgevoerd.

Formeel wordt big-O-notatie gebruikt om het langetermijngedrag van een functie te kwantificeren. We zeggen dat f (n) = O (g) (soms aangeduid als f (n) ∈ O (g (n)) in sommige bronnen) als er vaste constanten c en n 0 zijn zodat f (n) ≤ c · g (n) voor alle n ≥ n 0 . Deze formele definitie verklaart waarom we niet geïnteresseerd zijn in termen van lage orde (ze kunnen worden onderverdeeld door c groter en toenemend n 0 te maken ) en constante factoren (de term c absorbeert ze). Deze formele definitie wordt vaak gebruikt in de rigoureuze analyse van algoritmen, maar wordt zelden informeel gebruikt.