Skirtumas tarp Big-O ir Little-O pastabų

Koks yra skirtumas tarp Big-O O(n) ir Small-O O(n) žymėjimo?

219
01 сент. nustatė Jeffrey Lott 01 Sep 2009-09-01 23:22 '09, 11:22 AM 2009-09-01 23:22
@ 3 atsakymai

f ∈ O (g) iš esmės sako

Mažiausiai vienai pastoviai k> 0 pasirinkimui galite rasti pastovią a, kad nelygybė 0 <= f (x) <= kg (x) tinka visiems x> a.

Atkreipkite dėmesį, kad O (g) yra visų funkcijų, kurioms ši sąlyga yra įvykdyta, rinkinys.

f ∈ o (g) iš esmės sako

Kiekvienam pastovaus k> 0 pasirinkimui galite rasti pastovumą a, kad nelygybė 0 <= f (x) <kg (x) tinka visiems x> a.

Dar kartą atkreipkite dėmesį, kad o (g) yra rinkinys.

„Big-O“ atveju reikia rasti tik tam tikrą veiksnį k, kurio nelygybė yra įvykdyta už tam tikro minimalaus x.

„Little-o“ turėtų būti, kad yra minimalus x, po kurio nelygybė laikoma, nesvarbu, kiek mažai jūs k, jei jis nėra neigiamas ar nulis.

Abi jos apibūdina viršutines ribas, nors šiek tiek priešais intuityvumą, Little-o yra tvirtesnis teiginys. Tarp augimo greičių f ir g, jei f ∈ o (g), yra daug didesnis skirtumas nei f ∈ O (g).

Vienas iš skirtumų yra toks: f ∈ O (f) yra teisinga, bet f ∈ o (f) nėra tiesa. Todėl Big-O gali būti laikoma "f ∈ O (g) reiškia, kad f asimptotinis augimas nėra greitesnis nei g", o "f ∈ o (g) reiškia, kad f asimptotinis augimas yra griežtai lėčiau nei g". Tai tarsi <= palyginti su < .

Visų pirma, jei g (x) vertė yra pastovus f (x) vertės daugiklis, tada f ∈ O (g) yra tiesa. Štai kodėl galite nustatyti konstantas, kai dirbate su pastabomis su dideliais išėjimais.

Tačiau, jei f ∈ o (g) yra teisinga, tuomet g savo formoje turėtų įeiti didesnis x laipsnis, todėl santykinis f (x) ir g (x) atskyrimas turėtų iš tikrųjų didėti, kai x padidėja.

Naudokite tik matematinius pavyzdžius (o ne nurodykite algoritmus):

Big-O atveju šios reikšmės yra teisingos, tačiau tai nėra tiesa, jei naudojote mažai:

  • x ^ 2 ∈ O (x ^ 2)
  • x ^ 2 ∈ O (x ^ 2 + x)
  • x ^ 2 ∈ O (200 * x ^ 2)

„Little-o“ atveju teisinga:

  • x ^ 2 ∈ o (x ^ 3)
  • x ^ 2 ∈ o (x!)
  • ln (x) ∈ o (x)

Atkreipkite dėmesį, kad jei f ∈ o (g), tai reiškia, kad f ∈ O (g). pavyzdžiui, x ^ 2 ∈ o (x ^ 3), tai taip pat tiesa, kad x ^ 2 ∈ O (x ^ 3) (dar kartą nustatėme O kaip <= ir o kaip < )

288
01 сент. Atsakymą pateikė Tyler McHenry rugsėjo 1 d 2009-09-01 23:32 '09 ne 23:32 2009-09-01 23:32

Big-O - šiek tiek ir - < . Big-O yra visa apimanti viršutinė riba, o mažoji-o yra griežta viršutinė riba.

Pavyzdžiui, funkcija f(n) = 3n :

  • O(n^2) , O(n^2) ir O(n)
  • ne O(lg n) , O(lg n) arba O(n)

Panašiai ir numeris 1 lygus:

  • ≤ 2 , < 2 ir ≤ 1
  • ne ≤ 0 , < 0 arba < 1

Čia yra lentelė, rodanti bendrą idėją:

2019

132
01 сент. atsakymas, kurį pateikė Craig Gidney Sep 01 2009-09-01 23:50 '09, 23:50, 2009-09-01 23:50

Manau, kad kai negaliu konceptualiai suprasti kažko, galvoju apie tai, kodėl naudojote X, naudinga suprasti X. (Negalima pasakyti, kad jūs to nepadarėte, aš tiesiog užmezgau sceną.)

[žinoma medžiaga]. Įprastas algoritmų klasifikavimo būdas yra runtime ir, atsižvelgiant į Big-Oh algoritmo sudėtingumą, galite gauti gana gerą įvertinimą, kuris iš jų yra „geresnis“ - priklausomai nuo mažiausios „funkcijos“ O! Net realiame pasaulyje, O ( N) yra „geriau“ nei O (N ^ 2), uždraudžiant kvailiems dalykams, pvz., Supermazinėms konstantoms ir tt [/ Medžiaga, kurią žinote]

Tarkime, yra algoritmas, kuris veikia O (N). Gana gera? Bet leiskite man pasakyti, kad jūs (jūs esate puikus žmogus, jūs) atėjote į algoritmą, kuris veikia O (N / logloglogN). Hurray! Greičiau! Bet jūs būsite kvaili rašyti jį dar kartą ir vėl, kai rašysite disertaciją. Todėl jūs jį rašote vieną kartą, ir galite pasakyti: "Šiame straipsnyje aš įrodiau, kad X algoritmas, anksčiau apskaičiuotas O (N) metu, iš tikrųjų yra apskaičiuojamas o (n)."

Taigi, visi žino, kad jūsų algoritmas yra greitesnis - kaip neaišku, bet jis jį žino greičiau. Teoriškai :)

20
02 сент. Atsakymas pateiktas agorenst 02 Sep. 2009-09-02 07:53 '09 at 7:53 AM 2009-09-02 07:53