Mikä on O isossa O: ssa?

No, arvaukseni olisi järjestys, joka on sama kuin wikipedia .

Muokkaa: (oma (kaikki parannukset arvostetaan)) käännös saksankielisestä wikipedia-artikkelista

Isoa O-kirjainta (oikeastaan iso omikroni tuolloin) symbolina järjestyksessä (saksaksi: ”Ordnung von”) käytti ensin saksalainen numeroteoreetikko Paul Bachman analyyttistä lukuteoriaa käsittelevän kirjansa toisessa numerossa ilmestyi vuonna 1894. Merkinnät saivat suosiota toisen saksalaisen numeroteoreetikon Edmund Landau, jonka kanssa tämä nimikkeistö on nykyään laajalti yhteydessä, erityisesti Saksankielinen terminologia.

Kommentit

• Vaikka voi olla, että monet matemaatikot ovat viitanneet se sinänsä, se ei ollut alun perin niin. Jos luet 1900-luvun alun numeroteoriakirjoja, et löydä tällaista selitystä. Se on mitä se on, enkä voi ’ lukea saksaa selvittääkseen, mikä hänen ajattelunsa oli merkinnässä.
• @Jonathan: Viesti päivitetty.
• Erittäin mukavaa! Katsoin kaikkia lukuteoriakirjojani, enkä voinut ’ löytää mistään O: n selitystä. +1
• I ’ olen aina lausunut sen järjestykseksi , koska pelkkä O: n sanominen ei tarkoita paljoa.
• Erittäin informatiivinen! mutta silti – Miksi O lausutaan ’ oh ’ ohjelmoijilta?

”Iso” tarkoittaa ”pääoma” ja ”O” tarkoittaa järjestystä, kuten ”monimutkaisuusjärjestyksessä”. Niin nimetty, koska ”monimutkaisuusjärjestys” on kirjoitettu O: ksi (f (x)), esim. Isolla kirjaimella ”O” tai ”iso O”. Kukaan ei puhu siitä paljon, koska ”kaikki” ymmärtävät mitä se tarkoittaa, ja sen ymmärtäminen ei todellakaan auta sinua ymmärtämään monimutkaisuusanalyysiä.

Ymmärtääkseni monimutkaisuusanalyysin mielestäni topgun_ivardin lähettämä linkki on hyvä paikka aloittaa. Myös tietorakenteita tai algoritmeja käsittelevä hyvä johdantokirja voi auttaa.

Kommentit

• I ’ anteeksi, mutta Bachmann-Landau-merkinnän on keksinyt saksalainen matemaatikko, joten tuskin luulen, että hän olisi nimennyt sen englanninkielisen sanan mukaan. Itse asiassa vaikka sen olisi keksinyt amerikkalainen matemaatikko, se olisi todennäköisesti vielä nimetty saksankielisen sanan mukaan, koska kun se keksittiin (mielestäni noin vuonna 1920), matematiikan kansainvälinen kieli oli saksa. Lisäksi se ei ’ t edes etänä ole mitään tekemistä monimutkaisuuden kanssa.
• @J ö rg: Kyllä, mutta ei ’ t että vain Ordnung , jonka saksalaisen wikiartikkelin mukaan alkuperä on: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel voisitko tehdä pienen muutoksen artikkeliin, jotta voin äänestää sinut? Olet todellakin oikeassa. Sinun on muokattava, ennen kuin voin äänestää.
• @Jonathan, en ’ ole varma, minkä pienen muutoksen haluat. Voitko vain mennä eteenpäin ja tehdä haluamasi muokkauksen? Tai voisimme vain antaa back2dos ’ -vastausjalustan, näyttää siltä, että hän olisi voinut päätyä parhaaseen vastaukseen erinomaisen tutkimuksen vuoksi 🙂
• Hm , mielenkiintoista. Ruotsissa Big Oh kutsutaan yleensä ” ordo ” (latinaksi sanalle, hyvin, tilaus) sijaan ” ordning ” (ruotsalainen järjestyssana).

O tarkoittaa järjestystä.

Sen esitteli alun perin saksalainen matemaatikko Paul Bachmann -numeroteoriaa käsittelevien kirjojensa Die Analytische Zahlentheorie toisessa osassa, julkaistu vuonna 1894 (s. 401) . Hän toteaa kaavan jälkeen, jossa hän käyttää ensin merkintää:

(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (…)

Käännökseni:

(…) missä merkinnällä O (n) me ilmoita suuruusluokka, jonka järjestys n viittaa ei ylitä n (…)

Päinvastoin kuin muut ovat sanoneet, mikään hänen tekstissään ei osoita, että kyseessä on itse asiassa kreikkalainen pääkaupunki omikron. Hän käyttää paljon sekä kreikkalaisia että latinankielisiä merkkejä, joten ei ole mitään tapaa kertoa. Ottaen huomioon hänen jatkuvan tekstinsyötön ”Ordnung n log n ” jne., On selvää, että se tarkoittaa ”Ordnung” (saksankielinen ”järjestys”, jos epäilyksiä on) joka tapauksessa, mutta se voi silti jättää avoimeksi hienon kreikkalaisen O. käytön.

Omikronin alkuperä on kuitenkin todennäköisemmin takaisinsana Donald Knuthille, joka esitteli symboleja omega (Ω) ja theta (Θ) asiaan liittyville käsitteille paperissaan Big Omicron ja Big Omega ja Big Theta tai mahdollisesti Hardy ja Littlewood , jotka esittivät omega-symbolin aiemmin.

Kommentit

• Mielenkiintoista. Oletan, että olet oikeassa. Etsin juuri määritelmiä sekä Landau ’ s- että Bachmann ’ -kirjoista, ja he todellakin a) käyttävät latinalaista Oh, ei kreikkalainen Omikron, b) molemmat käyttävät sanaa ” Ordnung ” ja c) Landau nimenomaisesti sanoo, että se tarkoittaa ” Ordnung ”. Olen oikeassa.
• Mikä parempaa sanaa voisi löytää? Tarkoitan saksalaiselta? Ordnung ist das halbe Leben!
• Luulen, että vastauksen (oikean, äänestetyn, mahtavan) ensimmäisen virkkeen tulisi kuulua seuraavasti: ’ O tarkoittaa ” Ordnung ” (saksankielinen merkitys ” Järjestys ”) . ’ Se auttaisi tätä vastausta herättämään muiden lukijoiden huomion.

Pidän tästä artikkelista , toivoen, että sinäkin pidät siitä hyödyllisenä!

Lainaan osan artikkelista:
Isot kreikkalaiset kirjeet

Isoa O: ta käytetään usein väärin. Big O tai Big Oh on oikeastaan lyhyt Big Omicronista. Se edustaa asymptoottisen monimutkaisuuden ylärajaa. Joten jos algoritmi on O (n log n), on olemassa vakio c siten, että yläraja on cn log n.

Θ (n log n) (iso teeta) on tiukemmin sidottu kuin tämä. Tällainen algoritmi tarkoittaa, että on olemassa kaksi vakiota c1 ja c2 siten, että c1n log n < f (n) < c2n log n.

Ω (n log n) (Big Omega) sanoo, että algoritmilla on alempi cn log n: n raja.

On muitakin, mutta nämä ovat yleisimpiä ja iso O on yleisimpiä kaikkien yhteinen. Tällainen ero on tyypillisesti merkityksetöntä, mutta se on syytä huomata. Oikea merkintätapa on loppujen lopuksi oikea merkintätapa.

Mikä on iso O?

Big O-merkinnällä pyritään kuvaamaan algoritmin suhteellista monimutkaisuutta vähentämällä kasvunopeus avaimeen tekijät, kun avaintekijä pyrkii kohti ääretöntä. Tästä syystä kuulet usein lauseen asymptoottinen monimutkaisuus. Tällöin kaikki muut tekijät jätetään huomiotta. Se on suhteellisuus monimutkaisuudesta.

Mikä ei ole iso O?

Iso O ei ole algoritmin suorituskykytesti. Se on myös käsitteellinen tai abstrakti, koska sillä on taipumus jättää huomiotta muut tekijät. Algoritmien monimutkaisuus lajitellaan tyypillisesti avaintekijänä lajiteltavien elementtien lukumäärään. Tämä on hieno, mutta siinä ei oteta huomioon seuraavia asioita:

Muistin käyttö: yksi algoritmi saattaa käyttää paljon enemmän muistia kuin toinen. Tilanteesta riippuen tämä voi olla täysin merkityksetöntä kriittiseen; Vertailukustannukset: Voi olla, että elementtien vertailu on todella kallista, mikä voi muuttaa algoritmien välistä todellista vertailua; Elementtien siirtämisen kustannukset: elementtien kopiointi on tyypillisesti halpaa, mutta näin ei välttämättä ole; jne.

Kommentit

• Artikkelin yksinkertainen linkittäminen ei ole liikaa hyötyä ’. ’ on yleensä hyvä muotoilla tai lainata sitä osaa, joka on mielestäsi erityisen merkityksellinen säikeelle.
• Ovatko alhainen äänestys todella tarpeellista? Hänen linkittämä artikkeli on erittäin merkityksellinen, ja IMHO on melko hyödyllinen.Samaan aikaan suosituin vastaus on linkki Wikipedia-artikkeliin. +1 tasoittaa pesämielen tekopyhyyttä.
• -1, koska vaikka artikkeli onkin erittäin mukava ja hyvin kirjoitettu artikkeli, se ei ’ Minulla ei ole mitään tekemistä kysymyksen kanssa.
• @Jorg, en koskaan sanonut, että artikkeli ratkaisee ongelman, mutta jaoin, koska minusta oli ollut hyödyllistä, kun tarkastelin näitä käsitteitä.
• @topgun_ivard: Joten mitä tapahtuu, jos se muuttuu kuolleeksi linkiksi? Muotoilun avulla 1) tämän ketjun yleisö saa Coles-muistiinpanotiedoston linkistäsi (aika on rahaa) ja 2) varmistaa, että viestiäsi ei tehdä merkityksettömäksi kuolleen linkin kohdalla.

MUOKKAA: Osoittautuu, että olen väärässä. Siitä huolimatta ehkä tämä auttaa jotakuta pitämään symbolinsa suorana, joten en aio poistaa sitä.

Itse asiassa se ei latinankielinen kirjain Voi , se on kreikkalainen kirjain Omicron . Valitettavasti näillä kahdella on täsmälleen sama kuviokuva, joten ajan myötä alkuperäinen versio vioittui, ja nyt se on vain Voi .

Symbolin valinnalla ei ole oikeastaan mitään erityistä merkitystä, se valittiin muisti laitteeksi:

• Omicron issa on kirjaimet MICRO, ja Omicron-symbolin semantiikka tarkoittaa karkeasti ”pienempää kuin”
• Omega sisältää MEGA-kirjaimet , ja Omega-symbolin semantiikka tarkoittaa karkeasti ”isompaa kuin”
• Theta (Θ) näyttää vähän kuin yhtäläisyysmerkki , ja Theta-symbolin semantiikka tarkoittaa karkeasti ”yhtä suuri”

Se on siinä. Sillä ei ole todellista merkitystä, se on vain sanaleikki, jos auttaa muistamaan semantiikan enemmän e nopeasti.

Kommentit

• Vaikka haluaisin mielelläni uskoa mnemoniseen ehdotukseesi (se on todella siisti idea), minun täytyy nähdä jotkut todisteet siitä, että tämä on Bachmannin todellinen alkuperäinen tarkoitus. Anna se, ja minä ’ ll +1 sinulle.
• @Jonathan Henson: Ilmeisesti prof. Knuth johti minut harhaan 🙂

”f (x) on iso-oh g: stä (x)”

Se on matemaattinen tapa ennustaa funktioiden kasvu.

Olkoon f ja g funktiot kokonaislukujoukosta tai joukko- tai reaaliluvuista reaalilukujoukkoihin. Sanomme, että f (x) on O (g (x)), jos vakioita C ja k on sellaisia, että | f (x) | < = C | g (x) | missä tahansa x> k.

Luisit tämän seuraavasti: ”f (x) on iso-oh g (x): stä”

Isoa O: ta kutsutaan joskus Landau-symboliksi saksalainen matemaatikko Edmund Landau. En usko, että se edustaa mitään muuta kuin sitä. Sinulla on myös samanlaiset iso-Omega- ja iso-Theta-merkinnät. Symbolit ovat yhtä mielivaltaisia kuin teetalla aina kolmiojesi kulmien merkitseminen oli lukion Planar Geometryssä. luokka.

Korjaus @ back2dos on antanut O: lle tyydyttävän selityksen järjestykseen viittaavaksi. Job. Katso hänen vastauksensa.

Donald Knuth sovelsi sitä tietokoneohjelmien monimutkaisuuden tutkimiseen.

Jos haluat löytää merkinnän käyttämisen syyn, lue

”Analytische Zahlentheorie”, Paul Bachmann vuodelta 1892

PÄIVITYS: Yritän puhdistaa vastaukseni ja olla tarkempi

Iso O-notaatio on tapa luonnehtia toimintoja kasvunopeuden mukaan. tarkoittaa järjestystä (ensimmäinen järjestys on n toinen järjestys on n-neliö jne.) Ja jos en ole väärin tämä olisi pahin skenaario menetelmien ajonaikaiselle (tai tallennustilalle) annetulle N elementille. Mitä suurempi järjestys on huonoin menetelmä suorittaa.
Esimerkiksi tietueen etsiminen taulukosta on O (1) (uskon, että myös hash-taulukot toteutetaan). Arvon lisääminen linkkiluettelon loppuun olisi O (N), koska sinun on päästävä luettelon loppuun ennen kuin voit lisätä elementin jne.

Tämän vastauksen tulisi olla hieman oikeampi kuin ensimmäinen yritykseni 🙂

Kommentit

• -1, koska tämä on yksinkertaisesti vanhaa virheellistä JA vastasi erilliseen kysymykseen kuin pyydettiin. Kysymys oli, miksi kirjainta ” O ” käytetään, ei ” miten iso O merkintätyö? ”. ’ Olet väärässä siitä, kuinka Big-oh toimii, vaikka … silmukka taulukon läpi on O (n) missä n on matriisin koko, ei O (1) . Merkinnällä ei ole mitään tekemistä algoritmin ” -syklien ” kanssa … se ’ sa algoritmin ajoajan ylärajan mittaus.
• Ei kiistellä kanssasi tässä, mutta että ’ tarkoitin sellaista. Mitä juoksuaika tarkoittaa oikein?No, ajoaika määräytyy sen mukaan, mitä koneessa on käsiteltävä. Luulen, että käytän tavallaan täällä vapaasti. Syklin mukaan minun olisi pitänyt sanoa iterate-through tai jotain sellaista. Olet kuitenkin oikeassa ylärajasta, se ei määrää keskiarvoa. Siksi hyväksyn alennuksen.