Koks skirtumas tarp Θ (n) ir O (n)?

Kartais matau n (n) keistą simbolį Θ su kažkuo tarp ir kartais tik O (n). Ar tai tiesiog pernelyg tingus, nes niekas nežino, kaip rašyti šį simbolį, ar tai reiškia kažką kito?

348
23 янв. martinus set on Jan 23 2009-01-23 01:58 '09 ne 1:58 2009-01-23 01:58
@ 9 atsakymai

Trumpas paaiškinimas:

Jei algoritmas turi Θ (g (n)) reikšmę, tai reiškia, kad algoritmo veikimo laikas, kai padidėja n (įvesties dydis), yra proporcingas g (n).

Jei algoritme yra O (g (n)), tai reiškia, kad algoritmo veikimo laikas, kai padidėja n, yra ne daugiau kaip proporcingas g (n).

Paprastai, net kai žmonės kalba apie O (g (n)), jie iš tikrųjų reiškia Θ (g (n)), bet techniškai yra skirtumas.


Daugiau techniškai:

O (n) reiškia viršutinę ribą. Θ (n) reiškia kietą rišimą. N (n) yra apatinė riba.

f (x) = (g (x)), jei f (x) = O (g (x)) ir f (x) = Ω (g (x))

Pavyzdžiui, viršutinė naivaus rekursinio metodo riba apskaičiuojant Fibonacci seką:

Fib (x) = O (2 n )

tačiau griežtas įvertinimas

Fib (x) = Θ (Fn), kur Fn yra Fibonacci seka.

kuri taip pat yra galiojanti viršutinė riba.

Iš esmės, kai sakome, kad algoritmas turi O (n), jis taip pat yra O (n 2 ), O (n 1000000 ), O (2 n ), bet algoritmas Θ (n) nėra (n 2 ) .

Iš tiesų, kadangi f (n) = Θ (g (n)) reiškia, kad pakankamai didelėms n, f (n) gali būti susietos su c 1 g (n) ir c 2 g (n) kai kurioms c 1 reikšmėms . ir c2, t.y. augimo greitis f yra asimptotiškai lygus g: g gali būti apatinė riba ir viršutinė riba f. Tai tiesiogiai reiškia, kad f gali būti apatinė riba ir viršutinė riba. Todėl

f (x) = (g (x)), jei g (x) = (f (x))

Panašiai, norint parodyti f (n) = Θ (g (n)), pakanka parodyti, kad g yra f viršutinė riba (t.y. f (n) = O (g (n))) ir f yra apatinė riba g (t.y. f (n) = Ω (g (n)), kuri yra tokia pati kaip g (n) = O (f (n))). Lakoniškas

f (x) = (g (x)), jei f (x) = O (g (x)) ir g (x) = O (f (x))


Taip pat yra nedidelis ooo ir mažas omega ( ω ), žymintis laisvas viršutines ir laisvas apatines funkcijų ribas.

Apibendrinant:

f(x) = O(g(x)) (big-oh) reiškia, kad augimo greitis f(x) yra asimptotiškai mažesnis arba lygus augimo greičiui g(x) .

f(x) = Ω(g(x)) (big-omega) reiškia, kad augimo greitis f(x) yra asimptotiškai didesnis arba lygus augimo greičiui g(x)

f(x) = O(g(x)) (mažas-oh) reiškia, kad augimo greitis f(x) yra asimptotiškai mažesnis nei augimo greitis g(x) .

f(x) = ω(g(x)) (žemas omega) reiškia, kad augimo greitis f(x) yra asimptotiškai didesnis už augimo greitį g(x)

f(x) = Θ(g(x)) (teta) reiškia, kad augimo greitis f(x) yra asimptotiškai lygus augimo greičiui g(x)

Dėl išsamesnės diskusijos galite perskaityti „Wikipedia“ apibrėžimą arba kreiptis į klasikinį vadovėlį, pvz., „Cormen“ ir kitų „Įvadas į algoritmus“.

512
23 янв. Mehrdad Afshari atsakymas dėl sausio 23 d 2009-01-23 02:00 '09, 2:00 2009-01-23 02:00

Yra paprastas būdas (manau, apgauti) prisiminti, ką reiškia.

Visi „Big-O“ ženklai gali būti laikomi turinčiais barą.

Žvelgiant į Ω, juosta yra apačioje, todėl tai yra (asimptotinė) apatinė riba.

Žiūrint į Θ skydelį, akivaizdu, kad jis yra viduryje. Taigi tai yra (asimptotinė) griežta riba.

Rašydami „O“, jūs paprastai baigsite aukščiau ir piešiate kokteilį. Todėl O (n) yra viršutinė funkcijos riba. Kad tai būtų teisinga, tai neveikia su daugeliu šriftų, tačiau tai yra pirminis pavadinimų pagrindimas.

272
23 янв. Andrei Krotkovo atsakymas dėl sausio 23 d 2009-01-23 03:50 '09, 3:50, 2009-01-23 03:50

vienas yra didelis „O“

vienas yra Big Theta

http://en.wikipedia.org/wiki/Big_O_notation

Didelis O reiškia, kad jūsų algoritmas veiks ne daugiau kaip nurodyta išraiška (n ^ 2)

„Big Omega“ reiškia, kad jūsų algoritmas veiks ne mažiau nei šiame išraiška (n ^ 2)

Jei tos pačios išraiškos atveju abi sąlygos yra teisingos, galite naudoti daugiau teta žymėjimo.

50
23 янв. Atsakymas pateikiamas l_39217_l sausio 23 d 2009-01-23 02:01 '09 2:01 am 2009-01-23 02:01

Užuot pateikęs teorinę apibrėžtį, kuri čia gražiai aprašyta, pateiksiu paprastą pavyzdį:

Tarkime, kad vykdymo laikas f(i) yra O(1) . Žemiau yra kodo fragmentas, kurio asimptotinis vykdymo laikas yra Θ(n) . Jis visada vadina funkciją f(...) n kartus. Apatinė ir viršutinė riba n.

 for(int i=0; i<n; i++){ f(i); } 

Antrasis kodo fragmentas turi asimptotinį vykdymo laiką O(n) . Jis vadina funkciją f(...) ne daugiau kaip n kartus. Viršutinė riba yra n, bet apatinė riba gali būti Ω(1) arba Ω(log(n)) , priklausomai nuo to, kas vyksta f2(i) viduje.

 for(int i=0; i<n; i++){ if( f2(i) ) break; f(i); } 
30
27 сент. atsakymas suteikiamas kara deniz 27 sep. 2012-09-27 22:17 '12 10:17 val. 2012-09-27 22:17

Grafikas gali padėti suprasti ankstesnius atsakymus:

Θ - Pavadinimas - ta pati tvarka O-žymėjimas - viršutinė riba

2019

8
20 мая '15 в 7:17 2015-05-20 07:17 atsakymą įteikė Ricardo gegužės 15 d. 15 val. 07:17 2015-05-20 07:17

Pagalvokite, kad Theta = afunction kaip etiketė, sakydamas Big-O = afunction IR Omega = afunction

Kai didelės O funkcijos ir Omega funkcijos yra tos pačios, Theta yra sutrumpintas būdas nurodyti šią konkrečią situaciją.

Taigi, jei sakote, kad Theta = some expression , vis dar teisinga pasakyti O = some expression ir Omega = some expression . Vienintelis skirtumas yra tas, kad Theta = some expression turi daugiau informacijos.


Apytikslė analogija:

O sako, kad "gyvūnas yra mažesnis arba lygus 5 kojoms." Omega sako, kad "gyvūnas turi daugiau kaip 5 kliūtis."

Theta yra panaši į tai, kad „gyvūnas turi 5 kojeles“.

Kitaip tariant, jei gyvūnui yra 5 kojos (Theta), tokie teiginiai yra teisingi:

  • gyvūnas turi 5 ar mažiau kojų. (O)
  • gyvūnas turi 5 ar daugiau kojų. (Omega)

Turėkite omenyje, kad išraiškos nebūtinai yra specifiniai skaičiai, bet skirtingų dydžių funkcijos (log (n), n, n ^ 2 ir tt).

7
07 янв. atsakymas pateikiamas ahnbizcad 07 jan. 2015-01-07 09:58 '15 at 9:58 2015-01-07 09:58

f(n) priklauso O(n) jei yra teigiamas k kaip f(n)<=k*n

f(n) priklauso Θ(n) jei yra teigiamas k1 , k2 kaip k1*n<=f(n)<=k2*n

Vikipedijos straipsnis apie „Big O“ žymėjimą

5
23 янв. vartotojo54579 atsakymas 2009-01-23 02:04 '09, 02:04 2009-01-23 02:04

Naudokite ribas

Apsvarstykite f(n) > 0 ir g(n) > 0 visiems n . Tai normalu, nes greičiausias algoritmas turi bent vieną operaciją ir užbaigia jo vykdymą po paleidimo. Tai supaprastina skaičiavimą, nes vietoj absoliučios vertės ( |f(n)| ) galime naudoti vertę ( f(n) ).

  • f(n) = O(g(n))

    Bendrieji:

      f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n) 

    g(n) = n :

      f(n) 0 ≤ lim ──────── < ∞ n➜∞ n 

    <strong> Pavyzdžiai:

      Expression Value of the limit ------------------------------------------------ n = O(n) 1 1/2*n = O(n) 1/2 2*n = O(n) 2 n+log(n) = O(n) 1 n = O(n*log(n)) 0 n = O(n²) 0 n = O(nⁿ) 0 

    Kontekstiniai pavyzdžiai:

      Expression Value of the limit ------------------------------------------------- n ≠ O(log(n)) ∞ 1/2*n ≠ O(sqrt(n)) ∞ 2*n ≠ O(1) ∞ n+log(n) ≠ O(log(n)) ∞ 
  • f(n) = Θ(g(n))

    Bendrieji:

      f(n) 0 < lim ──────── < ∞ n➜∞ g(n) 

    g(n) = n :

      f(n) 0 < lim ──────── < ∞ n➜∞ n 

    <strong> Pavyzdžiai:

      Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1 

    Kontekstiniai pavyzdžiai:

      Expression Value of the limit ------------------------------------------------- n ≠ Θ(log(n)) ∞ 1/2*n ≠ Θ(sqrt(n)) ∞ 2*n ≠ Θ(1) ∞ n+log(n) ≠ Θ(log(n)) ∞ n ≠ Θ(n*log(n)) 0 n ≠ Θ(n²) 0 n ≠ Θ(nⁿ) 0 
2
27 янв. Atsakymas pateikiamas ROMANIA_engineer sausio 27 d 2016-01-27 11:14 '16 at 11:14 2016-01-27 11:14

Išvada: mes laikome didelius O, didelius θ ir didelius Ω kaip vieną ir tą patį.

Kodėl Aš paaiškinsiu šią priežastį:

Pirma, paaiškinsiu vieną neteisingą teiginį, kai kurie mano, kad mums reikia tik blogiausio laiko, todėl mes visuomet naudojame didelį O, o ne didelį θ. Sakau, kad šis žmogus yra šūdas. Viršutinės ir apatinės ribos naudojamos apibūdinti vieną funkciją, kuri nėra naudojama laiko sudėtingumui apibūdinti. Blogiausia laiko funkcija turi viršutines ir apatines ribas; geriausia laiko funkcija taip pat turi viršutines ir apatines ribas.

Norėdami aiškiai paaiškinti ryšį tarp didelių O ir didelių θ, paaiškinsiu ryšį tarp didelių O ir mažų o pirmųjų. Iš apibrėžimo lengva suprasti, kad mažas o yra didelės O pogrupis. Pavyzdžiui:

T (n) = n ^ 2 + n, galime pasakyti, kad T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4) . Tačiau mažiems o T (n) = o (n ^ 2) neatitinka mažos o apibrėžties. Taigi T (n) = o (n ^ 3), T (n) = o (n ^ 4) tinka mažiems o. Rezervas T (n) = O (n ^ 2) yra kas? Tai didelis θ!

Apskritai, mes sakome, kad didelis O yra O (n ^ 2), mažai tikėtina, kad T (n) = O (n ^ 3), T (n) = O (n ^ 4). Kodėl? Kadangi mes laikome didelius O kaip didelius θ nesąmoningai.

Panašiai mes taip pat žiūrime į didelį Ω kaip didelį θ nesąmoningai.

Trumpai tariant, dideli O, dideli large ir dideli Ω nėra vienodi iš apibrėžimų, bet jie yra vienodi mūsų burnoje ir smegenyse.

2
30 нояб. atsakymas pateikiamas haibo cu . 2016-11-30 21:22 '16 at 21:22 pm 2016-11-30 21:22