Hva er stort og O i stor O-notasjon? Jeg har lest definisjonene, og det forteller ikke hva som er O uttalt som «oh». For eksempel – Jeg forstår at O (n) er kompleksiteten til en lineær algoritme der n kan være antall operasjoner. men hva er en O ?
Kommentarer
- Det ‘ s den 15. bokstaven i det engelske alfabetet. Det ‘ er også den 15. bokstaven i det greske alfabetet.
- Bare for å avklare: Du ‘ leter etter grunnen til at O er symbolet som brukes (i stedet for Q eller E eller noe annet), og hvilken betydning, hvis noen, har O over andre symboler?
- @Joel: Egentlig er det ‘ s Omicron, og det er ledetråden til hvorfor akkurat dette brevet ble valgt.
- dette svaret tilbakeviser (riktig tror jeg) Omicron-teorien.
Svar
Vel, jeg antar å være rekkefølge, som sammenfaller med wikipedia .
Rediger: (min egen (eventuelle forbedringer verdsatt)) oversettelse fra tysk wikipedia-artikkel
Storbokstaven O (egentlig en storbokstav på den tiden) som et symbol for orden av (tysk: «Ordnung von») ble først brukt av den tyske tallteoretikeren Paul Bachman i det andre nummeret av sin bok om analytisk tallteori dukket opp i 1894. Notasjonen ble populær på grunn av arbeidet til Edmund Landau, en annen tysk tallteoretiker, som denne nomenklaturen er mye assosiert med i dag, spesielt i Tysk terminologi.
Kommentarer
- Selv om det kan være tilfelle mange matematikere har referert til det som sådan, det var ikke opprinnelig det. Hvis du leser tallteoribøker fra begynnelsen av 1900-tallet, finner du ingen slik forklaring. Det er hva det er, og jeg kan ‘ t lese tysk for å finne ut hva han tenkte på notasjonen.
- @Jonathan: Innlegg oppdatert.
- Veldig hyggelig! Jeg så i alle tallteoribøkene mine, og jeg kunne ikke ‘ ikke finne en forklaring på O hvor som helst. +1
- Jeg ‘ har alltid uttalt det som rekkefølge av som bare å si O betyr ikke mye.
- Veldig informativ! men likevel – Hvorfor O uttalt som ‘ oh ‘ av programmerere?
Svar
«Stor» betyr «kapital», og «O» betyr rekkefølge, som i «rekkefølge av kompleksitet». Så kalt på grunn av konvensjonen om å skrive «orden på kompleksitet» som O (f (x)), f.eks. Med store bokstaver «O» eller «Big O». Ingen snakker mye om det fordi «alle» forstår hva det betyr, og å forstå det ikke virkelig hjelper deg med å forstå kompleksitetsanalyse.
For en forståelse av kompleksitetsanalyse, tror jeg lenken lagt ut av topgun_ivard er en bra sted å starte. En god innledende lærebok som dekker datastrukturer eller algoritmer kan også hjelpe.
Kommentarer
- I ‘ Beklager, men Bachmann-Landau-notasjonen ble oppfunnet av en tysk matematiker, så jeg tror neppe han ville ha oppkalt den etter et engelsk ord. Faktisk selv om det hadde blitt oppfunnet av en amerikansk matematiker, ville det sannsynligvis fortsatt ha blitt oppkalt etter et tysk ord, for da det ble oppfunnet (rundt 1920, tror jeg), var det internasjonale språket i matematikk tysk. Pluss at det ikke ‘ t selv eksternt har noe å gjøre med kompleksitet.
- @J ö rg: Ja, men ville ikke ‘ t som bare er Ordnung , som den tyske wiki-artikkelen hevder å være opprinnelsen: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @ Ethel kan du gjøre en mindre endring i artikkelen din slik at jeg kan stemme deg opp? Du har virkelig rett. Du må redigere før jeg kan stemme.
- @Jonathan, jeg ‘ er usikker på nøyaktig hvilken mindre endring du vil ha. Kan du bare gjøre en redigering du vil ha? Eller, vi kunne bare la back2dos ‘ svare, det ser ut til at han kanskje hadde endt med det beste svaret uansett på grunn av noen gode undersøkelser 🙂
- Hm , interessant. I Sverige kalles Big Oh vanligvis » ordo » (latin for, vel, orden) i stedet for » ordning » (det svenske ordet for ordre).
Svar
O står for orden.
Den ble opprinnelig introdusert av den tyske matematikeren Paul Bachmann i det andre bindet av hans bøker om tallteori Die Analytische Zahlentheorie , utgitt i 1894 (s. 401) . Han bemerker, etter en formel der han først bruker notasjonen:
(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (…)
Min oversettelse:
(…) hvor med notasjonen O (n) vi angi størrelsen som rekkefølgen med henvisning til n ikke overstiger rekkefølgen på n (…)
I motsetning til hva andre har sagt, indikerer ingenting i teksten at dette faktisk er en gresk hovedstadomikron. Han bruker mange både greske og latinske tegn, så det er ikke noen måte å fortelle på. Gitt hans fortsatte bruk av «Ordnung n log n » osv. I teksten, er det klart at det står for «Ordnung» (tysk for «orden» hvis det var tvil) i alle fall, men det kan fremdeles åpne bruken av et fancy gresk O.
Opprinnelsen til omikronen er imidlertid mer sannsynlig et retronym på grunn av Donald Knuth som introduserte symbolene omega (Ω) og theta (Θ) for relaterte begreper i hans papir Big Omicron og Big Omega og Big Theta , eller muligens Hardy og Littlewood som introduserte et omega-symbol tidligere.
Kommentarer
- Interessant. Jeg antar at du har rett. Jeg har bare slått opp definisjonene i både Landau ‘ s og Bachmann ‘ s bøker, og de faktisk a) bruker en latinsk Oh, ikke en gresk Omikron, b) begge bruker ordet » Ordnung «, og c) Landau uttrykkelig sier at det betyr » Ordnung «. Jeg står korrigert.
- Hvilket bedre ord kan man finne? Jeg mener, fra en tysker? Ordnung ist das halbe Leben!
- Jeg synes den første setningen i ditt (korrekte, oppstemte, kjempebra) svar skal lyde: ‘ O står for » Ordnung » (tysk betydning » Bestill «) . ‘ Det vil hjelpe dette svaret å fange oppmerksomheten til andre lesere.
Svar
Jeg liker denne artikkelen , og håper du også vil finne den nyttig!
Sitere et avsnitt fra artikkelen:
Store greske bokstaver
Big O blir ofte misbrukt. Big O eller Big Oh er faktisk kort for Big Omicron. Det representerer øvre grense for asymptotisk kompleksitet. Så hvis en algoritme er O (n log n), eksisterer det en konstant c slik at den øvre grensen er cn log n.
Θ (n log n) (Big Theta) er tettere bundet enn det. En slik algoritme betyr at det eksisterer to konstanter c1 og c2 slik at c1n log n < f (n) < c2n log n.
Ω (n log n) (Big Omega) sier at algoritmen har en nedre grense av cn log n.
Det er andre, men disse er de vanligste og Big O er den mest vanlig av alle. Et slikt skille er vanligvis uviktig, men det er verdt å merke seg. Den riktige notasjonen er tross alt den riktige notasjonen.
Hva er Big O?
Big O-notasjon søker å beskrive den relative kompleksiteten til en algoritme ved å redusere vekstraten til nøkkelen faktorer når nøkkelfaktoren har en tendens mot uendelig. Av denne grunn vil du ofte høre uttrykket asymptotisk kompleksitet. Ved å gjøre dette blir alle andre faktorer ignorert. Det er en relativ representasjon av kompleksitet.
Hva er ikke stor O?
Stor O er ikke en ytelsestest av en algoritme. Det er også tenkt eller abstrakt ved at det har en tendens til å ignorere andre faktorer. Sorteringsalgoritmekompleksitet reduseres vanligvis til antall elementer som blir sortert som nøkkelfaktoren. Dette er greit, men det tar ikke hensyn til problemer som:
Minnebruk: en algoritme kan bruke mye mer minne enn en annen. Avhengig av situasjonen kan dette være alt fra helt irrelevant til kritisk; Sammenligningskostnad: Det kan være at det er veldig dyrt å sammenligne elementer, noe som potensielt vil endre enhver sammenligning mellom algoritmer i den virkelige verden; Kostnader ved å flytte elementer: å kopiere elementer er vanligvis billig, men dette er ikke nødvendigvis tilfelle; osv.
Kommentarer
- Bare det å koble en artikkel er ikke ‘ t altfor nyttig. Det ‘ er vanligvis en god ide å omskrive eller sitere den delen du synes er spesielt relevant for tråden.
- Er nedstemmene virkelig nødvendige? Artikkelen han lenket til er veldig relevant, og IMHO ganske nyttig.I mellomtiden er det toppstemte svaret en lenke til en Wikipedia-artikkel. +1 for å kompensere for hykleriet til bikubesinnet.
- -1, fordi kunstneren, selv om den er en veldig fin og velskrevet artikkel, ikke ‘ har ikke noe med spørsmålet å gjøre.
- @Jorg, jeg sa aldri at artikkelen ville løse problemet, men jeg delte fordi jeg hadde funnet det nyttig når jeg så på disse konseptene.
- @topgun_ivard: Så hva skjer hvis det blir en død lenke? Omskrivning tillater 1) publikum i denne tråden å få en Coles-notaterversjon av lenken din (tid er penger), og 2) sørger for at innlegget ditt ikke blir gjort irrelevant på en død lenke.
Svar
EDIT: Viser seg at jeg tar feil. Likevel, kanskje dette hjelper noen med å holde symbolene rett, så jeg vil ikke slette det.
Det er faktisk ikke den latinske bokstaven Å det er den greske bokstaven Omicron . Dessverre har disse to nøyaktig samme tegn, så over tid ble den opprinnelige versjonen ødelagt, og nå er den bare Oh .
Valget av symbol har egentlig ikke noen spesiell betydning, det ble valgt som en mnemonic enhet:
- Omicron har bokstavene MICRO i seg, og semantikken til Omicron-symbolet betyr omtrent «mindre enn»
- Omega har bokstavene MEGA i seg , og semantikken til Omega-symbolet betyr omtrent «større enn»
- Theta (Θ) ser litt ut som et likhetstegn , og semantikken til Theta-symbolet betyr omtrent «lik»
Det er det. Det er ingen reell mening med det, det er bare et ordspill, hvis du vil, for å hjelpe deg å huske semantikken mer e asily.
Kommentarer
- Selv om jeg gjerne vil tro ditt mnemoniske forslag (det er en veldig kul idé), vil jeg trenge å se noe bevis på at dette er den egentlige opprinnelige intensjonen til Bachmann. Gi det, og jeg ‘ vil +1 deg.
- @Jonathan Henson: Tilsynelatende ble jeg villedet av prof. Knuth 🙂
Svar
«f (x) er stor-oh av g (x)»
Det er en matematisk måte å forutsi veksten av funksjoner på.
La f og g være funksjoner fra settet med heltall eller mengden eller reelle tall til settet med reelle tall. Vi sier at f (x) er O (g (x)) hvis det er konstanter C og k slik at | f (x) | < = C | g (x) | uansett hvor x> k.
Du vil lese dette som «f (x) er stor-oh av g (x)»
Den store-O blir noen ganger kalt et Landau-symbol etter den tyske matematikeren Edmund Landau. Jeg tror ikke det står for noe utover det. Du har også de samme store Omega- og Big-Theta-notasjonene. Symbolene er like vilkårlige som å alltid bruke theta til å betegne vinklene i trekantene dine i planargeometrien på videregående skole. klasse.
Korreksjon @ back2dos har gitt en tilfredsstillende forklaring på O som refererer til ordre. Flott Job. Se svaret.
Donald Knuth brukte det på å studere kompleksiteten til dataprogrammer.
Hvis du vil finne årsaken til at notasjonen ble brukt, bør du lese
«Analytische Zahlentheorie» av Paul Bachmann fra 1892
Svar
UPDATE: Forsøk på å rydde opp i svaret mitt og være mer nøyaktig
Stor O-notasjon er en måte å karakterisere funksjoner i henhold til vekstratene. står for ordre (første ordre er n andre ordens å være kvadrat osv.) Og hvis jeg ikke er det feil, dette ville være det verste tilfellet for en metode kjøretid (eller lagring) gitt N-elementer. Jo større rekkefølge det verste metoden utfører.
For eksempel å slå opp en post i en matrise er O (1) (jeg tror på noen implementering av hash-tabeller som også er tilfelle). Å legge til en verdi på slutten av en koblingsliste vil være O (N) fordi du må komme til slutten av listen før du kan legge til elementet osv.
Dette svaret skal være litt mer korrekt enn mitt første forsøk 🙂
Kommentarer
- -1 fordi dette bare er gammel feil og svarte på et eget spørsmål enn det ble spurt. Spørsmålet var hvorfor brukes bokstaven » O «, ikke » hvordan fungerer Big O notasjonsarbeid? «. Du ‘ er feil når det gjelder hvordan Big-oh fungerer også, men … å løpe gjennom en matrise er O (n) hvor n er størrelsen på matrisen, ikke O (1) . Notasjonen har ingenting å gjøre med » sykluser » til en algoritme … det ‘ en måling av den øvre grensen for en algoritmes kjøretid.
- Ikke for å krangle med deg her, men at ‘ er det jeg mente. Hva betyr kjøretid riktig?Vel, kjøretiden bestemmes av hva som må behandles på maskinen. Jeg antar at jeg liksom bruker syklusen her. Etter syklus antar jeg at jeg burde ha sagt iterate-through eller noe sånt. Du har rett i øvre grense, men det bestemmer ikke gjennomsnittet. Derfor aksepterer jeg nedgradering.