Big O Notation

Big O Notation on viis algoritmide võrdlemiseks. See võrdleb neid, arvutades, kui palju mälu on vaja ja kui palju aega kulub selleks.

Big O märkust kasutatakse sageli probleemi keerukuse määramisel, mida nimetatakse ka probleemi keerukusklassiks. Matemaatik Paul Bachmann (1837-1920) oli esimene, kes kasutas seda märkust oma raamatu "Analytische Zahlentheorie" teises väljaandes 1896. aastal. Edmund Landau (1877-1938) tegi selle notatsiooni populaarseks. Seetõttu viidatakse Landau sümbolitest rääkides sellele notatsioonile.

Big O Notation on nime saanud termini "funktsiooni järjestus" järgi, mis viitab funktsioonide kasvule. Big O notatsiooni kasutatakse funktsiooni kasvukiiruse ülemise piiri (suurima võimaliku summa) leidmiseks, mis tähendab, et see arvutab välja pikima aja, mis kulub sisendi muutmiseks väljundiks. See tähendab, et algoritmi saab rühmitada selle järgi, kui kaua tal võib kuluda halvimal juhul, kui iga kord võetakse kõige pikem tee.

Big O on väljend, mis leiab halvima stsenaariumi tööaja, näidates, kui tõhus on algoritm, ilma et programmi peaks arvutis käivitama. See on kasulik ka seetõttu, et erinevatel arvutitel võib olla erinev riistvara ja seetõttu kulub selleks erinevalt palju aega. Kuna Big O eeldab alati halvimat juhtumit, saab see näidata järjekindlat kiiruse mõõtmist: sõltumata riistvarast, O ( 1 ) {\displaystyle O(1)} $O(1)$ lõpetab alati kiiremini kui O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , sest nende tõhusus on erinev.

Näited

Järgnevad näited kasutavad kõik Pythonis kirjutatud koodi. Pange tähele, et see ei ole täielik nimekiri Big O tüüpidest.

Pidev

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Võtab alati sama palju aega, olenemata sisendist. Võtame näiteks funktsiooni, mis võtab vastu täisarvu (nimega x) ja tagastab selle kahekordse väärtuse:

def double(x): return x * 2 #Return the value of x times 2

Pärast sisendi vastuvõtmist teeb see funktsioon alati ühe sammu, et tagastada väljund. See on konstantne, sest see võtab alati sama palju aega, seega on see O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineaarne

O ( n ) {\displaystyle O(n)} $O(n)$ . Suureneb vastavalt sisendi suurusele, mida esindab n {\displaystyle n} . Oletame, et funktsioon võtab vastu n ja tagastab iga arvu 1 kuni n:

def count(n): i = 1 #Loo loendur nimega "i" väärtusega 1 while i <= n: #While i on väiksem või võrdne n-ga print(i) #Trükki i väärtus i = i + 1 #Redefineeri i kui "väärtus i + 1"

Kui me sisestaksime väärtuse 5, siis oleks väljundiks 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} $1,2,3,4,5$ , mis nõuab 5 tsüklit. Samamoodi, kui me sisestaksime 100, annaks see tulemuseks 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , mis nõuab 100 tsüklit. Kui sisend on n {\displaystyle n}, siis on algoritmi tööaeg iga kord täpselt n {\displaystyle n} silmust, seega on see O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktorija

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Suureneb faktoriaalselt, mis tähendab, et ajakulu suureneb massiivselt koos sisendiga. Näiteks ütleme, et soovime külastada viit linna üle maailma ja tahame näha kõiki võimalikke järjestusi (permutatsioone). Algoritm, mille võiksime kirjutada Pythoni itertools raamatukogu kasutades, on järgmine:

import itertools #Import itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Massiivi meie valitud linnadest def permutations(cities): #Võttes sisendiks linnade massiivi: for i in itertools. permutations(cities): #Kõigi meie elementide permutatsiooni jaoks (määratud muutujale "i") print(i) #väljund i

See algoritm arvutab iga meie linnade unikaalse permutatsiooni ja seejärel väljastab selle. Näited väljunditest on järgmised:

("London", "Pariis", "Berliin", "Amsterdam", "Rooma") ("London", "Pariis", "Berliin", "Rooma", "Amsterdam") ("London", "Pariis", "Amsterdam", "Berliin", "Rooma") ... ("Rooma", "Amsterdam", "Pariis", "Berliin", "London") ("Rooma", "Amsterdam", "Berliin", "London", "Pariis") ("Rooma", "Amsterdam", "Berliin", "Pariis", "London")

Siin on meie sisestusnimekiri 5 elementi pikk ja iga valiku puhul vähenevad meie ülejäänud valikud 1 võrra. Teisisõnu, meie 5 sisendit valivad 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elementi (või 5 ! {\displaystyle 5!} $5!$ ). Kui meie sisend on n {\displaystyle n} linna pikkune, siis on väljundite arv n ! {\displaystyle n! } $n!$ ; teisisõnu, eeldades, et me läbime iga permutatsiooni, vajame selle lõpetamiseks O ( n ! ) {\displaystyle O(n!)} $O(n!)$ silmust.

Little-o Notation

Big O rangem versioon on little-o. Suure O ja little-o erinevus seisneb selles, et little-o on range ülempiir: kui O ( n ) {\displaystyle O(n)} $O(n)$ tähendab, et lõpetamise aeg suureneb sisendi suuruse põhjal selle maksimumini, siis o ( n ) {\displaystyle o(n)} $o(n)$ tähendab, et lõpetamise aeg jääb üldiselt alla selle aja. Teisisõnu, Big O eeldab, et iga silmus kulgeb kõige pikemat teed ja protsess võtab võimalikult kaua aega, samas kui little-o on tegeliku tööaja suhtes realistlikum; kui silmuste arv põhineb 6-kandilise täringu viskamisel, siis Big O eeldab alati, et viskatakse 6, samas kui little-o arvestab teiste numbrite viskamise võrdse tõenäosusega.

Küsimused ja vastused

K: Mis on Big O märkimine?

V: Big O notatsioon on viis erinevate funktsioonide kasvukiiruste võrdlemiseks, mida kasutatakse sageli erinevate algoritmide tõhususe võrdlemiseks, arvutades, kui palju mälu ja aega kulub nende täitmiseks. Seda saab kasutada ka selleks, et määrata, kui keeruline on probleem.

K: Kes kasutas seda notatsiooni esimesena?

V: Matemaatik Paul Bachmann (1837-1920) kasutas seda notatsiooni esimesena oma 1896. aastal ilmunud raamatus "Analytische Zahlentheorie".

K: Mida tähendab suur O?

V: Big O tähistab "funktsiooni järjestust", mis viitab funktsioonide kasvukiirusele.

K: Kuidas kasutatakse Big O-d?

V: Big O tähistust kasutatakse funktsiooni kasvukiiruse ülemise piiri (suurima võimaliku summa) leidmiseks, mis tähendab, et see arvutab välja pikima aja, mis kulub sisendi muutmiseks väljundiks. See tähendab, et algoritme saab rühmitada selle järgi, kui kaua neil kulub halvimal juhul, kus iga kord võetakse kõige pikem tee.

K: Mis on Landau sümbolid?

V: Landau sümbolid viitavad Big O notatsioonile, mis on nimetatud Edmund Landau (1877-1938) järgi, kes tegi selle notatsiooni populaarseks.

K: Miks on Big O kasulik?

V: Big O võimaldab meil mõõta kiirust, ilma et peaksime programme arvutites käivitama, kuna see eeldab alati halvimat stsenaariumi, mis teeb selle järjepidevaks sõltumata arvutite vahelistest riistvaralistest erinevustest. Samuti näitab see, kui tõhus on algoritm, ilma et seda tegelikult arvutis käivitataks.