Wat is Big-O-notatie?

Heeft u zich ooit afgevraagd waarom het zo lang duurde voordat een programma dat u schreef, werd uitgevoerd? Misschien wilt u weten of u uw code efficiënter kunt maken. Begrijpen hoe code-runs uw code naar een hoger niveau kunnen tillen. Big-O-notatie is een handig hulpmiddel om te berekenen hoe efficiënt uw code werkelijk is.

Wat is de Big-O-notatie?

Big-O-notatie geeft u een manier om te berekenen hoe lang het duurt om uw code uit te voeren. U kunt fysiek bepalen hoe lang het duurt voordat uw code wordt uitgevoerd, maar met die methode is het moeilijk om kleine tijdsverschillen op te vangen. De tijd die nodig is tussen het uitvoeren van 20 tot 50 regels code is bijvoorbeeld erg klein. In een groot programma kunnen die inefficiënties echter oplopen.

Big-O-notatie telt hoeveel stappen een algoritme moet uitvoeren om de efficiëntie te meten. Het op deze manier benaderen van uw code kan zeer effectief zijn als u uw code moet afstemmen om de efficiëntie te vergroten. Met de Big-O-notatie kunt u verschillende algoritmen meten aan de hand van het aantal stappen dat nodig is om uit te voeren en de efficiëntie van de algoritmen objectief vergelijken.

Hoe bereken je de Big-O-notatie

Laten we eens kijken naar twee functies die tellen hoeveel individuele sokken er in een la zitten. Elke functie neemt het aantal paar sokken en retourneert het aantal individuele sokken. De code is geschreven in Python, maar dat heeft geen invloed op hoe we het aantal stappen zouden tellen.

Algoritme 1:

def sockCounter (numberOfPairs):
individualSocks = 0
voor x in bereik (numberOfPairs):
individualSocks = individualSocks + 2
retourneer individualSocks

Algoritme 2:

def sockCounter (numberOfPairs):
retour nummer van paren * 2

Dit is een dom voorbeeld, en je zou gemakkelijk moeten kunnen zien welk algoritme efficiënter is. Maar laten we om te oefenen ze allemaal doornemen.

VERWANT: Wat is een functie bij programmeren?

Wat is een functie bij programmeren?

Als u leert hoe u uw eigen code moet programmeren, moet u weten wat de functies zijn.

Algoritme 1 heeft veel stappen:

1. Het kent een waarde van nul toe aan de variabele individualSocks.
2. Het kent een waarde van één toe aan de variabele i.
3. Het vergelijkt de waarde van i met numberOfPairs.
4. Het voegt er twee toe aan individualSocks.
5. Het kent zichzelf de verhoogde waarde van individualSocks toe.
6. Het verhoogt i met één.
7. Vervolgens doorloopt het stap 3 tot en met 6 even vaak als (indiviualSocks - 1).

Het aantal stappen dat we moeten doorlopen voor algoritme één kan worden uitgedrukt als:

4n + 2

Er zijn vier stappen die we n keer moeten doorlopen. In dit geval zou n gelijk zijn aan de waarde van numberOfPairs. Er zijn ook 2 stappen die één keer worden voltooid.

Ter vergelijking: algoritme 2 heeft slechts één stap. De waarde van numberOfPairs wordt vermenigvuldigd met twee. We zouden dat uitdrukken als:

1

Als het nog niet duidelijk was, kunnen we nu gemakkelijk zien dat algoritme 2 een stuk efficiënter is.

Big-O-analyse

Als u geïnteresseerd bent in de Big-O-notatie van een algoritme, bent u over het algemeen meer geïnteresseerd in de algehele efficiëntie en minder in de fijnkorrelige analyse van het aantal stappen. Om de notatie te vereenvoudigen, kunnen we alleen de grootte van de efficiëntie aangeven.

In de bovenstaande voorbeelden zou algoritme 2 als één worden uitgedrukt:

O (1)

Maar algoritme 1 zou worden vereenvoudigd als:

Aan)

Deze snelle momentopname vertelt ons hoe de efficiëntie van algoritme één is gekoppeld aan de waarde van n. Hoe groter het getal, hoe meer stappen het algoritme moet doorlopen.

Lineaire code

Omdat we de waarde van n niet kennen, is het handiger om na te denken over de invloed van de waarde van n op de hoeveelheid code die moet worden uitgevoerd. In algoritme 1 kunnen we zeggen dat de relatie lineair is. Als u het aantal stappen vs. de waarde van n krijg je een rechte lijn die omhoog gaat.

Kwadratische code

Niet alle relaties zijn zo eenvoudig als het lineaire voorbeeld. Stel dat u een 2D-array heeft en u wilt naar een waarde in de array zoeken. U kunt een algoritme als volgt maken:

def searchForValue (targetValue, arraySearched):
foundTarget = False
voor x in array Gezocht:
voor y in x:
if (y == targetValue):
foundTarget = Waar
return foundTarget

In dit voorbeeld is het aantal stappen afhankelijk van het aantal arrays in arraySearched en het aantal waarden in elke array. Het vereenvoudigde aantal stappen zou dus n * n of n² zijn.

Deze relatie is een kwadratische relatie, wat betekent dat het aantal stappen in ons algoritme exponentieel toeneemt met n. In de Big-O-notatie zou je het schrijven als:

O (n²)

VERWANT: Handige tools om CSS-bestanden te controleren, op te schonen en te optimaliseren

Logaritmische code

Hoewel er veel andere relaties zijn, is de laatste relatie die we zullen bekijken logaritmische relaties. Om je geheugen op te frissen, is de log van een getal de exponentwaarde die nodig is om een ​​getal te bereiken met een gegeven basis. Bijvoorbeeld:

logboek 2 (8) = 3

De log is gelijk aan drie, want als onze basis 2 was, zouden we een exponentwaarde van 3 nodig hebben om bij het getal 8 te komen.

De relatie van een logaritmische functie is dus het tegenovergestelde van een exponentiële relatie. Naarmate n toeneemt, zijn er minder nieuwe stappen nodig om het algoritme uit te voeren.

Op het eerste gezicht lijkt dit contra-intuïtief. Hoe kunnen de stappen van een algoritme langzamer groeien dan n? Een goed voorbeeld hiervan zijn binaire zoekopdrachten. Laten we eens kijken naar een algoritme om te zoeken naar een getal in een reeks unieke waarden.

• We beginnen met een array om te zoeken in de volgorde van klein naar groot.
• Vervolgens zullen we de waarde in het midden van de array controleren.
• Als uw nummer hoger is, zullen we de lagere nummers uitsluiten in onze zoekopdracht en als het aantal lager was, zullen we de hogere nummers uitsluiten.
• Nu kijken we naar het middelste nummer van de resterende nummers.
• Nogmaals, we zullen de helft van de getallen uitsluiten op basis van of onze doelwaarde hoger of lager is dan de middelste waarde.
• We zullen dit proces voortzetten totdat we ons doel hebben gevonden, of vaststellen dat het niet in de lijst staat.

Zoals u kunt zien, aangezien binaire zoekopdrachten de helft van de mogelijke waarden elimineren, naarmate n groter wordt, wordt het effect op het aantal keren dat we de array controleren nauwelijks beïnvloed. Om dit in Big-O-notatie uit te drukken, zouden we schrijven:

O (logboek (n))

Het belang van Big-O-notatie

Big-O nation biedt u een snelle en gemakkelijke manier om te communiceren hoe efficiënt een algoritme is. Dit maakt het gemakkelijker om tussen verschillende algoritmen te kiezen. Dit kan met name handig zijn als u een algoritme uit een bibliotheek gebruikt en niet per se weet hoe de code eruitziet.

Wanneer u voor het eerst leert coderen, begint u met lineaire functies. Zoals je kunt zien in de bovenstaande grafiek, kom je een heel eind. Maar naarmate u meer ervaring krijgt en complexere code begint te bouwen, begint efficiëntie een probleem te worden. Als u begrijpt hoe u de efficiëntie van uw code kunt kwantificeren, krijgt u de tools die u nodig hebt om deze af te stemmen op efficiëntie en de voor- en nadelen van algoritmen af ​​te wegen.

10 meest voorkomende programmeer- en codeerfouten

Coderingsfouten kunnen tot zoveel problemen leiden. Deze tips helpen u programmeerfouten te voorkomen en uw code zinvol te houden.

Over de auteur