Python >> Python tutorial >  >> Python

Big O-notation og algoritmeanalyse med Python-eksempler

Der er flere måder at løse et problem på ved hjælp af et computerprogram. For eksempel er der flere måder at sortere elementer i en matrix på. Du kan bruge flettesortering, boblesortering, indsættelsessortering osv. Alle disse algoritmer har deres egne fordele og ulemper. En algoritme kan tænkes på en procedure eller formel til at løse et bestemt problem. Spørgsmålet er, hvilken algoritme man skal bruge til at løse et specifikt problem, når der findes flere løsninger på problemet?

Algoritmeanalyse refererer til analyse af kompleksiteten af ​​forskellige algoritmer og finde den mest effektive algoritme til at løse det aktuelle problem. Big-O Notation er et statistisk mål, der bruges til at beskrive kompleksiteten af ​​algoritmen.

I denne artikel vil vi kort gennemgå algoritmeanalyse og Big-O-notation. Vi vil se, hvordan Big-O-notation kan bruges til at finde algoritmekompleksitet ved hjælp af forskellige Python-funktioner.

Hvorfor er algoritmeanalyse vigtig?

For at forstå hvorfor algoritmeanalyse er vigtig, vil vi tage hjælp af et simpelt eksempel.

Antag, at en leder giver en opgave til to af sine medarbejdere om at designe en algoritme i Python, der beregner fakulteten af ​​et tal, som brugeren indtaster.

Algoritmen udviklet af den første medarbejder ser således ud:

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

print(fact(5))

Bemærk, at algoritmen blot tager et heltal som et argument. Inde i fact funktion en variabel ved navn product initialiseres til 1. En løkke udføres fra 1 til N og under hver iteration, værdien i product ganges med tallet, der gentages af løkken, og resultatet gemmes i product variabel igen. Efter at løkken er udført, vises product variablen vil indeholde faktoren.

På samme måde udviklede den anden medarbejder også en algoritme, der beregner fakultet af et tal. Den anden medarbejder brugte en rekursiv funktion til at beregne fakultetet for et program som vist nedenfor:

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

print(fact2(5))

Lederen skal beslutte, hvilken algoritme der skal bruges. For at gøre det skal han finde kompleksiteten af ​​algoritmen. En måde at gøre det på er ved at finde den tid, der kræves til at udføre algoritmerne.

I Jupyter-notesbogen kan du bruge %timeit literal efterfulgt af funktionskaldet for at finde den tid, det tager funktionen at udføre. Se på følgende script:

%timeit fact(50)

Output:

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

Outputtet siger, at algoritmen tager 9 mikrosekunder (plus/minus 45 nanosekunder) pr. loop.

På samme måde skal du udføre følgende script:

%timeit fact2(50)

Output:

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

Den anden algoritme, der involverer rekursion, tager 15 mikrosekunder (plus/minus 427 nanosekunder).

Udførelsestiden viser, at den første algoritme er hurtigere sammenlignet med den anden algoritme, der involverer rekursion. Dette eksempel viser vigtigheden af ​​algoritmeanalyse. I tilfælde af store input kan ydelsesforskellen blive større.

Udførelsestid er dog ikke en god metrik til at måle kompleksiteten af ​​en algoritme, da den afhænger af hardwaren. Der er behov for en mere objektiv kompleksitetsanalyse for algoritmerne. Det er her, Big O-notationen kommer til at spille.

Algorithmeanalyse med Big-O-notation

Big-O notation er en metrik, der bruges til at finde algoritmens kompleksitet. Grundlæggende betyder Big-O-notation forholdet mellem input til algoritmen og de nødvendige trin for at udføre algoritmen. Det er angivet med et stort "O" efterfulgt af åbne- og lukkeparenteser. Inde i parentesen præsenteres forholdet mellem inputtet og de trin, algoritmen tager, ved hjælp af "n".

For eksempel, hvis der er et lineært forhold mellem inputtet og det trin, algoritmen tager for at fuldføre dens udførelse, vil den anvendte Big-O-notation være O(n). På samme måde er Big-O-notationen for kvadratiske funktioner O(n^2)

Følgende er nogle af de mest almindelige Big-O-funktioner:

Navn Big O
Konstant O(c)
Lineær O(n)
Kvadratisk O(n^2)
Kubisk O(n^3)
Eksponentiel O(2^n)
Logaritmisk O(log(n))
Log lineær O(nlog(n))

For at få en idé om, hvordan Big-O-notation beregnes, lad os tage et kig på nogle eksempler på konstant, lineær og kvadratisk kompleksitet.

Konstant kompleksitet (O(C))

Kompleksiteten af ​​en algoritme siges at være konstant, hvis de nødvendige trin for at fuldføre udførelsen af ​​en algoritme forbliver konstante, uanset antallet af input. Den konstante kompleksitet er angivet med O(c), hvor c kan være et hvilket som helst konstant tal.

Lad os skrive en simpel algoritme i Python, der finder kvadratet af det første element på listen og derefter udskriver det på skærmen.

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

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

I ovenstående script, uafhængigt af inputstørrelsen , eller antallet af elementer i inputlisten items , udfører algoritmen kun 2 trin:Finder kvadratet af det første element og udskriver resultatet på skærmen. Derfor forbliver kompleksiteten konstant.

Hvis du tegner et linjeplot med den varierende størrelse af items input på x-aksen og antallet af trin på y-aksen, får du en ret linje. For at visualisere dette skal du udføre følgende script:

import matplotlib.pyplot as plt
import numpy as np

x = [2, 4, 6, 8, 10, 12]

y = [2, 2, 2, 2, 2, 2]

plt.plot(x, y, 'b')
plt.xlabel('Inputs')
plt.ylabel('Steps')
plt.title('Constant Complexity')
plt.show()

Output:

Lineær kompleksitet (O(n))

Kompleksiteten af ​​en algoritme siges at være lineær, hvis de nødvendige trin for at fuldføre udførelsen af ​​en algoritme stiger eller falder lineært med antallet af input. Lineær kompleksitet er angivet med O(n).

Lad os i dette eksempel skrive et simpelt program, der viser alle elementer på listen til konsollen:

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

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

Kompleksiteten af ​​linear_algo funktion er lineær i ovenstående eksempel, da antallet af iterationer af for-løkken vil være lig med størrelsen af ​​inputtet items matrix . For eksempel, hvis der er 4 elementer i items liste, vil for-løkken blive udført 4 gange, og så videre.

Plottet for lineær kompleksitet med input på x-aksen og antal trin på x-aksen er som følger:

import matplotlib.pyplot as plt
import numpy as np

x = [2, 4, 6, 8, 10, 12]

y = [2, 4, 6, 8, 10, 12]

plt.plot(x, y, 'b')
plt.xlabel('Inputs')
plt.ylabel('Steps')
plt.title('Linear Complexity')
plt.show()

Output:

Et andet punkt at bemærke her er, at i tilfælde af et stort antal input bliver konstanterne ubetydelige. Tag for eksempel et kig på følgende script:

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

    for item in items:
        print(item)

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

I scriptet ovenfor er der to for-loops, der itererer over inputtet items liste. Derfor bliver kompleksiteten af ​​algoritmen O(2n), men i tilfælde af uendelige elementer i inputlisten, er det dobbelte af uendelighed stadig lig med uendeligt, derfor kan vi ignorere konstanten 2 (da den i sidste ende er ubetydelig) og kompleksiteten af algoritmen forbliver O(n).

Vi kan yderligere verificere og visualisere dette ved at plotte inputs på x-aksen og antallet af trin på y-aksen som vist nedenfor:

import matplotlib.pyplot as plt
import numpy as np

x = [2, 4, 6, 8, 10, 12]

y = [4, 8, 12, 16, 20, 24]

plt.plot(x, y, 'b')
plt.xlabel('Inputs')
plt.ylabel('Steps')
plt.title('Linear Complexity')
plt.show()

I scriptet ovenfor kan du tydeligt se, at y=2n, men outputtet er lineært og ser sådan ud:

Kvadratisk kompleksitet (O(n^2))

Kompleksiteten af ​​en algoritme siges at være kvadratisk, når de nødvendige trin for at udføre en algoritme er en kvadratisk funktion af antallet af elementer i inputtet. Kvadratisk kompleksitet betegnes som O(n^2). Tag et kig på følgende eksempel for at se en funktion med kvadratisk kompleksitet:

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

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

I scriptet ovenfor kan du se, at vi har en ydre sløjfe, der itererer gennem alle elementerne i inputlisten og derefter en nestet indre loop, som igen itererer gennem alle elementerne i inputlisten. Det samlede antal udførte trin er n * n, hvor n er antallet af elementer i input-arrayet.

Følgende graf viser antallet af input vs. trinene for en algoritme med kvadratisk kompleksitet.

Find kompleksiteten af ​​komplekse funktioner

I de foregående eksempler så vi, at der kun blev udført én funktion på inputtet. Hvad hvis der udføres flere funktioner på indgangen? Tag et kig på følgende eksempel.

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 scriptet ovenfor udføres flere opgaver, først udskrives en streng 5 gange på konsollen ved hjælp af print udmelding. Dernæst udskriver vi inputlisten to gange på skærmen og til sidst udskrives endnu en streng tre gange på konsollen. For at finde kompleksiteten af ​​en sådan algoritme er vi nødt til at nedbryde algoritmekoden i dele og forsøge at finde kompleksiteten af ​​de enkelte stykker.

Lad os opdele vores manuskript i individuelle dele. I den første del har vi:

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

Kompleksiteten af ​​denne del er O(5). Da der udføres fem konstante trin i dette stykke kode, uanset input.

Dernæst har vi:

    for item in items:
        print(item)

Vi ved, at kompleksiteten af ​​ovenstående kodestykke er O(n).

På samme måde er kompleksiteten af ​​det følgende kodestykke også O(n)

    for item in items:
        print(item)

Til sidst, i det følgende kodestykke, bliver en streng udskrevet tre gange, hvorfor kompleksiteten er O(3)

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

For at finde den overordnede kompleksitet skal vi blot tilføje disse individuelle kompleksiteter. Lad os gøre det:

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

For at forenkle ovenstående får vi:

O(8) + O(2n)

Vi sagde tidligere, at når inputtet (som har længden n i dette tilfælde) bliver ekstremt stort, bliver konstanterne ubetydelige, dvs. to gange eller halvdelen af ​​uendeligheden forbliver stadig uendelig. Derfor kan vi ignorere konstanterne. Algoritmens endelige kompleksitet vil være O(n).

Worst vs Best Case Complexity

Normalt, når nogen spørger dig om kompleksiteten af ​​algoritmen, spørger han dig om den værste kompleksitet. For at forstå den bedste sag og værre sagskompleksitet, se på følgende script:

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 scriptet ovenfor har vi en funktion, der tager et tal og en liste over tal som input. Det returnerer sandt, hvis det beståede tal findes på listen over tal, ellers returnerer det None . Søger du 2 i listen, vil den blive fundet i den første sammenligning. Dette er det bedste tilfælde af kompleksiteten af ​​algoritmen, at det søgte emne findes i det først søgte indeks. Den bedste sagskompleksitet, i dette tilfælde, er O(1). På den anden side, hvis du søger 10, vil den blive fundet ved det sidst søgte indeks. Algoritmen bliver nødt til at søge gennem alle elementerne på listen, og derfor bliver det værste tilfælde O(n).

Udover best og worst case kompleksitet kan du også beregne den gennemsnitlige kompleksitet af en algoritme, som fortæller dig "ud fra et tilfældigt input, hvad er den forventede tidskompleksitet af algoritmen"?

Rumkompleksitet

Ud over tidskompleksiteten, hvor du tæller antallet af trin, der kræves for at fuldføre udførelsen af ​​en algoritme, kan du også finde pladskompleksitet, som refererer til det antal pladser, du skal allokere i hukommelsespladsen under udførelsen af ​​et program .

Tag et kig på følgende eksempel:

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

I scriptet ovenfor accepterer funktionen en liste over heltal og returnerer en liste med de tilsvarende kvadrater af heltal. Algoritmen skal allokere hukommelse til det samme antal elementer som i inputlisten. Derfor bliver rumkompleksiteten af ​​algoritmen O(n).

Konklusion

Big-O-notationen er standardmetrikken, der bruges til at måle kompleksiteten af ​​en algoritme. I denne artikel undersøgte vi, hvad Big-O-notation er, og hvordan det kan bruges til at måle kompleksiteten af ​​en række forskellige algoritmer. Vi studerede også forskellige typer af Big-O-funktioner ved hjælp af forskellige Python-eksempler. Til sidst gennemgik vi kort den værste og bedste sags kompleksitet sammen med pladskompleksiteten.