Big O-notatie en algoritmeanalyse met Python-voorbeelden

Introductie

Er zijn meestal meerdere manieren om het probleem op te lossen met behulp van een computerprogramma. Er zijn bijvoorbeeld verschillende manieren om items in een array te sorteren - u kunt gebruiken voeg soort samen, bellen sorteren, invoegsoort, enzovoort. Al deze algoritmen hebben hun eigen voor- en nadelen en het is de taak van de ontwikkelaar om ze af te wegen om het beste algoritme te kunnen kiezen dat in elk geval kan worden gebruikt. Met andere woorden, de belangrijkste vraag is welk algoritme moet worden gebruikt om een ​​specifiek probleem op te lossen wanneer er meerdere oplossingen voor het probleem bestaan.

Algoritme analyse verwijst naar de analyse van de complexiteit van verschillende algoritmen en het vinden van het meest efficiënte algoritme om het probleem op te lossen. Big-O-notatie is een statistische maat die wordt gebruikt om de complexiteit van het algoritme te beschrijven.

In deze gids zullen we eerst een korte bespreking van de algoritme-analyse nemen en daarna dieper ingaan op de Big-O-notatie. We zullen zien hoe Big-O-notatie kan worden gebruikt om de complexiteit van algoritmen te vinden met behulp van verschillende Python-functies.

Waarom is algoritmeanalyse belangrijk?

Om te begrijpen waarom algoritmeanalyse belangrijk is, gebruiken we een eenvoudig voorbeeld. Stel dat een manager twee van zijn medewerkers de opdracht geeft om in Python een algoritme te ontwerpen dat de faculteit berekent van een door de gebruiker ingevoerd getal. Het door de eerste medewerker ontwikkelde algoritme ziet er als volgt uit:

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

Merk op dat het algoritme gewoon een geheel getal als argument neemt. Binnen in de fact() functie een variabele genaamd product is geïnitialiseerd op 1. Een lus wordt uitgevoerd vanaf 1 naar n en tijdens elke iteratie, de waarde in de product wordt vermenigvuldigd met het nummer dat wordt herhaald door de lus en het resultaat wordt opgeslagen in de product weer variabel. Nadat de lus is uitgevoerd, wordt de product variabele zal de faculteit bevatten.

Evenzo ontwikkelde de tweede medewerker een algoritme dat de faculteit van een getal berekent. De tweede werknemer gebruikte een recursieve functie om de faculteit van het getal te berekenen n:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

De manager moet beslissen welk algoritme hij gaat gebruiken. Om dit te doen, hebben ze besloten om te kiezen welk algoritme sneller werkt. Een manier om dit te doen is door de tijd te vinden die nodig is om de code op dezelfde invoer uit te voeren.

In het Jupyter-notebook kunt u de %timeit letterlijk gevolgd door de functieaanroep om de tijd te vinden die nodig is om de functie uit te voeren:

%timeit fact(50)

Dit geeft ons:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

De uitvoer zegt dat het algoritme neemt 9 microseconden (plus/min 45 nanoseconden) per lus.

Op dezelfde manier kunnen we berekenen hoeveel tijd de tweede benadering kost om uit te voeren:

%timeit fact2(50)

Dit resulteert in:

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Het tweede algoritme met recursie duurt 15 microseconden (plus/min 427 nanoseconden).

De uitvoeringstijd laat zien dat het eerste algoritme sneller is in vergelijking met het tweede algoritme met recursie. Bij het omgaan met grote inputs kan het prestatieverschil groter worden.

Uitvoeringstijd is echter geen goede maatstaf om de complexiteit van een algoritme te meten, aangezien deze afhankelijk is van de hardware. Er is behoefte aan een objectievere metriek voor complexiteitsanalyse voor een algoritme. Dit is waar de Grote O-notatie komt spelen.

Algoritmeanalyse met Big-O-notatie

Big-O-notatie geeft de relatie aan tussen de invoer van het algoritme en de stappen die nodig zijn om het algoritme uit te voeren. Het wordt aangegeven met een grote "O", gevolgd door een haakje openen en sluiten. Binnen de haakjes wordt de relatie tussen de invoer en de stappen van het algoritme weergegeven met behulp van "n".

De belangrijkste afhaalmaaltijd is - Big-O is niet geïnteresseerd in een bijzonder instantie waarin u een algoritme uitvoert, zoals fact(50), maar eerder, hoe goed doet het? schaal steeds meer input krijgen. Dit is een veel betere maatstaf om te evalueren dan concrete tijd voor een concrete instantie!

Als er bijvoorbeeld een lineaire relatie tussen de invoer en de stap die het algoritme neemt om de uitvoering te voltooien, is de gebruikte Big-O-notatie O (n). Evenzo is de Big-O-notatie voor kwadratische functies is O(n²).

Intuïtie opbouwen:

• O (n): Bij n=1, wordt 1 stap gezet. Bij n=10, worden 10 stappen gezet.
• O(n²): Bij n=1, wordt 1 stap gezet. Bij n=10, worden 100 stappen gezet.

At n=1, deze twee zouden hetzelfde presteren! Dit is nog een reden waarom het beter is om de relatie tussen de invoer en het aantal stappen om die invoer te verwerken te observeren dan alleen functies te evalueren met wat concrete invoer.

Hieronder volgen enkele van de meest voorkomende Big-O-functies:

Naam	Big O
constante	O (c)
Lineair	O (n)
vierkant	O(n²)
kubiek	O(n)
Exponentiële	O(2ⁿ)
Logaritmisch	O (logboek (n))
Lineair loggen	O(nlog(n))

U kunt deze functies visualiseren en vergelijken:

Over het algemeen wordt alles wat erger is dan lineair beschouwd als een slechte complexiteit (dwz inefficiënt) en moet indien mogelijk worden vermeden. Lineaire complexiteit is oké en meestal een noodzakelijk kwaad. Logaritmisch is goed. Constant is geweldig!

Laten we eens kijken naar enkele voorbeelden van constante, lineaire en kwadratische complexiteit om een ​​idee te krijgen van hoe een Big-O wordt berekend.

Constante complexiteit - O(C)

De complexiteit van een algoritme is constant als de stappen die nodig zijn om de uitvoering van een algoritme te voltooien constant blijven, ongeacht het aantal ingangen. De constante complexiteit wordt aangegeven met O (c) WAAR c kan elk constant getal zijn.

Laten we een eenvoudig algoritme in Python schrijven dat het kwadraat van het eerste item in de lijst vindt en dit vervolgens op het scherm afdrukt:

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

In het bovenstaande script ongeacht de invoergrootte, of het aantal items in de invoerlijst items, voert het algoritme slechts 2 stappen uit:

1. Het kwadraat van het eerste element vinden
2. Het resultaat op het scherm afdrukken.

De complexiteit blijft dus constant.

Als u een lijnplot tekent met de variërende grootte van de items invoer op de X-as en het aantal stappen op de Y-as, dan krijgt u een rechte lijn. Laten we een kort script maken om dit te visualiseren. Ongeacht het aantal ingangen, het aantal uitgevoerde stappen blijft hetzelfde:

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

Lineaire complexiteit - O (n)

De complexiteit van een algoritme wordt lineair genoemd als de stappen die nodig zijn om de uitvoering van een algoritme te voltooien lineair toenemen of afnemen met het aantal ingangen. Lineaire complexiteit wordt aangeduid met O (n).

Laten we in dit voorbeeld een eenvoudig programma schrijven dat alle items in de lijst op de console weergeeft:

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

De complexiteit van de linear_algo() functie is lineair in het bovenstaande voorbeeld, aangezien het aantal iteraties van de for-lus zal zijn gelijk aan de grootte van de invoer items reeks. Als er bijvoorbeeld 4 items in de items list, wordt de for-loop 4 keer uitgevoerd.

Laten we snel een plot maken voor het lineaire complexiteitsalgoritme met het aantal ingangen op de x-as en het aantal stappen op de y-as:

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

Dit resulteert in:

Een belangrijk ding om op te merken is dat bij grote invoer constanten de neiging hebben om waarde te verliezen. Dit is de reden waarom we meestal constanten uit de Big-O-notatie verwijderen, en een uitdrukking zoals O(2n) wordt meestal afgekort tot O(n). Zowel O(2n) als O(n) zijn lineair – het gaat om de lineaire relatie, niet om de concrete waarde. Laten we bijvoorbeeld de wijzigen linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

Er zijn twee for-lussen die de invoer herhalen items lijst. Daarom wordt de complexiteit van het algoritme O (2n), maar in het geval van oneindige items in de invoerlijst, is het dubbele van oneindig nog steeds gelijk aan oneindig. We kunnen de constante negeren 2 (omdat het uiteindelijk onbeduidend is) en de complexiteit van het algoritme blijft O (n).

Laten we dit nieuwe algoritme visualiseren door de invoer op de X-as en het aantal stappen op de Y-as te plotten:

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

In het bovenstaande script kun je dat duidelijk zien j=2n, de uitvoer is echter lineair en ziet er als volgt uit:

Kwadratische complexiteit - O(n²)

De complexiteit van een algoritme wordt kwadratisch genoemd wanneer de stappen die nodig zijn om een ​​algoritme uit te voeren een kwadratische functie zijn van het aantal items in de invoer. Kwadratische complexiteit wordt aangeduid als O(n²):

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

We hebben een buitenste lus die alle items in de invoerlijst doorloopt en vervolgens een geneste binnenste lus, die opnieuw alle items in de invoerlijst doorloopt. Het totale aantal uitgevoerde stappen is n*n, waarbij n het aantal items in de invoerarray is.

In de volgende grafiek wordt het aantal ingangen uitgezet tegen de stappen voor een algoritme met kwadratische complexiteit:

Logaritmische complexiteit – O (ingelogd)

Sommige algoritmen bereiken logaritmische complexiteit, zoals: Binaire zoekopdracht. Binary Search zoekt naar een element in een array, door de . aan te vinken midden van een array, en het snoeien van de helft waarin het element zich niet bevindt. Het doet dit opnieuw voor de resterende helft en gaat door met dezelfde stappen totdat het element is gevonden. Bij elke stap is het helften het aantal elementen in de array.

Dit vereist dat de array wordt gesorteerd en dat we een aanname maken over de gegevens (zoals dat deze is gesorteerd).

Wanneer u aannames kunt doen over de binnenkomende gegevens, kunt u stappen ondernemen die de complexiteit van een algoritme verminderen. Logaritmische complexiteit is wenselijk, omdat het zelfs met zeer geschaalde invoer goede prestaties levert.

De complexiteit van complexe functies vinden?

In eerdere voorbeelden hadden we vrij eenvoudige functies bij invoer. Maar hoe berekenen we de Big-O van functies die (meerdere) andere functies op de invoer aanroepen?

Laten we kijken:

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

In het bovenstaande script worden verschillende taken uitgevoerd, eerst wordt er 5 keer een string op de console afgedrukt met de print uitspraak. Vervolgens printen we de invoerlijst twee keer op het scherm en ten slotte wordt drie keer een andere string op de console afgedrukt. Om de complexiteit van zo'n algoritme te vinden, moeten we de algoritmecode in delen opsplitsen en proberen de complexiteit van de afzonderlijke stukken te vinden. Markeer de complexiteit van elk stuk.

In het eerste deel hebben we:

for i in range(5):
	print("Python is awesome")

De complexiteit van dit deel is: O (5) omdat er in dit stuk code vijf constante stappen worden uitgevoerd, ongeacht de invoer.

Vervolgens hebben we:

for item in items:
	print(item)

We weten dat de complexiteit van het bovenstaande stukje code is: O (n). Evenzo is de complexiteit van het volgende stuk code ook: O (n):

for item in items:
	print(item)

Ten slotte wordt in het volgende stuk code drie keer een tekenreeks afgedrukt, vandaar dat de complexiteit is O (3):

print("Big O")
print("Big O")
print("Big O")

Om de algehele complexiteit te vinden, hoeven we alleen deze individuele complexiteiten toe te voegen:

O(5) + O(n) + O(n) + O(3)

Als we het bovenstaande vereenvoudigen, krijgen we:

O(8) + O(2n) = O(8+2n)

We zeiden eerder dat wanneer de invoer (die in dit geval lengte n heeft) extreem groot wordt, de constanten onbeduidend worden, dat wil zeggen dat twee of de helft van de oneindigheid nog steeds oneindig blijft. Daarom kunnen we de constanten negeren. De uiteindelijke complexiteit van het algoritme zal zijn: O (n)!

Worst vs Best Case Complexiteit

Als iemand je vraagt ​​naar de complexiteit van een algoritme, is hij meestal geïnteresseerd in de complexiteit in het slechtste geval (Big-O). Soms zijn ze misschien ook geïnteresseerd in de best-case complexiteit (Big-Omega).

Laten we eens naar een ander stukje code kijken om de relatie hiertussen te begrijpen:

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

In het bovenstaande script hebben we een functie die een getal en een lijst met getallen als invoer nodig heeft. Het retourneert true als het doorgegeven getal wordt gevonden in de lijst met getallen, anders retourneert het None. Als u zoekt naar 2 in de lijst, wordt deze gevonden in de eerste vergelijking. Dit is de best case complexiteit van het algoritme omdat het gezochte item wordt gevonden in de eerste gezochte index. De beste case-complexiteit, in dit geval, is O (1). Aan de andere kant, als u 10 zoekt, wordt deze gevonden in de laatst gezochte index. Het algoritme zal door alle items in de lijst moeten zoeken, vandaar de worst-case complexiteit wordt O (n).

Naast best- en worstcasecomplexiteit, kun je ook berekenen: de gemiddelde complexiteit (Big-Theta) van een algoritme, dat u vertelt "gegeven een willekeurige invoer, wat is de verwachte tijdscomplexiteit van het algoritme"?

Complexiteit van de ruimte

Naast de tijdscomplexiteit, waarbij je het aantal stappen telt dat nodig is om de uitvoering van een algoritme te voltooien, kun je ook de ruimte complexiteit wat verwijst naar de hoeveelheid ruimte die u in het geheugen moet toewijzen tijdens de uitvoering van een programma.

Kijk eens naar het volgende voorbeeld:

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

De return_squares() functie accepteert een lijst met gehele getallen en retourneert een lijst met de bijbehorende vierkanten. Het algoritme moet geheugen toewijzen voor hetzelfde aantal items als in de invoerlijst. Daarom wordt de ruimtecomplexiteit van het algoritme O (n).

Conclusie

De Big-O-notatie is de standaardmaat die wordt gebruikt om de complexiteit van een algoritme te meten. In deze gids hebben we onderzocht wat Big-O-notatie is en hoe deze kan worden gebruikt om de complexiteit van verschillende algoritmen te meten. We hebben ook verschillende soorten Big-O-functies bestudeerd met behulp van verschillende Python-voorbeelden. Ten slotte hebben we kort de complexiteit van het slechtste en het beste geval besproken, samen met de complexiteit van de ruimte.