Big O" užrašas -

"Big O" užrašas - tai algoritmų palyginimo būdas. Jis juos lygina apskaičiuodamas, kiek atminties reikia ir kiek laiko užtrunka algoritmo įgyvendinimas.

Didysis O užrašas dažnai naudojamas nustatant, kokia sudėtinga yra problema, dar vadinama problemos sudėtingumo klase. Matematikas Paulas Bachmannas (1837-1920) pirmasis panaudojo šią notaciją 1896 m. antrajame savo knygos "Analytische Zahlentheorie" leidime. Šį užrašą išpopuliarino Edmundas Landau (1877-1938). Dėl šios priežasties, kai kalbama apie Landau simbolius, turima omenyje ši notacija.

"Big O" užrašas pavadintas pagal terminą "funkcijos tvarka", kuris reiškia funkcijų augimą. Big O užrašas naudojamas funkcijos augimo greičio viršutinei ribai (didžiausiam įmanomam dydžiui) rasti, t. y. nustatomas ilgiausias laikas, per kurį įvestis bus paversta išvestimi. Tai reiškia, kad algoritmą galima sugrupuoti pagal tai, kiek laiko jis gali užtrukti blogiausiu atveju, kai kiekvieną kartą bus pasirinktas ilgiausias kelias.

"Big O" - tai išraiška, kuria nustatomas blogiausio scenarijaus vykdymo laikas, parodantis, koks yra algoritmo efektyvumas, nepaleidžiant programos kompiuteryje. Tai naudinga ir todėl, kad skirtinguose kompiuteriuose gali būti skirtinga techninė įranga, todėl jai atlikti gali prireikti skirtingo laiko. Kadangi "Big O" visada numato blogiausią atvejį, galima nuosekliai išmatuoti greitį: nepriklausomai nuo jūsų techninės įrangos, "O ( 1 )" {\displaystyle O(1)} $O(1)$ visada bus baigtas greičiau nei "O ( n ! )" {\displaystyle O(n!)}, $O(n!)$ nes jų efektyvumas skiriasi.

Pavyzdžiai

Visuose toliau pateikiamuose pavyzdžiuose naudojamas "Python" kalba parašytas kodas. Atkreipkite dėmesį, kad tai nėra išsamus "Big O" tipų sąrašas.

Nuolatinis

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Visada užtrunka tiek pat laiko, nepriklausomai nuo įvesties. Pavyzdžiui, paimkime funkciją, kuri priima sveikąjį skaičių (vadinamą x) ir grąžina dvigubą jo vertę:

def double(x): return x * 2 #Grąžinama x vertė, padauginta iš 2

Priėmusi įvestį, ši funkcija visada atliks vieną žingsnį, kad grąžintų išvestį. Jis yra pastovus, nes visada užtruks tiek pat laiko, taigi jis yra O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linijinis

O ( n ) {\displaystyle O(n)} $O(n)$ . Padidėja priklausomai nuo įvesties dydžio, išreikšto n {\displaystyle n} . Tarkime, kad funkcija priima n ir grąžina kiekvieną skaičių nuo 1 iki n:

def count(n): i = 1 #Sukurkite skaitiklį, pavadintą "i", kurio reikšmė yra 1 while i <= n: #Kol i yra mažesnis arba lygus n print(i) #Spausdinkite i reikšmę i = i + 1 #Nustatykite i kaip "i + 1 reikšmę"

Jei įvestume vertę 5, tuomet būtų išvedama 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,3,4,5} $1,2,3,4,5$ , o tam, kad būtų užbaigti 5 ciklai, reikia 5 ciklų. Panašiai, jei įvestume 100, būtų išvesta 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , todėl reikėtų atlikti 100 ciklų. Jei įvestis yra n {\displaystyle n}, algoritmo veikimo laikas kiekvieną kartą yra lygiai n {\displaystyle n} ciklų, todėl jis yra O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktorinis

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Didėja faktoriniais dydžiais, o tai reiškia, kad laiko sąnaudos didėja kartu su įvesties dydžiu. Pavyzdžiui, tarkime, norime aplankyti penkis pasaulio miestus ir norime pamatyti visus įmanomus išsidėstymus (permutacijas). Algoritmas, kurį galėtume parašyti naudodami Python itertools biblioteką, yra toks:

import itertools #Importuokite itertools biblioteką cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Mūsų pasirinktų miestų masyvas def permutations(cities): #Kaip įvestį imant miestų masyvą: for i in itertools. permutations(cities): #Kiekvienai mūsų elementų permutacijai (priskirtai kintamajam "i") print(i) #Išėjimas i

Šis algoritmas apskaičiuos kiekvieną unikalią mūsų miestų permutaciją ir ją išves. Išvesties pavyzdžiai bus tokie:

("Londonas", "Paryžius", "Berlynas", "Amsterdamas", "Roma") ("Londonas", "Paryžius", "Berlynas", "Roma", "Amsterdamas") ("Londonas", "Paryžius", "Amsterdamas", "Berlynas", "Roma") ... ("Roma", "Amsterdamas", "Paryžius", "Berlynas", "Londonas") ("Roma", "Amsterdamas", "Berlynas", "Londonas", "Paryžius") ("Roma", "Amsterdamas", "Berlynas", "Paryžius", "Londonas")

Šiuo atveju mūsų įvesties sąrašas yra 5 elementų ilgio, o su kiekvienu pasirinkimu mūsų likusios galimybės sumažėja 1. Kitaip tariant, mūsų 5 įvestys pasirenka 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elementų (arba 5 ! {\displaystyle 5!} $5!$ ). Jei mūsų įvestis yra n {\displaystyle n} miestų ilgio, tai išėjimų skaičius yra n ! {\displaystyle n! } $n!$ ; kitaip tariant, jei pereisime per kiekvieną permutaciją, reikės O ( n ! ) {\displaystyle O(n!)} $O(n!)$ ciklų, kad ją užbaigtume.

Little-o užrašas

Griežtesnė "Didžiojo O" versija yra "little-o". Skirtumas tarp big O ir little-o yra tas, kad little-o yra griežta viršutinė riba: nors O ( n ) {\displaystyle O(n)} reiškia, kad $O(n)$ užbaigimo laikas, atsižvelgiant į įvesties dydį, padidės iki šios maksimalios ribos, o ( n ) {\displaystyle o(n)} reiškia, kad $o(n)$ užbaigimo laikas paprastai neviršys šios ribos. Kitaip tariant, Big O daro prielaidą, kad kiekviena kilpa eis ilgiausiu keliu ir procesas užtruks kuo ilgiau, o little-o realiau vertina faktinį vykdymo laiką; jei kilpų skaičius grindžiamas šešiabriaunio kauliuko metimu, Big O visada darys prielaidą, kad iškrito 6, o little-o atsižvelgs į vienodą tikimybę, kad iškrito kiti skaičiai.

Klausimai ir atsakymai

K: Kas yra "Big O" užrašas?

A: Didžioji O notacija - tai būdas palyginti skirtingų funkcijų augimo tempus, dažnai naudojamas skirtingų algoritmų efektyvumui palyginti, apskaičiuojant, kiek atminties ir laiko reikia jiems atlikti. Jis taip pat gali būti naudojamas nustatyti, kiek sudėtinga yra problema.

Klausimas: Kas pirmasis panaudojo šį užrašą?

A: Matematikas Paulas Bachmannas (1837-1920) 1896 m. savo knygoje "Analytische Zahlentheorie" pirmasis panaudojo šį užrašą.

K: Ką reiškia "Big O"?

A: Big O reiškia "funkcijos tvarką", kuri reiškia funkcijų augimo greitį.

K: Kaip naudojamas Big O?

A: Big O užrašas naudojamas funkcijos augimo greičio viršutinei ribai (didžiausiam įmanomam dydžiui) rasti, t. y. nustatomas ilgiausias laikas, per kurį įvestis virsta išvestimi. Tai reiškia, kad algoritmus galima sugrupuoti pagal tai, kiek laiko jie užtrunka blogiausiu atveju, kai kiekvieną kartą bus pasirinktas ilgiausias kelias.

K: Kas yra Landau simboliai?

A: Landau simboliai reiškia "Big O" notaciją, pavadintą Edmundo Landau (1877-1938), kuris išpopuliarino šią notaciją, vardu.

K: Kodėl Big O yra naudingas?

A:Big O leidžia mums matuoti greitį nepaleidžiant programų kompiuteriuose, nes jis visada numato blogiausius scenarijus, todėl yra nuoseklus, nepriklausomai nuo kompiuterių techninės įrangos skirtumų. Jis taip pat parodo, koks yra algoritmo efektyvumas, nereikalaujant, kad jis būtų paleistas kompiuteryje.