Grote-O-notatie | een manier om groeisnelheden van verschillende functies te vergelijken

In de wiskunde en informatica is de Big O-notatie een manier om de groeisnelheid van verschillende functies te vergelijken. Het wordt vaak gebruikt om de efficiëntie van verschillende algoritmen te vergelijken, wat gebeurt door te berekenen hoeveel geheugen er nodig is, en hoeveel tijd het kost om het te voltooien.

De Big O-notatie wordt vaak gebruikt om aan te geven hoe complex een probleem is, ook wel de complexiteitsklasse van het probleem genoemd. De wiskundige Paul Bachmann (1837-1920) was de eerste die deze notatie gebruikte, in de tweede editie van zijn boek "Analytische Zahlentheorie", in 1896. Edmund Landau (1877-1938) maakte de notatie populair. Daarom verwijzen mensen die het hebben over Landau-symbolen naar deze notatie.

De Big O-notatie is genoemd naar de term "orde van de functie", die verwijst naar de groei van functies. De Big O-notatie wordt gebruikt om de bovengrens (de hoogst mogelijke hoeveelheid) van de groeisnelheid van de functie te vinden, wat betekent dat de langste tijd wordt berekend die nodig is om de invoer om te zetten in de uitvoer. Dit betekent dat een algoritme kan worden gegroepeerd aan de hand van hoe lang het kan duren in een worst-case scenario, waarbij telkens de langste weg wordt genomen.

Meer bepaald, gegeven twee positieve functies f ( x ) {displaystyle f(x)} f(x) en g ( x ) {displaystyle g(x)} $g(x)$ , zeggen we dat f {displaystyle f} in de grote O van g {displaystyle g} ligt (geschreven f ∈ O ( g ) {displaystyle f in O(g)} $f\in O(g)$ ) als voor groot genoeg x {displaystyle x} , f ( x ) ≤ k ⋅ $f(x)\leq k\cdot g(x)$ voor een constante k {displaystyle k} .

Big O is een uitdrukking die een worst-case scenario run-time vindt, die laat zien hoe efficiënt een algoritme is zonder dat het programma op een computer moet worden uitgevoerd. Dit is ook nuttig omdat verschillende computers verschillende hardware kunnen hebben, en daarom verschillende hoeveelheden tijd nodig hebben om het programma te voltooien. Aangezien Big O altijd uitgaat van het slechtste geval, kan het een consistente snelheidsmeting weergeven: ongeacht de hardware, zal O ( 1 ) {displaystyle O(1)} $O(1)$ altijd sneller klaar zijn dan O ( n ! ) {displaystyle O(n!)}. $O(n!)$ omdat ze verschillende efficiëntieniveaus hebben.

Voorbeelden

De volgende voorbeelden gebruiken allemaal code geschreven in Python. Merk op dat dit geen volledige lijst van Big O-types is.

Constant

O ( 1 ) {O(1)} $O(1)$ duurt altijd even lang, ongeacht de invoer. Neem bijvoorbeeld een functie die een geheel getal accepteert (genaamd x) en een dubbele waarde teruggeeft:

def double(x): return x * 2 #Return de waarde van x maal 2

Na het accepteren van de invoer zal deze functie altijd één stap nemen om een uitvoer te retourneren. Dit is constant omdat het altijd even lang duurt, dus het is O ( 1 ) {O(1)} $O(1)$ .

Lineair

O ( n ) {\displaystyle O(n)} $O(n)$ neemt toe met de grootte van de invoer, voorgesteld door n {\displaystyle n} . Bijvoorbeeld voor de volgende functie die n accepteert en elk getal van 1 tot n teruggeeft:

def count(n): i = 1 #Maak een teller genaamd "i" met een waarde van 1 terwijl i <= n: #While i is less-than or equal to n print(i) #Print de waarde van i = i + 1 #Redefine i als "de waarde van i + 1".

Als we de waarde 5 zouden invoeren, dan zou dit opleveren. $1,2,3,4,5$ waarvoor 5 lussen nodig zijn. Evenzo, als we 100 invoeren, dan zou het $1,2,3...98,99,100$ uitvoeren, waarvoor 100 lussen nodig zijn. Indien de invoer n is {playstyle n} dan is de looptijd van het algoritme telkens precies n {displaystyle n} lussen, dus O ( n ) {displaystyle O(n)} $O(n)$ .

Factorieel

O ( n ! ) {O(n!)} $O(n!)$ neemt toe in factorische hoeveelheden, wat betekent dat de tijd die nodig is enorm toeneemt met de invoer. Stel bijvoorbeeld dat wij vijf steden in de wereld willen bezoeken en elke mogelijke ordening (permutatie) willen zien. Een algoritme dat we zouden kunnen schrijven met behulp van de itertools-bibliotheek van Python is als volgt:

import itertools #Import the itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Een array van onze gekozen steden def permutations(cities): #Het nemen van een array van steden als invoer: voor i in itertools.permutations(cities): #Voor elke permutatie van onze items (toegewezen aan variabele "i") print(i) #Invoer i

Dit algoritme zal elke unieke permutatie van onze steden berekenen en vervolgens uitvoeren. Voorbeelden van uitvoer zijn:

('Londen', 'Parijs', 'Berlijn', 'Amsterdam', 'Rome') ('Londen', 'Parijs', 'Berlijn', 'Rome', 'Amsterdam') ('Londen', 'Parijs', 'Amsterdam', 'Berlijn', 'Rome') ... ('Rome', 'Amsterdam', 'Parijs', 'Berlijn', 'Londen', 'Parijs') ('Rome', 'Amsterdam', 'Berlijn', 'Londen', 'Londen')

Hier is onze invoerlijst 5 items lang, en voor elke selectie nemen onze resterende opties af met 1. Met andere woorden, onze 5 inputs kiezen $5\times 4\times 3\times 2\times 1$ items (of 5 ! {\displaystyle 5!} $5!$ ). Als onze invoer n {displaystyle n} steden lang is, dan is het aantal uitgangen n ! { $n!$ ; in het algemeen, ervan uitgaande dat we elke permutatie doorlopen, dan hebben we O ( n ! ) {\displaystyle O(n!)} $O(n!)$ lussen nodig om het te voltooien.

Little-o notatie

Een verwant begrip aan de grote-O-notatie is de kleine-O-notatie. Big-O wordt gebruikt om aan te geven dat een functie niet sneller groeit dan een andere functie, terwijl little-o wordt gebruikt om aan te geven dat een functie langzamer groeit dan een andere functie. Als twee functies even snel groeien, kan big-O worden gebruikt, maar little-o niet. Het verschil tussen big-O en little-o is vergelijkbaar met het verschil tussen ≤ {displaystyle \leq } $\leq$ en < {displaystyle <} $<$ .

Als f ( x ) {displaystyle f(x)} langzamer groeit dan g ( x ) {displaystyle g(x)} $g(x)$ , dan groeit f ( x ) ∈ $f(x)\in O(g(x))$ en f ( x ) ∈ o ( g ( x ) ) { $f(x)\in o(g(x))$ .
Als f ( x ) {displaystyle f(x)} even snel groeit als g ( x ) {displaystyle g(x)} $g(x)$ , dan is f ( x ) ∈ O ( g ( x ) ) {in O(g(x))} $f(x)\in O(g(x))$ maar f ( x ) ∉ $f(x)\not \in o(g(x))$ .
Als f ( x ) {displaystyle f(x)} sneller groeit dan g ( x ) {displaystyle g(x)} $g(x)$ , dan groeit f ( x ) ∉ $f(x)\not \in O(g(x))$ en f ( x ) ∉ $f(x)\not \in o(g(x))$ .

Vragen en antwoorden

V: Wat is de Big O-notatie?

A: De Big O-notatie is een manier om groeisnelheden van verschillende functies te vergelijken, vaak gebruikt om de efficiëntie van verschillende algoritmen te vergelijken door te berekenen hoeveel geheugen en tijd het kost om te voltooien. Het kan ook worden gebruikt om te bepalen hoe complex een probleem is.

V: Wie was de eerste die deze notatie gebruikte?

A: De wiskundige Paul Bachmann (1837-1920) was de eerste die deze notatie gebruikte in zijn boek "Analytische Zahlentheorie" in 1896.

V: Waar staat Big O voor?

A: Big O staat voor "orde van de functie", die verwijst naar de groeisnelheid van functies.

V: Hoe wordt Big O gebruikt?

A: De Big O-notatie wordt gebruikt om een bovengrens (het hoogst mogelijke bedrag) te vinden voor de groeisnelheid van de functie, wat betekent dat de langste tijd wordt berekend die nodig is om van een invoer een uitvoer te maken. Dit betekent dat algoritmen kunnen worden gegroepeerd volgens de tijd die zij in het slechtste geval nodig hebben, waarbij telkens de langste weg wordt genomen.

V: Wat zijn Landau-symbolen?

A: Landau-symbolen verwijzen naar de Big O-notatie, genoemd naar Edmund Landau (1877-1938) die deze notatie populair maakte.

V: Waarom is Big O nuttig?

A: Big O stelt ons in staat snelheid te meten zonder programma's op computers te laten draaien, omdat het altijd uitgaat van worst-case scenario's, waardoor het consistent is ongeacht hardwareverschillen tussen computers. Het laat ook zien hoe efficiënt een algoritme is zonder het daadwerkelijk op een computer uit te voeren.