Ymmärrän matemaattisesti $ f (n) \ in O (g (n)) $: $ f (n) $ ei kasvaa nopeammin kuin $ g (n) $. Muodollisemmin, $ \ olemassa c, n_0 $ s.t. $ f (n) \ leq cg (n) \ kaikki n \ geq n_0 $.
Vastaavasti $ f (n) \ in \ Theta (g (n)) $ tarkoittaa, että $ f (n) $ kasvaa suunnilleen yhtä nopeasti kuin $ g (n) $. ts. $ f (n) \ O: ssa (g (n)), \ Omega (g (n)) $.
En ymmärrä, miksi ihmiset käyttävät isoa Oh: ta algoritmi? Pitäisikö meidän käyttää suurta Thetaa. Kun sanomme algoritmin ”käyntiaika”, tarkoitamme pahimman tapauksen käyntiaikaa, ts. $ T (n) = max \ {ALG (x): | x | = n \} $.
Joten, esim. lineaarisen haun pahin tapa-aika syötteellä, jonka koko on $ n $ ($ n $ -elementit ja kohde-arvo), on $ \ Theta (n) $ ja $ O (n) $, mutta $ \ Theta (n) $ antaa lisätietoja. Joten miksi algoritmikirjoissa käytetään $ O (n) $ eikä $ \ Theta (n) $.
Kommentit
- Usein se ' s, koska emme yksinkertaisesti voi ' saada tiukkaa iso-teeta-sidosta algoritmin käyntiaikaan. Jos algoritmi on riittävän monimutkainen, voi tapahtua, että paras mitä voimme tehdä, on sanoa, että juoksuaika on, sano $ O (n ^ {n!}) $, Missä todellisuudessa se voi olla $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Historialliset syyt.
- " Mitä en halua ' t saa, miksi ihmiset käyttävät suurta Ohia algoritmin käyntiaikana? Pitäisi ' t käyttää suurta Thetaa. " – Kyllä. Odota, älä, meidän pitäisi antaa vielä tarkempia lausuntoja. Mutta jos minun on valittava, kyllä, $ \ Theta $!
Vastaa
Näen kaksi syytä ihmiset pitävät paremmasta Big Ohista kuin Big Theta:
- Algoritmin ajonaikaisen monimutkaisuuden ei välttämättä määritellä olevan pahin tapa ajonaikaisen monimutkaisuuden. Saatat myös nähdä sen vain suoritusaikana mielivaltaisessa esimerkissä, jonka pituus on $ n $. Sitten, jos kirjoitat esimerkiksi, että algoritmin ajoaika $ t (n) $ on muodossa $ \ mathcal {O} (n ^ 2) $, tämä tarkoittaa, että mikä tahansa valitsemasi pituuden $ n $ syöttö, se kasvaa aina asymptoottisesti hitaampi kuin funktio $ c \ cdot n ^ 2 $ joillekin vakioille $ c $ – joten annamme sitten selvän ilmoituksen pahimmasta tapauksesta.
- Joskus kun analysoit ajonaikaa sellaisen algoritmin monimutkaisuus, jota et tiedä varmasti, onko antamasi pahimman tapauksen monimutkaisuus todella tiukka. Otetaan esimerkiksi matriisikertomuksen ajonaikinen monimutkaisuus . Siellä ei vieläkään ole selvää, onko ajonaikainen $ n ^ {2.3728639} $ todellakin pahin tapaus. Ja siten käyntiajan tiedetään olevan $ \ mathcal {O} (n ^ {2.3728639}) $, kun se on ” en ole varma, onko se $ \ Theta (n ^ {2.3728639}) $: ssa.
Mutta olet myös oikeassa, että joissakin tapauksissa olisi parempi antaa iso teeta sidottu kuin iso Oh sidottu.
Kommentit
- Mainos 1: Lukijat, ole varovainen olla lukematta liikaa siihen !
Vastaa
(Huolimaton) yläraja on helpompi todistaa kuin tiukka yläraja, puhumattakaan ylemmistä ja alemmista rajoista.
Jotkut algoritmit suorittamisaikaa eivät voi t annetaan samalla toiminnolla kuin ylä- / alaraja. Esimerkiksi. yksinkertaiset lajittelualgoritmit ovat $ O (n ^ 2) $, mutta niillä on alaraja $ \ Omega (n) $.
Jotkut vaativat pyrkimystä tuottaa suorituskykyä asymptoottisesti $ \ sim $, jossa $ f (n) \ sim g (n) $ jos
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(sanotaan keskiarvona tai pahimmassa tapauksessa joidenkin kriittisten operaatioiden lukumääränä, kuten vertailut lajittelussa). Eli, heiluta tilaa, mutta maton alle ei pyyhitty (mahdollisesti humongous) vakioita.
Kommentit
- Kun viitataan kohtaan " runtime ", tarkoitamme jotain parhaista juoksuaikoista, pahimmista tapauksista ja keskimääräisistä tapauksista. Esim.: Quicksortilla on $ \ Theta (n ^ 2) $ pahin tapa ajoaika ja $ \ Theta (n) $ paras tapa ajoaika. Asymptootit määritetään oikealla olevilla funktioilla.
Vastaus
Jos isoa-Thetaa voidaan käyttää isojen Voi, sitä tulisi käyttää, ellei se lisää tarpeettomia vaikeuksia ymmärtää. On joitain hienovaraisia tapauksia, joissa iso-Thetaa ei voida käyttää ison-Oh: n sijaan, esimerkiksi:
Harkitse seuraavaa ongelmaa: lajittele tasaisen pituiset taulukot. Ohjelma tämän ongelman ratkaisemiseksi voisi olla: jos matriisin pituus on pariton, poistu välittömästi, jos matriisin pituus on tasainen, tee kuplalajittelu. Mikä on tämän algoritmin huonoin tapa ajoaika?
Se on varmasti $ O (n ^ 2) $, mutta se EI ole $ \ Omega (n ^ 2) $ siinä mielessä $ \ Omega $ määritellään yleensä. Sen sijaan sen pahin tapa-aika on ”$ \ Omega (n ^ 2) $ äärettömän usein” niin sanotusti (varoitus: ei-standardi terminologia).
vastaus
Vastauksessa ”miksi algoritmikirjoissa käytetään iso-oh eikä Theta”:
Big-Oh käytetään pahimpien tapausten analysointiin ja Big-Omega vain parhaisiin tapauksiin. Mutta analysoimalla Big-Theta, puhumme molemmista Big-Oh & Big-Omegasta samanaikaisesti.
ts. Big-Thetalle on välttämätöntä, että Big-Oh == Big-Omega, muuten emme voi puhua Big-Thetasta.
Joten missä tahansa (kirja / mikä tahansa asiakirja) näet Big-Theta, ne antavat monimutkaisuuden molemmille Big-Oh & Big-Omegalle (ja molemmat ovat myös tasa-arvoisia) .Mutta monissa tapauksissa ne eivät ole tasa-arvoisia, niin käytämme vain Big- Voi vain pahimmassa tapauksessa.