Computerwetenschappen problemen vaak gepaard met meer dan een oplossing , en elke oplossing wordt bereikt door het volgen van een set van regels , ook wel bekend als een algoritme . Big O notatie een werkwijze beschrijven van de efficiëntie van een algoritme - met andere woorden , de tijd die een algoritme uit te voeren als een functie van de grootte van de input van de algoritme . Achtergrond
Big O notatie - ook wel bekend als Landau 's symbool , na de Duitse Joodse wiskundige , Edmund Landau - beschrijft de groei van een functie , ook wel bekend als de ' orde', vandaar de hoofdletter " O " Big O notatie is bedoeld om de uitvoering van een algoritme zelf meten , in plaats van de hardware waarop het algoritme wordt uitgevoerd . Een stukje hardware kan sneller of langzamer dan de andere door een constante factor te zijn , zijn dus alle constante factoren van Big O notatie verwijderd .
Constant Duurtijd
Een algoritme die altijd duurt ongeveer dezelfde tijd te lopen , ongeacht de grootte van de input , wordt gezegd dat het " constant " looptijd hebben . In Big O notatie , wordt dit type algoritme bekend als een "beslissing 1 " algoritme en wordt aangeduid met O (1 ) . Voorbeelden van O ( 1 ) algoritmen bevatten duwen of popping gegevens van en naar een programmering stapel , en het ophalen van een data item uit een array als je de positie weet . Deze algoritmen slechts een bepaald aantal stappen , ongeacht hoe groot de ingang wordt uitgevoerd .
Lineaire Duurtijd
Een algoritme waarvan de looptijd stijgt proportioneel , of lineair , met de omvang van haar inbreng wordt gezegd dat " lineair " running tijd te hebben . In Big O notatie , wordt dit type algoritme bekend als een "orde n" algoritme en wordt aangeduid met O ( n ) , wat aangeeft dat de tijd die het algoritme lineair toeneemt uitgevoerd als het aantal gegevens , " n , " verhoogt . Een eenvoudig voorbeeld van een O ( n ) algoritme is een algoritme dat het totaal van een lijst getallen berekent , een aanvulling vereist voor elk element in de lijst , zodat het aantal toevoegingen is gelijk aan het aantal elementen < br . >
Quadratic Duurtijd
een algoritme waarvan de looptijd stijgt met een factor n ^ 2 wanneer de grootte van haar inbreng stijgt met een factor " n" wordt gezegd dat het hebben " kwadratisch " running tijd . In Big O notatie , wordt dit type algoritme bekend als een orde n ^ 2 algoritme , of gewoon een kwadratische algoritme , en wordt aangeduid met O ( n ^ 2 ) . Voorbeelden van O ( n ^ 2 ) algoritmen omvatten sorteeralgoritmes , zoals insertion sort en bubble sort , waarbij een verdubbeling van de omvang van de invoer verviervoudigt de looptijd .
|
