Big O Cheat Sheet: Forklart med Python-eksempler

Big O Analysis er en teknikk for å analysere og rangere effektiviteten til algoritmer.

Dette lar deg velge de mest effektive og skalerbare algoritmene. Denne artikkelen er et Big O Cheat Sheet som forklarer alt du trenger å vite om Big O Notation.

Hva er Big O-analyse?

Big O Analysis er en teknikk for å analysere hvor godt algoritmer skalerer. Spesifikt spør vi hvor effektiv en algoritme er når inngangsstørrelsen øker.

Effektivitet er hvor godt systemressurser brukes mens de produserer en utgang. Ressursene vi først og fremst er opptatt av er tid og hukommelse.

Derfor, når du utfører Big O-analyse, er spørsmålene vi stiller:

Hvordan endres en algoritmes bruk av minne ettersom inngangsstørrelsen vokser?

Hvordan endrer tiden en algoritme tar å produsere en utgang ettersom inngangsstørrelsen vokser?

Svaret på det første spørsmålet er algoritmens romkompleksitet, mens svaret på det andre er tidskompleksiteten. Vi bruker en spesiell notasjon kalt Big O Notation for å uttrykke svar på begge spørsmålene. Dette vil bli dekket neste gang i Big O Cheat Sheet.

Forutsetninger

Før jeg går videre, må jeg si at for å få mest mulig ut av dette Big O Cheat Sheet, må du forstå litt algebra. I tillegg, fordi jeg skal gi Python-eksempler, er det også nyttig å forstå litt av Python. En dybdeforståelse er unødvendig siden du ikke skal skrive noen kode.

Hvordan utføre Big O-analyse

I denne delen vil vi dekke hvordan du utfører Big O-analyse.

Når du utfører Big O Complexity Analysis, er det viktig å huske at algoritmeytelsen avhenger av hvordan inndataene er strukturert.

For eksempel kjører sorteringsalgoritmer raskest når dataene i listen allerede er sortert i riktig rekkefølge. Det er det beste scenarioet for algoritmens ytelse. På den annen side er de samme sorteringsalgoritmene tregest når data er strukturert i omvendt rekkefølge. Det er det verste scenarioet.

Når vi utfører Big O-analyse, tar vi kun i betraktning det verste tilfellet.

Romkompleksitetsanalyse

La oss begynne dette Big O Cheat Sheet med å dekke hvordan man utfører romkompleksitetsanalyse. Vi ønsker å vurdere hvordan tilleggsminnet en algoritme bruker skalerer etter hvert som inngangen blir større og større.

For eksempel bruker funksjonen nedenfor rekursjon for å sløyfe fra n til null. Den har en romkompleksitet som er direkte proporsjonal med n. Dette er fordi når n vokser, øker også antallet funksjonsanrop på anropsstakken. Så den har en romkompleksitet på O(n).

def loop_recursively(n):
    if n == -1:
        return
    else:
        print(n)
        loop_recursively(n - 1)

En bedre implementering vil imidlertid se slik ut:

def loop_normally(n):
    count = n
    while count >= 0:
        print(count)
        count =- 1

I algoritmen ovenfor lager vi bare én ekstra variabel og bruker den til å løkke. Hvis n ble større og større, ville vi fortsatt bare brukt én ekstra variabel. Derfor har algoritmen konstant romkompleksitet, betegnet med «O(1)»-symbolet.

Ved å sammenligne romkompleksiteten til de to algoritmene ovenfor, konkluderte vi med at while-løkken var mer effektiv enn rekursjon. Det er hovedmålet med Big O Analysis: å analysere hvordan algoritmer endres når vi kjører dem med større innganger.

Tidskompleksitetsanalyse

Når vi utfører tidskompleksitetsanalyse, er vi ikke bekymret for veksten i total tid tatt av algoritmen. Snarere er vi bekymret over veksten av beregningsmessige skritt som er tatt. Dette er fordi den faktiske tiden avhenger av mange systemiske og tilfeldige faktorer som er vanskelig å gjøre rede for. Så vi sporer bare veksten av beregningstrinn og antar at hvert trinn er likt.

For å demonstrere tidskompleksitetsanalyse, vurder følgende eksempel:

Anta at vi har en liste over brukere der hver bruker har en ID og navn. Vår oppgave er å implementere en funksjon som returnerer brukerens navn når det gis en ID. Slik kan vi gjøre det:

users = [
    {'id': 0, 'name': 'Alice'},
    {'id': 1, 'name': 'Bob'},
    {'id': 2, 'name': 'Charlie'},
]

def get_username(id, users):
    for user in users:
        if user['id'] == id:
            return user['name']
    return 'User not found'

get_username(1, users)

Gitt en liste over brukere, går algoritmen vår gjennom hele brukerens array for å finne brukeren med riktig ID. Når vi har 3 brukere, utfører algoritmen 3 iterasjoner. Når vi har 10, utfører den 10.

Derfor er antall trinn lineært og direkte proporsjonalt med antall brukere. Så algoritmen vår har lineær tidskompleksitet. Imidlertid kan vi forbedre algoritmen vår.

Anta at i stedet for å lagre brukere i en liste, lagret vi dem i en ordbok. Da vil algoritmen vår for å slå opp en bruker se slik ut:

users = {
    '0': 'Alice',
    '1': 'Bob',
    '2': 'Charlie'
}

def get_username(id, users):
     if id in users:
         return users[id]
     else:
         return 'User not found'

get_username(1, users)

Med denne nye algoritmen, anta at vi hadde 3 brukere i ordboken vår; vi ville utføre flere trinn for å få brukernavnet. Og anta at vi hadde flere brukere, si ti. Vi ville utført samme antall trinn som før for å få brukeren. Etter hvert som antallet brukere vokser, forblir antall trinn for å få et brukernavn konstant.

Derfor har denne nye algoritmen konstant kompleksitet. Det spiller ingen rolle hvor mange brukere vi har; antall beregningstrinn som er tatt er det samme.

Hva er Big O-notasjon?

I forrige avsnitt diskuterte vi hvordan man beregner Big O-rom- og tidskompleksiteten for forskjellige algoritmer. Vi brukte ord som lineær og konstant for å beskrive kompleksiteter. En annen måte å beskrive kompleksiteten på er å bruke Big O Notation.

Big O-notasjon er en måte å representere en algoritmes rom- eller tidskompleksitet. Notasjonen er relativt enkel; det er en O etterfulgt av parenteser. Innenfor parentesene skriver vi en funksjon av n for å representere den spesielle kompleksiteten.

Lineær kompleksitet er representert av n, så vi ville skrive den som O(n) (lest som «O av n»). Konstant kompleksitet er representert med 1, så vi vil skrive den som O(1).

Det er flere kompleksiteter, som vi vil diskutere i neste avsnitt. Men generelt, for å skrive en algoritmes kompleksitet, følg følgende trinn:

Prøv å utvikle en matematisk funksjon av n, f(n), der f(n) er mengden plass som brukes eller beregningstrinn etterfulgt av algoritmen og n er inngangsstørrelsen.

Ta det mest dominerende begrepet i den funksjonen. Rekkefølgen av dominans for forskjellige termer fra mest dominant til minst dominant er som følger: Faktoriell, Eksponentiell, Polynomisk, Kvadratisk, Linearitmisk, Lineær, Logaritmisk og Konstant.

Fjern eventuelle koeffisienter fra begrepet.

Resultatet av det blir begrepet vi bruker innenfor parentesene våre.

Eksempel:

Tenk på følgende Python-funksjon:

users = [
    'Alice',
    'Bob',
    'Charlie'
]

def print_users(users):
    number_of_users = len(users)
    print("Total number of users:", number_of_users)

    for i in number_of_users:
        print(i, end=': ')
        print(user)

Nå skal vi beregne algoritmens Big O Time-kompleksitet.

Vi skriver først en matematisk funksjon av nf(n) for å representere antall beregningstrinn algoritmen tar. Husk at n representerer inngangsstørrelsen.

Fra vår kode utfører funksjonen to trinn: ett for å beregne antall brukere og det andre for å skrive ut antall brukere. Deretter, for hver bruker, utfører den to trinn: ett for å skrive ut indeksen og ett for å skrive ut brukeren.

Derfor kan funksjonen som best representerer antall beregningstrinn som er tatt, skrives som f(n) = 2 + 2n. Hvor n er antall brukere.

Vi går videre til trinn to, og velger det mest dominerende begrepet. 2n er et lineært ledd, og 2 er et konstantledd. Lineær er mer dominant enn konstant, så vi velger 2n, det lineære leddet.

Så vår funksjon er nå f(n) = 2n.

Det siste trinnet er å eliminere koeffisienter. I funksjonen vår har vi 2 som koeffisient. Så vi eliminerer det. Og funksjonen blir f(n) = n. Det er begrepet vi bruker mellom parentesene våre.

Derfor er tidskompleksiteten til algoritmen vår O(n) eller lineær kompleksitet.

Ulike Big O-kompleksiteter

Den siste delen i vårt Big O Cheat Sheet vil vise deg forskjellige kompleksiteter og tilhørende grafer.

#1. Konstant

Konstant kompleksitet betyr at algoritmen bruker en konstant mengde plass (når man utfører romkompleksitetsanalyse) eller et konstant antall trinn (når man utfører tidskompleksitetsanalyse). Dette er den mest optimale kompleksiteten ettersom algoritmen ikke trenger ekstra plass eller tid ettersom inngangen vokser. Den er derfor veldig skalerbar.

Konstant kompleksitet er representert som O(1). Det er imidlertid ikke alltid mulig å skrive algoritmer som kjører i konstant kompleksitet.

#2. Logaritmisk

Logaritmisk kompleksitet er representert ved begrepet O(log n). Det er viktig å merke seg at hvis logaritmebasen ikke er spesifisert i informatikk, antar vi at den er 2.

Derfor er log n log2n. Logaritmiske funksjoner er kjent for å vokse raskt først og deretter bremse ned. Dette betyr at de skalerer og jobber effektivt med stadig større antall n.

#3. Lineær

For lineære funksjoner, hvis den uavhengige variabelen skaleres med en faktor på p. Den avhengige variabelen skalerer med samme faktor p.

Derfor vokser en funksjon med en lineær kompleksitet med samme faktor som inngangsstørrelsen. Hvis inngangsstørrelsen dobles, vil antallet beregningstrinn eller minnebruk også gjøre det. Lineær kompleksitet er representert med symbolet O(n).

#4. Linearitmisk

O (n * log n) representerer linearitmiske funksjoner. Linearitmiske funksjoner er en lineær funksjon multiplisert med logaritmefunksjonen. Derfor gir en linearitmisk funksjon resultater litt større enn lineære funksjoner når log n er større enn 1. Dette er fordi n øker når multiplisert med et tall større enn 1.

Log n er større enn 1 for alle verdier på n større enn 2 (husk at log n er log2n). Derfor, for enhver verdi på n større enn 2, er linearitmiske funksjoner mindre skalerbare enn lineære funksjoner. Hvorav n er større enn 2 i de fleste tilfeller. Så linearitmiske funksjoner er generelt mindre skalerbare enn logaritmiske funksjoner.

#5. Kvadratisk

Kvadratisk kompleksitet er representert ved O(n2). Dette betyr at hvis inndatastørrelsen din øker med 10 ganger, øker antallet trinn som tas eller plass brukt med 102 ganger eller 100! Dette er lite skalerbart, og som du kan se av grafen, blåser kompleksiteten opp veldig raskt.

Kvadratisk kompleksitet oppstår i algoritmer der du løkker n ganger, og for hver iterasjon sløyfer du n ganger igjen, for eksempel i Bubble Sort. Selv om det generelt ikke er ideelt, har du til tider ikke noe annet valg enn å implementere algoritmer med kvadratisk kompleksitet.

#6. Polynom

En algoritme med polynomkompleksitet er representert ved O(np), der p er et konstant heltall. P representerer rekkefølgen der n heves.

Denne kompleksiteten oppstår når du har flere nestede løkker. Forskjellen mellom polynomkompleksitet og kvadratisk kompleksitet er kvadratisk er i størrelsesorden 2, mens polynom har et hvilket som helst tall større enn 2.

#7. Eksponentiell

Eksponentiell kompleksitet vokser enda raskere enn polynomkompleksitet. I Math er standardverdien for eksponentialfunksjonen konstanten e (Eulers tall). I informatikk er imidlertid standardverdien for eksponentialfunksjonen 2.

Eksponentiell kompleksitet er representert med symbolet O(2n). Når n er 0, er 2n 1. Men når n økes til 5, blåser 2n opp til 32. En økning i n med én vil doble det forrige tallet. Derfor er funksjoner av eksponentiell ikke veldig skalerbare.

#8. Faktoriell

Faktoriell kompleksitet er representert ved symbolet O(n!). Denne funksjonen vokser også veldig raskt og er derfor ikke skalerbar.

Konklusjon

Denne artikkelen dekket Big O-analyse og hvordan du beregner den. Vi diskuterte også de ulike kompleksitetene og diskuterte deres skalerbarhet.

Deretter vil du kanskje øve Big O-analyse på Python-sorteringsalgoritmen.