Keskustelu:Asymptoottinen suoritusaika

Wikipediasta
Siirry navigaatioon Siirry hakuun

Voisiko tästä tehdä hiukan yleistajuisemman, mihin tätä käytetään jne.--Teveten 17. tammikuuta 2006 kello 18.48 (UTC)

Lisäsin asymptoottisen rajan määritelmän ja esimerkin, jonka pitäisi selventää asymptoottisen rajan merkitystä. Mandariini 15. tammikuuta 2007 kello 10.18 (UTC)

Ordo versus iso-O versus O-notaatio[muokkaa wikitekstiä]

Kutsutaanko tuota todella Suomessa ordo-notaatioksi ja miksi niin? Mitä olen nähnyt, niin suomenkielinen oppimateriaali yleensä joko ei ota kantaa nimitykseen tai mainitsee englannin kielessä yleisimmän termin big O notation, iso-O-notaatio. Neutraalein ilmaus olisi varmaankin O-notaatio tai O-merkintä. --Anurmi 5. helmikuuta 2008 kello 16.29 (UTC)

Yleisesti noin suunnilleen ihan kaikkialla puhutaan iso-O -notaatiosta (engl. big O notation). Ordo on varmaankin virheellinen väännös sanasta Ordnung (suom. järjestys), josta O on otettu. Bachmann-Landau -notaatio olisi periaatteessa korrekti, mutta iso-O on de facto käytetty nimi. Huom: epäilen, että suomenkieliset tekstit ovat ottaneet "ordo-notaation" fi-wikistä virheellisesti, en löydä järkevää lähdettä joka edeltäisi wikiin tehtyä tekstiä. Ipr1 (keskustelu) 23. kesäkuuta 2022 kello 16.43 (EEST)[vastaa]

Paljon korjattavaa[muokkaa wikitekstiä]

Artikkelissa puhutaan jatkuvasti notaatiosta, mikä on turhaa: olisi parempi puhua notaation merkityksestä eli asymptoottisesta suoritusajasta. "Ordo-merkintä kuvastaa pahinta mahdollista tapausta. − − Ordo-notaatiolla jätetään syötteen aiheuttama suoritusajan vaihtelu huomiotta, ja keskitytään vain pahimpaan mahdolliseen tapaukseen..." Tämä on virheellistä tietoa! Se ei aina kuvaa pahinta mahdollista tapausta, ja asymptoottinen suoritusaika on nimenomaan verrannollinen syötteeseen.

O kuvaa asymptoottista ylärajaa (tarkempi analyysi voi paljastaa pienemmän samalle algoritmille), Ω alarajaa (pienempää ei voida löytää) ja Θ yhtäaikaista ylä- ja alarajaa suoritusajalle. Raja voi olla muun muassa pahimmalle tapaukselle, parhaimmalle tapaukselle, keskimääräiselle tapaukselle tai tasoitetulle (amortized) suoritusajalle. Esimerkiksi pikajärjestäminen on O(n2) pahimmassa ja O(n log n) keskimääräisessä tapauksessa. Toisaalta se on myös vaikka O(n3) ja O(nn), mutta yleensä puhutaan vain pienimmästä löydetystä ylärajasta. Usein myös käytetään pelkkää O-merkintää, vaikka kyseessä on Θ. Se johtunee siitä, että ohjelmoijalle pienin tunnettu yläraja ja tiukka raja ovat aika lailla sama asia.

Voisin korjailla tuota, kun minulla on enemmän aikaa.

--Anurmi 5. helmikuuta 2008 kello 16.29 (UTC)
Varsinainen notaation kuvaus voisi olla täysin eri artikkelissa eikä tässä muuta kuin linkki: niitä kun on erilaisia samassa "perheessä" ja merkintätapa on eri asiaa. Ipr1 (keskustelu) 23. kesäkuuta 2022 kello 16.49 (EEST)[vastaa]

Tilantarve samaan artikkeliin - mikä nimeksi?[muokkaa wikitekstiä]

Otsikkonsa mukaan tämä artikkeli kertoo vain suoritusajasta, mutta olisi käytännöllisempää sijoittaa myös asymptoottinen tilantarve samaan paikkaan. Mikä olisi tällaiselle artikkelille sopiva nimi? O-notaatio? Asymptoottinen resurssintarve? Asymptoottinen vaativuus? --Anurmi 5. helmikuuta 2008 kello 16.44 (UTC)

Itse asiassa O-notaatio on vieläkin yleisempi käsite, eikä sen tarvitse liittyä mihinkään resurssintarpeeseen (en:Big O Notation#Usage). Tässä on siis kolme eri abstraktiotason juttua:
  1. Asymptoottinen notaatio yleensä
  2. Edellisen erikoistapauksena asymptoottinen resurssintarve (yleensä tilan tai ajan)
  3. Edellisen erikoistapauksena asymptoottinen ajantarve
Sanoisin, että matemaattisena käsitteenä 1. ansaitsee oman artikkelinsa O-notaatio eli Landaun notaatio, ja 2.-3. voi käsitellä yhdessä nimellä Asymptoottinen resurssintarve tms. Uudelleenohjauksia tarpeen mukaan. --Jmk 28. tammikuuta 2009 kello 10.34 (EET)[vastaa]

Määritelmästä[muokkaa wikitekstiä]

Tuollainen määritelmä

"Ο(g(n)) = {f(n) | 0 ⇐ f(n) ⇐ c2g(n) kaikilla n >= n0}
missä c2 on jokin positiivinen reaaliluku ja n0 on jokin luonnollinen luku.

Merkitään, että f(n) = Ο(g(n))."

Johtaa Russellin paradoksiin. Tällainen määritelmä taitaa olla aika yleinen tietojenkäsittelytieteessä. Mutta olisiko syytä opettaa myös matemaattisesti oikea tapa tehdä asiat, vaikka täsmällinen määritelmä on harvinaisempi? Näyttäisi pikaisen silmäyksen perusteella, että osoitteessa http://people.ds.cam.ac.uk/rc476/asymptoticmethods/am_notes.pdf luvussa 2 voisi olla oikea tapa tehdä asioita. Kuulemma myös J. D. Murrayn kirjassa Asymptotic analysis on formaali tapa, mutta minulla ei ole saatavilla tuota kirjaa ainakaan tällä hetkellä. Minusta tarkkuus olisi suotavaa vaikka se ei olisikaan yleisesti käytettyä. --2001:14BA:8300:0:0:0:1:FECE 29. marraskuuta 2017 kello 13.13 (EET)[vastaa]