Vad är Big och O i Big O-notation? Jag har läst definitionerna och det berättar inte vad som O uttalas som ”åh”. Till exempel – jag förstår att O (n) är komplexiteten hos en linjär algoritm där n kan vara antalet operationer. men vad är en O ?
Kommentarer
- Det ’ s den 15: e bokstaven i det engelska alfabetet. Det ’ är också den 15: e bokstaven i det grekiska alfabetet.
- Bara för att klargöra: Du ’ du letar efter anledningen till varför O är den symbol som används (istället för Q eller E eller något annat), och vilken betydelse, om någon, O har över andra symboler?
- @Joel: Egentligen ’ s Omicron, och det är ledtråden till varför just detta brev valdes.
- detta svar motbevisar (korrekt tror jag) Omicron-teorin.
Svar
Jag antar att det är ordning som sammanfaller med wikipedia .
Redigera: (min egen (alla förbättringar uppskattade)) översättning från Tyska wikipedia-artikel
Stora bokstaven O (egentligen en stor omicron vid den tiden) som en symbol för ordningen på (tyska: ”Ordnung von”) användes först av den tyska talteoretikern Paul Bachman i det andra numret av sin bok om analytisk talteori dök upp 1894. Notationen blev populär på grund av Edmund Landaus arbete, en annan tysk nummerteoretiker, som denna nomenklatur är allmänt associerad med idag, särskilt i Tysk terminologi.
Kommentarer
- Även om det kan vara fallet som många matematiker har hänvisat till det som sådant var det inte ursprungligen så. Om du läser talteoriböcker från början av 1900-talet hittar du ingen sådan förklaring. Det är vad det är och jag kan ’ inte läsa tyska för att ta reda på vad han tänkte på notationen.
- @Jonathan: Inlägget uppdaterat.
- Mycket trevligt! Jag tittade i alla mina teoriböcker och jag kunde inte ’ inte hitta en förklaring av O var som helst. +1
- Jag ’ har alltid uttalat det som ordning på som bara att säga O betyder inte mycket.
- Mycket informativt! men ändå – Varför O uttalas som ’ oh ’ av programmerare?
Svar
”Stor” betyder ”kapital” och ”O” betyder ordning, som i ”ordning på komplexitet”. Så benämnt på grund av konventionen att skriva ”ordning på komplexitet” som O (f (x)), t.ex. med en stor bokstav ”O” eller en ”Stor O”. Ingen talar mycket om det för att ”alla” förstår vad det betyder, och att förstå det verkligen inte hjälper dig att förstå komplexitetsanalys.
För att förstå komplexitetsanalys, tror jag att länken publicerad av topgun_ivard är en bra ställe att börja. En bra introduktionsbok som täcker datastrukturer eller algoritmer kan också hjälpa.
Kommentarer
- I ’ jag är ledsen, men Bachmann-Landau-notationen uppfanns av en tysk matematiker, så jag tror knappast att han skulle ha namngett det efter ett engelskt ord. Faktum är att även om det hade uppfunnits av en amerikansk matematiker skulle det nog ha fått sitt namn efter ett tyskt ord, för när det uppfanns (omkring 1920 tror jag) var det internationella språket i matematik tyskt. Plus att det inte ’ t även på distans har något att göra med komplexitet.
- @J ö rg: Ja, men skulle inte ’ t som bara är Ordnung , som den tyska wiki-artikeln påstår sig vara ursprunget: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @ Ethel kan du göra en mindre ändring av din artikel så att jag kan rösta upp dig? Du har verkligen rätt. Du måste redigera innan jag kan rösta.
- @Jonathan, jag ’ jag vet inte exakt vilken mindre förändring du vill ha. Kan du bara gå vidare och göra den redigering du vill ha? Eller så kan vi bara låta back2dos ’ svara, det ser ut som om han kanske hade fått det bästa svaret ändå på grund av utmärkt forskning 🙂
- Hm , intressant. I Sverige kallas Big Oh vanligtvis ” ordo ” (latin för, ja, ordning) snarare än ” ordning ” (det svenska ordet för ordning).
Svar
O står för ordning.
Den introducerades ursprungligen av den tyska matematikern Paul Bachmann i den andra volymen av hans böcker om talteori Die Analytische Zahlentheorie , publicerad 1894 (s. 401) . Han noterar, efter en formel där han först använder notationen:
(…) 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 översättning:
(…) var med notationen O (n) vi ange en storlek av vilken ordningen med hänvisning till n inte överstiger ordningen på n (…)
Till skillnad från vad andra har sagt, tyder ingenting i hans text på att detta i själva verket är en grekisk huvudomikron. Han använder gott om både grekiska och latinska tecken, så det finns inte något sätt att berätta. Med tanke på hans fortsatta användning av ”Ordnung n log n ” etc. i texten är det tydligt att det står för ”Ordnung” (tyska för ”order” om det fanns något tvivel) i vilket fall som helst, men det kan fortfarande lämna öppen användning av ett snyggt grekiskt O.
Omikronens ursprung är dock mer sannolikt en retronym på grund av Donald Knuth som introducerade symbolerna omega (Ω) och theta (Θ) för relaterade begrepp i hans uppsats Big Omicron och Big Omega och Big Theta , eller möjligen Hardy och Littlewood som introducerade en omega-symbol tidigare.
Kommentarer
- Intressant. Jag antar att du har rätt. Jag letade bara upp definitionerna i både Landau ’ s och Bachmann ’ s böcker, och de faktiskt a) använder en latin Oh, inte en grekisk Omikron, b) båda använder ordet ” Ordnung ”, och c) Landau uttryckligen säger att det betyder ” Ordnung ”. Jag står rättad.
- Vilket bättre ord kan man hitta? Jag menar, från en tysk? Ordnung ist das halbe Leben!
- Jag tycker att den första meningen i ditt (korrekta, upprösta, fantastiska) svar borde läsa: ’ O står för ” Ordnung ” (tyska betyder ” Beställ ”) . ’ Det skulle hjälpa det här svaret att få andra läsares uppmärksamhet.
Svar
Jag gillar den här artikel , och hoppas att du också tycker att den är användbar!
Citera ett avsnitt från artikeln:
Stora grekiska bokstäver
Big O missbrukas ofta. Big O eller Big Oh är faktiskt en förkortning för Big Omicron. Det representerar den övre gränsen för asymptotisk komplexitet. Så om en algoritm är O (n log n) finns det en konstant c så att den övre gränsen är cn log n.
Θ (n log n) (Big Theta) är tätare bunden än så. En sådan algoritm betyder att det finns två konstanter c1 och c2 så att c1n log n < f (n) < c2n log n.
Ω (n log n) (Big Omega) säger att algoritmen har en lägre gräns för cn log n.
Det finns andra men dessa är de vanligaste och Big O är den mest gemensamt av alla. En sådan skillnad är vanligtvis obetydlig men det är värt att notera. Den korrekta notationen är ju den korrekta notationen.
Vad är Big O?
Big O-notation försöker beskriva den relativa komplexiteten hos en algoritm genom att minska tillväxthastigheten till nyckeln faktorer när nyckelfaktorn tenderar mot oändlighet. Av denna anledning hör du ofta frasen asymptotisk komplexitet. Genom att göra det ignoreras alla andra faktorer. Det är en relativ representation av komplexitet.
Vad är inte Big O?
Big O är inte ett prestandatest av en algoritm. Det är också teoretiskt eller abstrakt genom att det tenderar att ignorera andra faktorer. Sorteringsalgoritmens komplexitet reduceras vanligtvis till antalet element som sorteras som nyckelfaktorn. Det här är bra men det tar inte hänsyn till frågor som:
Minnesanvändning: en algoritm kan använda mycket mer minne än en annan. Beroende på situationen kan detta vara allt från helt irrelevant till kritiskt; Jämförelsekostnad: Det kan vara så att jämförande element är väldigt dyra, vilket potentiellt kommer att förändra jämförelser mellan algoritmer i verkligheten; Kostnader för att flytta element: att kopiera element är vanligtvis billigt men så är det inte nödvändigtvis fallet; etc.
Kommentarer
- Att bara länka en artikel är inte ’ t alltför användbart. Det ’ är vanligtvis en bra idé att omformulera eller citera det avsnitt som du tycker är särskilt relevant för tråden.
- Är nedröstningarna verkligen nödvändiga? Artikeln han länkade är väldigt relevant och IMHO ganska hjälpsam.Under tiden är det högst röstade svaret en länk till en Wikipedia-artikel. +1 för att kompensera bikupets sinnets hyckleri.
- -1, eftersom artice, även om den är en mycket trevlig och välskriven artikel, inte ’ t har något att göra med frågan.
- @Jorg, jag sa aldrig att artikeln skulle lösa problemet, men jag delade eftersom jag tyckte att det var användbart när jag tittade på dessa begrepp.
- @topgun_ivard: Så vad händer om det blir en död länk? Omskrivning gör att 1) publiken i den här tråden kan få en Coles-anteckningsversion av din länk (tid är pengar) och 2) säkerställer att ditt inlägg inte görs irrelevant för en död länk.
Svar
EDIT: Visar att jag har fel. Ändå kanske det här hjälper någon att hålla sina symboler raka, så jag tänker inte radera dem.
Det är faktiskt inte den latinska bokstaven Åh det är den grekiska bokstaven Omicron . Tyvärr har dessa två exakt samma tecken, så med tiden blev originalversionen skadad, och nu är det bara Åh .
Symbolvalet har faktiskt ingen speciell betydelse, det valdes som en mnemonic -enhet:
- Omicron har bokstäverna MICRO i sig, och semantiken i Omicron-symbolen betyder ungefär ”mindre än”
- Omega har bokstäverna MEGA i sig , och semantiken i Omega-symbolen betyder ungefär ”större än”
- Theta (Θ) ser lite ut som ett likhetstecken , och semantiken i Theta-symbolen betyder ungefär ”lika med”
Det är det. Det finns ingen verklig mening med det, det är bara ett ordspel, om du kommer att hjälpa dig att komma ihåg semantiken mer e lika lätt.
Kommentarer
- Även om jag skulle vilja tro ditt mnemoniska förslag (det är en riktigt cool idé), kommer jag att behöva se ett visst bevis på att detta är Bachmanns verkliga ursprungliga avsikt. Ge det och jag ’ kommer att +1 dig.
- @Jonathan Henson: Tydligen blev jag vilseledd av professor Knuth 🙂
Svar
”f (x) är stort-oh av g (x)”
Det är ett matematiskt sätt att förutsäga funktionens tillväxt.
Låt f och g vara funktioner från uppsättningen heltal eller uppsättningen eller reella tal till uppsättningen reella tal. Vi säger att f (x) är O (g (x)) om det finns konstanter C och k så att | f (x) | < = C | g (x) | varhelst x> k.
Du skulle läsa detta som ”f (x) är stort-oh av g (x)”
Big-O kallas ibland en Landau-symbol efter den tyska matematikern Edmund Landau. Jag tror inte att det står för något utöver det. Du har också liknande stora-Omega- och stora-Theta-noteringar. Symbolerna är lika godtyckliga som att alltid använda theta för att beteckna vinklarna i dina trianglar var i din gymnasiums planära geometri klass.
Korrigering @ back2dos har gett en tillfredsställande förklaring för O som hänvisar till ordning. Job. Se hans svar.
Donald Knuth använde det för att studera komplexiteten i datorprogram.
Om du vill hitta orsaken till att notationen användes, bör du läsa
”Analytische Zahlentheorie” av Paul Bachmann från 1892
Svar
UPPDATERING: Att försöka städa upp mitt svar och vara mer exakt
Stor O-notering är ett sätt att karakterisera funktioner efter tillväxthastigheter. står för ordning (första ordningen är n andra ordningen är n-kvadrat osv.) Och om jag inte är det felaktigt skulle detta vara det värsta fallet för en metod runtime (eller lagring) givet N-element. Ju större ordning sämst metoden utför.
Att till exempel slå upp en post i en matris är O (1) (jag tror på en viss implementering av en hash-tabell som också är fallet). Att lägga till ett värde i slutet av en länklista skulle vara O (N) eftersom du måste komma till slutet av listan innan du kan lägga till elementet etc.
Detta svar ska vara något mer korrekt än mitt första försök 🙂
Kommentarer
- -1 eftersom detta bara är gammalt felaktigt OCH svarade på en separat fråga än vad som ställdes. Frågan var varför används bokstaven ” O ”, inte ” hur fungerar Big O notationsarbete? ”. Du ’ är felaktig om hur Big-oh fungerar också men … att slinga genom en array är O (n) där n är storleken på arrayen, inte O (1) . Notationen har ingenting att göra med ” cykler ” för en algoritm … det ’ en mätning av den övre gränsen för en algoritms körtid.
- Inte för att argumentera med dig här, men att ’ är något av det jag menade. Vad betyder körtid rätt?Jo, körtiden bestäms av vad som måste bearbetas på maskinen. Jag antar att jag typ av cykel använder mig här. Efter cykel antar jag att jag borde ha sagt iterate-through eller något liknande. Du har dock rätt om övre gräns, men det bestämmer inte genomsnittet. Därför accepterar jag nedgraderingen.