Big O-notation och algoritmanalys med Python-exempel

Beskrivning

Det finns vanligtvis flera sätt att lösa problemet med hjälp av ett datorprogram. Det finns till exempel flera sätt att sortera objekt i en array – du kan använda slå samman sortering, bubbelsorter, insättningssortering, och så vidare. Alla dessa algoritmer har sina egna för- och nackdelar och utvecklarens jobb är att väga dem för att kunna välja den bästa algoritmen att använda i alla användningsfall. Med andra ord är huvudfrågan vilken algoritm som ska användas för att lösa ett specifikt problem när det finns flera lösningar på problemet.

Algoritmanalys syftar på analys av komplexiteten hos olika algoritmer och att hitta den mest effektiva algoritmen för att lösa det aktuella problemet. Big-O-notering är ett statistiskt mått som används för att beskriva algoritmens komplexitet.

I den här guiden tar vi först en kort genomgång av algoritmanalys och tar sedan en djupare titt på Big-O-notationen. Vi ska se hur Big-O-notation kan användas för att hitta algoritmkomplexitet med hjälp av olika Python-funktioner.

Varför är algoritmanalys viktig?

För att förstå varför algoritmanalys är viktigt tar vi hjälp av ett enkelt exempel. Anta att en chef ger en uppgift till två av sina anställda att designa en algoritm i Python som beräknar fakulteten för ett tal som angetts av användaren. Algoritmen som utvecklats av den första medarbetaren ser ut så här:

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

print(fact(5))

Lägg märke till att algoritmen helt enkelt tar ett heltal som ett argument. Inuti fact() funktion en variabel med namnet product initialiseras till 1. En loop körs från 1 till n och under varje iteration, värdet i product multipliceras med talet som itereras av loopen och resultatet lagras i product variabel igen. Efter att loopen har körts, product variabeln kommer att innehålla faktorn.

På samma sätt utvecklade den andra anställde också en algoritm som beräknar ett tals faktor. Den andra anställde använde en rekursiv funktion för att beräkna numrets faktor n:

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

print(fact2(5))

Chefen måste bestämma vilken algoritm som ska användas. För att göra det har de bestämt sig för att välja vilken algoritm som kör snabbare. Ett sätt att göra det är att hitta den tid som krävs för att exekvera koden på samma ingång.

I Jupyter-anteckningsboken kan du använda %timeit literal följt av funktionsanropet för att hitta den tid det tar för funktionen att köra:

%timeit fact(50)

Detta kommer att ge oss:

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

Utdata säger att algoritmen tar 9 mikrosekunder (plus/minus 45 nanosekunder) per slinga.

På samma sätt kan vi beräkna hur lång tid det tar att utföra det andra tillvägagångssättet:

%timeit fact2(50)

Detta kommer att resultera i:

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

Den andra algoritmen som involverar rekursion tar 15 mikrosekunder (plus/minus 427 nanosekunder).

Exekveringstiden visar att den första algoritmen är snabbare jämfört med den andra algoritmen som involverar rekursion. När man hanterar stora insatser kan prestandaskillnaden bli mer betydande.

Exekveringstid är dock inte ett bra mått för att mäta komplexiteten hos en algoritm eftersom den beror på hårdvaran. En mer objektiv komplexitetsanalysmått för en algoritm behövs. Det är här Stor O-notation kommer att spela.

Algoritmanalys med Big-O-notation

Big-O-notation anger förhållandet mellan indata till algoritmen och de steg som krävs för att exekvera algoritmen. Det betecknas med ett stort "O" följt av en öppnings- och stängningsparentes. Inom parentesen presenteras förhållandet mellan indata och de steg som tas av algoritmen med hjälp av "n".

Det viktigaste är att Big-O inte är intresserad av en särskilt instans där du kör en algoritm, som t.ex fact(50), utan snarare, hur bra gör det skala ges ökande input. Detta är ett mycket bättre mått för att utvärdera än konkret tid för en konkret instans!

Till exempel, om det finns en linjärt förhållande mellan inmatningen och steget som algoritmen tar för att slutföra dess exekvering, kommer Big-O-notationen som används att vara O (n). På samma sätt, Big-O notationen för kvadratiska funktioner is O(n²).

Att bygga intuition:

• O (n): kl n=1, 1 steg tas. På n=10, 10 steg tas.
• O(n²): kl n=1, 1 steg tas. På n=10, 100 steg tas.

At n=1, dessa två skulle prestera likadant! Detta är ytterligare ett skäl till varför det är bättre att observera sambandet mellan input och antalet steg för att bearbeta den inputen än att bara utvärdera funktioner med någon konkret input.

Följande är några av de vanligaste Big-O-funktionerna:

Namn	Stor O
Konstant	O (c)
Linjär	O (n)
Kvadratisk	O(n²)
kubisk	O(n³)
Exponentiell	O(2ⁿ)
Logaritmisk	O (log (n))
Log linjär	O(nlog(n))

Du kan visualisera dessa funktioner och jämföra dem:

Generellt sett – allt värre än linjärt anses vara en dålig komplexitet (dvs ineffektiv) och bör undvikas om möjligt. Linjär komplexitet är okej och vanligtvis ett nödvändigt ont. Logaritmisk är bra. Constant är fantastiskt!

För att få en uppfattning om hur ett Big-O beräknas, låt oss ta en titt på några exempel på konstant, linjär och kvadratisk komplexitet.

Konstant komplexitet - O(C)

Komplexiteten hos en algoritm sägs vara konstant om de steg som krävs för att slutföra exekveringen av en algoritm förblir konstanta, oavsett antalet ingångar. Den konstanta komplexiteten betecknas med O (c) var c kan vara vilket konstant tal som helst.

Låt oss skriva en enkel algoritm i Python som hittar kvadraten på det första objektet i listan och sedan skriver ut det på skärmen:

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

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

I manuset ovan, oavsett ingångsstorlek, eller antalet objekt i inmatningslistan items, utför algoritmen endast två steg:

1. Hitta kvadraten på det första elementet
2. Skriver ut resultatet på skärmen.

Därför förblir komplexiteten konstant.

Om du ritar ett linjediagram med varierande storlek på items inmatning på X-axeln och antalet steg på Y-axeln får du en rak linje. Låt oss skapa ett kort skript som hjälper oss att visualisera detta. Oavsett antalet ingångar förblir antalet utförda steg detsamma:

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

Linjär komplexitet – O (n)

Komplexiteten hos en algoritm sägs vara linjär om de steg som krävs för att slutföra exekveringen av en algoritm ökar eller minskar linjärt med antalet ingångar. Linjär komplexitet betecknas med O (n).

I det här exemplet, låt oss skriva ett enkelt program som visar alla objekt i listan till konsolen:

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

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

Komplexiteten i linear_algo() funktionen är linjär i exemplet ovan eftersom antalet iterationer av for-loopen kommer att vara lika med storleken på ingången items array. Till exempel, om det finns 4 objekt i items listan kommer for-loopen att exekveras 4 gånger.

Låt oss snabbt skapa en plot för den linjära komplexitetsalgoritmen med antalet ingångar på x-axeln och antalet steg på y-axeln:

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')

Detta kommer att resultera i:

En viktig sak att notera är att med stora ingångar tenderar konstanter att förlora i värde. Det är därför vi vanligtvis tar bort konstanter från Big-O notation, och ett uttryck som O(2n) förkortas vanligtvis till O(n). Både O(2n) och O(n) är linjära – det linjära sambandet är det viktiga, inte det konkreta värdet. Låt oss till exempel ändra linear_algo():

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

    for item in items:
        print(item)

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

Det finns två for-loopar som itererar över ingången items lista. Därför blir komplexiteten i algoritmen O (2n), men i fallet med oändliga objekt i inmatningslistan, är två gånger av oändlighet fortfarande lika med oändlighet. Vi kan ignorera konstanten 2 (eftersom den i slutändan är obetydlig) och komplexiteten i algoritmen kvarstår O (n).

Låt oss visualisera denna nya algoritm genom att plotta ingångarna på X-axeln och antalet steg på Y-axeln:

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')

I manuset ovan kan du tydligt se det y=2nutgången är dock linjär och ser ut så här:

Kvadratisk komplexitet – O(n²)

Komplexiteten hos en algoritm sägs vara kvadratisk när stegen som krävs för att exekvera en algoritm är en kvadratisk funktion av antalet objekt i inmatningen. Kvadratisk komplexitet betecknas som O(n²):

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

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

Vi har en yttre slinga som itererar genom alla objekt i inmatningslistan och sedan en kapslad inre slinga, som återigen itererar genom alla objekt i inmatningslistan. Det totala antalet utförda steg är n*n, där n är antalet objekt i inmatningsmatrisen.

Följande graf plottar antalet ingångar mot stegen för en algoritm med kvadratisk komplexitet:

Logaritmisk komplexitet – O (logn)

Vissa algoritmer uppnår logaritmisk komplexitet, som t.ex Binär sökning. Binär sökning söker efter ett element i en array genom att markera mitten av en array och beskärning av halvan där elementet inte finns. Den gör detta igen för den återstående halvan och fortsätter med samma steg tills elementet hittas. I varje steg, det halvor antalet element i arrayen.

Detta kräver att arrayen sorteras och att vi gör ett antagande om data (som att den är sorterad).

När du kan göra antaganden om inkommande data kan du vidta åtgärder som minskar komplexiteten hos en algoritm. Logaritmisk komplexitet är önskvärt, eftersom den uppnår bra prestanda även med mycket skalad input.

Hitta komplexiteten hos komplexa funktioner?

I tidigare exempel hade vi ganska enkla funktioner på input. Men hur beräknar vi Big-O för funktioner som anropar (flera) andra funktioner på ingången?

Låt oss ta en titt:

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])

I skriptet ovan utförs flera uppgifter, först skrivs en sträng ut 5 gånger på konsolen med hjälp av print påstående. Därefter skriver vi ut inmatningslistan två gånger på skärmen, och slutligen skrivs ytterligare en sträng ut tre gånger på konsolen. För att hitta komplexiteten i en sådan algoritm måste vi bryta ner algoritmkoden i delar och försöka hitta komplexiteten hos de enskilda delarna. Markera komplexiteten hos varje del.

I det första avsnittet har vi:

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

Komplexiteten i denna del är O (5) eftersom fem konstanta steg utförs i denna kodbit oberoende av inmatningen.

Därefter har vi:

for item in items:
	print(item)

Vi vet att komplexiteten i ovanstående kodbit är O (n). På samma sätt är komplexiteten hos följande kodbit också O (n):

for item in items:
	print(item)

Slutligen, i följande kodbit, skrivs en sträng ut tre gånger, därför är komplexiteten O (3):

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

För att hitta den övergripande komplexiteten måste vi helt enkelt lägga till dessa individuella komplexiteter:

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

För att förenkla ovanstående får vi:

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

Vi sa tidigare att när ingången (som har längden n i det här fallet) blir extremt stor, blir konstanterna obetydliga, dvs två gånger eller hälften av oändligheten förblir fortfarande oändligt. Därför kan vi ignorera konstanterna. Algoritmens slutliga komplexitet kommer att vara O (n)!

Worst vs Best Case Complexity

Vanligtvis, när någon frågar dig om komplexiteten hos en algoritm – de är intresserade av värsta tänkbara komplexiteten (Big-O). Ibland kan de också vara intresserade av bästa möjliga komplexitet (Big-Omega).

För att förstå förhållandet mellan dessa, låt oss ta en titt på en annan kod:

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))

I skriptet ovan har vi en funktion som tar ett nummer och en lista med nummer som indata. Det returnerar sant om det godkända numret finns i listan med nummer, annars returnerar det None. Om du söker på 2 i listan så kommer den att hittas i den första jämförelsen. Detta är den bästa fallets komplexitet för algoritmen genom att det sökta objektet finns i det första sökta indexet. Det bästa fallets komplexitet, i det här fallet, är O (1). Å andra sidan, om du söker 10, kommer den att hittas vid det senast sökta indexet. Algoritmen måste därför söka igenom alla objekt i listan värsta tänkbara komplexiteten blir O (n).

Förutom best och worst case-komplexitet kan du även räkna den genomsnittliga komplexiteten (Big-Theta) av en algoritm, som säger till dig "med en slumpmässig inmatning, vad är den förväntade tidskomplexiteten för algoritmen"?

Rymdkomplexitet

Förutom tidskomplexiteten, där du räknar antalet steg som krävs för att slutföra exekveringen av en algoritm, kan du också hitta rymdkomplexitet vilket hänvisar till hur mycket utrymme du behöver allokera i minnet under körningen av ett program.

Ta en titt på följande exempel:

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))

Smakämnen return_squares() funktion accepterar en lista med heltal och returnerar en lista med motsvarande kvadrater. Algoritmen måste allokera minne för samma antal objekt som i inmatningslistan. Därför blir rymdkomplexiteten hos algoritmen O (n).

Slutsats

Big-O-notationen är standardmåttet som används för att mäta komplexiteten hos en algoritm. I den här guiden studerade vi vad Big-O-notation är och hur den kan användas för att mäta komplexiteten hos en mängd olika algoritmer. Vi studerade även olika typer av Big-O-funktioner med hjälp av olika Python-exempel. Slutligen granskade vi kort den värsta och bästa fallets komplexitet tillsammans med utrymmeskomplexiteten.