Hvad er Big og O i Big O-notation? Jeg har læst definitionerne, og det fortæller ikke, hvad der er O udtalt som “åh”. For eksempel – Jeg forstår, at O (n) er kompleksiteten af en lineær algoritme, hvor n kunne være antallet af operationer. men hvad er en O ?
Kommentarer
- Det ‘ s det 15. bogstav i det engelske alfabet. Det ‘ er også det 15. bogstav i det græske alfabet.
- Bare for at præcisere: Du ‘ leder efter årsagen til, at O er det symbol, der bruges (i stedet for Q eller E eller noget andet), og hvilken betydning, hvis nogen, O har over andre symboler?
- @Joel: Faktisk er det ‘ s Omicron, og det er ledetråden til hvorfor netop dette bogstav blev valgt.
- dette svar tilbageviser (korrekt tror jeg) Omicron-teorien.
Svar
Nå, jeg gætter på at være rækkefølge, som falder sammen med wikipedia .
Rediger: (min egen (eventuelle forbedringer værdsat)) oversættelse fra tysk wikipedia-artikel
Hovedbogstavet O (faktisk en storbogstav på det tidspunkt) som et symbol på rækkefølgen af (tysk: “Ordnung von”) blev først brugt af den tyske talteoretiker Paul Bachman i det andet nummer af sin bog om analytisk talteori dukkede op i 1894. Notationen blev populær på grund af Edmund Landaus arbejde, en anden tysk talteoretiker, som denne nomenklatur er meget forbundet med i dag, især i Tysk terminologi.
Kommentarer
- Selvom det kan være tilfældet, som mange matematikere har henvist til det som sådan var det oprindeligt ikke sådan. Hvis du læser talteoribøger fra det tidlige 20. århundrede, finder du ingen sådan forklaring. Det er hvad det er, og jeg kan ‘ ikke læse tysk for at finde ud af, hvad hans tænkning var på notationen.
- @Jonathan: Indlæg opdateret.
- Meget flot! Jeg kiggede i alle mine talteoribøger, og jeg kunne ikke ‘ ikke finde en forklaring på O overalt. +1
- Jeg ‘ har altid udtalt det som rækkefølge af som bare at sige O betyder ikke meget.
- Meget informativ! men stadig – Hvorfor O udtalt som ‘ oh ‘ af programmører?
Svar
“Stor” betyder “kapital”, og “O” betyder rækkefølge, som i “rækkefølge af kompleksitet”. Så navngivet på grund af konventionen om at skrive “orden af kompleksitet” som O (f (x)), f.eks. Med et stort bogstav “O” eller et “Big O”. Ingen taler meget om det, fordi “alle” forstår, hvad det betyder, og forståelse af det hjælper dig ikke rigtig med at forstå kompleksitetsanalyse.
For en forståelse af kompleksitetsanalyse, tror jeg, at linket fra topgun_ivard er et godt sted at starte. En god introduktionsbog, der dækker datastrukturer eller algoritmer, kan også hjælpe.
Kommentarer
- I ‘ undskyld, men Bachmann-Landau-notationen blev opfundet af en tysk matematiker, så jeg tror næppe, at han ville have navngivet det efter et engelsk ord. Faktisk selvom det var blevet opfundet af en amerikansk matematiker, ville det sandsynligvis stadig være opkaldt efter et tysk ord, for da det blev opfundet (omkring 1920, tror jeg), var matematikens internationale sprog tysk. Plus, det betyder ikke ‘ t selv eksternt har noget at gøre med kompleksitet.
- @J ö rg: Ja, men ville ikke ‘ t der bare er Ordnung , som den tyske wiki-artikel hævder at være oprindelsen: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @ Ethel kunne du foretage en mindre ændring af din artikel, så jeg kan stemme dig op? Du har virkelig ret. Du skal redigere, før jeg kan stemme.
- @Jonathan, jeg ‘ Jeg er ikke helt sikker på, hvilken mindre ændring du vil have. Kan du bare gå videre og foretage den ønskede redigering? Eller vi kunne bare lade back2dos ‘ svare, det ser ud til, at han muligvis endte med det bedste svar alligevel på grund af nogle fremragende undersøgelser 🙂
- Hm , interessant. I Sverige kaldes Big Oh normalt ” ordo ” (latin for, ja, rækkefølge) snarere end ” ordning ” (det svenske ord for ordre).
Svar
O står for orden.
Det blev oprindeligt introduceret af den tyske matematiker Paul Bachmann i andet bind af hans bøger om talteori Die Analytische Zahlentheorie , udgivet i 1894 (s. 401) . Han bemærker efter en formel, hvor han først bruger 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 oversættelse:
(…) hvor med betegnelsen O (n) vi angive en størrelsesorden, hvor rækkefølgen med henvisning til n ikke overstiger rækkefølgen af n (…)
I modsætning til hvad andre har sagt, indikerer intet i hans tekst, at dette faktisk er en græsk hovedstad omikron. Han bruger masser af både græske og latinske tegn, så der er ikke nogen måde at fortælle. I betragtning af hans fortsatte brug af “Ordnung n log n ” osv. I teksten er det klart, at det står for “Ordnung” (tysk for “ordre”, hvis der var tvivl) under alle omstændigheder, men det kan stadig lade brugen af et smukt græsk O være åbent.
Omikronens oprindelse er dog mere sandsynligt et retronym på grund af Donald Knuth, der introducerede symbolerne omega (Ω) og theta (Θ) for relaterede begreber i hans papir Big Omicron og Big Omega og Big Theta eller muligvis Hardy og Littlewood , der introducerede et omega-symbol tidligere.
Kommentarer
- Interessant. Jeg antager, at du har ret. Jeg har lige slået definitionerne op i både Landau ‘ s og Bachmann ‘ s bøger, og de faktisk a) bruger en latin Oh, ikke en græsk Omikron, b) begge bruger ordet ” Ordnung “, og c) Landau udtrykkeligt siger, at det betyder ” Ordnung “. Jeg står korrigeret.
- Hvilket bedre ord kunne findes? Jeg mener, fra en tysker? Ordnung ist das halbe Leben!
- Jeg synes, den første sætning i dit (korrekte, opstemte, fantastiske) svar skal lyde: ‘ O står for ” Ordnung ” (tysk betydning ” Bestil “) . ‘ Det ville hjælpe dette svar at få andre læsere opmærksomhed.
Svar
Jeg kan godt lide denne artikel og håber, at du også finder den nyttig!
Citering af et afsnit fra artiklen:
Store græske bogstaver
Big O misbruges ofte. Big O eller Big Oh er faktisk en forkortelse for Big Omicron. Det repræsenterer den øvre grænse for asymptotisk kompleksitet. Så hvis en algoritme er O (n log n), findes der en konstant c, således at den øvre grænse er cn log n.
Θ (n log n) (Big Theta) er tættere bundet end det. En sådan algoritme betyder, at der findes to konstanter c1 og c2, således at c1n log n < f (n) < c2n log n.
Ω (n log n) (Big Omega) siger, at algoritmen har en nedre grænse for cn log n.
Der er andre, men disse er de mest almindelige, og Big O er den mest fælles for alle. En sådan skelnen er typisk uvigtig, men det er værd at bemærke. Den korrekte notation er trods alt den korrekte notation.
Hvad er Big O?
Big O-notation søger at beskrive den relative kompleksitet af en algoritme ved at reducere vækstraten til nøglen faktorer, når nøglefaktoren har tendens til uendelig. Af denne grund vil du ofte høre sætningen asymptotisk kompleksitet. Ved at gøre dette ignoreres alle andre faktorer. Det er en relativ repræsentation af kompleksitet.
Hvad er ikke Big O?
Big O er ikke en præstationstest af en algoritme. Det er også teoretisk eller abstrakt, fordi det har tendens til at ignorere andre faktorer. Sorteringsalgoritme-kompleksitet reduceres typisk til antallet af elementer, der sorteres som værende nøglefaktoren. Dette er fint, men det tager ikke højde for problemer som:
Hukommelsesbrug: en algoritme bruger muligvis meget mere hukommelse end en anden. Afhængigt af situationen kan dette være alt fra fuldstændig irrelevant til kritisk; Omkostninger ved sammenligning: Det kan være, at sammenligning af elementer er virkelig dyrt, hvilket potentielt vil ændre enhver sammenligning mellem algoritmer i den virkelige verden; Omkostninger ved flytning af elementer: Kopiering af elementer er typisk billig, men det er ikke nødvendigvis tilfældet; osv.
Kommentarer
- Det er ikke alt for nyttigt at linke en artikel sammen ‘. Det ‘ er normalt en god idé at omskrive eller citere det afsnit, som du finder særlig relevant for tråden.
- Er nedstemningerne virkelig nødvendige? Den artikel, han linkede, er meget relevant og IMHO temmelig hjælpsom.I mellemtiden er det topstemte svar et link til en Wikipedia-artikel. +1 for at udligne hivehygiejets hykleri.
- -1, fordi kunstneren, selvom den er en meget flot og velskrevet artikel, ikke ‘ t har noget at gøre med spørgsmålet.
- @Jorg, jeg sagde aldrig, at artiklen ville løse problemet, men jeg delte det, fordi jeg havde fundet det nyttigt, da jeg kiggede på disse begreber.
- @topgun_ivard: Hvad sker der så, hvis det bliver til et dødt link? Omskrivning giver 1) publikum på denne tråd mulighed for at få en Coles-noteversion af dit link (tid er penge) og 2) sikrer, at dit indlæg ikke bliver irrelevant på et dødt link.
Svar
EDIT: Viser sig, at jeg tager fejl. Ikke desto mindre hjælper det måske nogen med at holde deres symboler lige, så jeg vil ikke slette det.
Det er faktisk ikke det latinske bogstav Åh det er det græske bogstav Omicron . Desværre har disse to nøjagtigt samme tegn, så den originale version blev over tid ødelagt, og nu er den bare Oh .
Valget af symbol har faktisk ikke nogen særlig betydning, det blev valgt som en mnemonic enhed:
- Omicron har bogstaverne MICRO i sig, og semantikken i Omicron-symbolet betyder stort set “mindre end”
- Omega har bogstaverne MEGA i sig , og semantikken i Omega-symbolet betyder stort set “større end”
- Theta (Θ) ligner et ligetegn , og semantikken i Theta-symbolet betyder omtrent “lig med”
Det er det. Der er ingen reel betydning for det, det er bare et ordspil, hvis du vil, for at hjælpe dig med at huske semantikken mere e asily.
Kommentarer
- Selvom jeg meget gerne vil tro dit mnemoniske forslag (det er en rigtig cool idé), bliver jeg nødt til at se noget bevis for, at dette er den egentlige oprindelige hensigt fra Bachmann. Giv det, og jeg ‘ vil +1 dig.
- @Jonathan Henson: Tilsyneladende blev jeg vildledt af Prof. Knuth 🙂
Svar
“f (x) er stor-oh af g (x)”
Det er en matematisk måde at forudsige væksten af funktioner på.
Lad f og g være funktioner fra sæt af heltal eller sæt eller reelle tal til sæt af reelle tal. Vi siger, at f (x) er O (g (x)), hvis der er konstanter C og k, således at | f (x) | < = C | g (x) | hvor som helst x> k.
Du læser dette som “f (x) er stor-oh af g (x)”
Big-O kaldes undertiden et Landau-symbol efter den tyske matematiker Edmund Landau. Jeg tror ikke, det står for noget ud over det. Du har også de samme store Omega- og Big-Theta-notationer. Symbolerne er så vilkårlige som altid at bruge theta til at betegne vinklerne i dine trekanter var i din gymnasiums planare geometri klasse.
Korrektion @ back2dos har givet en tilfredsstillende forklaring på O som henvisning til ordre. Fantastisk Job. Se hans svar.
Donald Knuth anvendte det til at undersøge kompleksiteten af computerprogrammer.
Hvis du vil finde årsagen til, at notationen blev brugt, skulle du læse
“Analytische Zahlentheorie” af Paul Bachmann fra 1892
Svar
UPDATE: Forsøg på at rydde op i mit svar og være mere præcis
Stor O-notation er en måde at karakterisere funktioner i henhold til deres vækstrater. O står for orden (første orden er n anden orden er n-kvadrat osv.) Og hvis jeg ikke er det fejlagtigt ville dette være det værste tilfælde for en metode runtime (eller lagring) givet N-elementer. Jo større rækkefølge, den værste metode udfører.
For eksempel at finde en post i en matrix er O (1) (jeg tror på en vis implementering af hash-tabeller, hvilket også er tilfældet). Tilføjelse af en værdi i slutningen af en linkliste ville være O (N), fordi du skal komme til slutningen af listen, før du kan tilføje elementet osv.
Dette svar skal være lidt mere korrekt end mit første forsøg 🙂
Kommentarer
- -1 fordi dette bare er gammelt forkert OG besvarede et separat spørgsmål, end der blev stillet. Spørgsmålet var, hvorfor bruges brevet ” O “, ikke ” hvordan fungerer Big O notationsarbejde? “. Du ‘ er forkert i, hvordan Big-oh fungerer så godt, selvom … at løkke gennem en matrix er O (n) hvor n er størrelsen på arrayet, ikke O (1) . Notationen har intet at gøre med ” cyklusser ” af en algoritme … det ‘ en måling af den øvre grænse for en algoritmes løbetid.
- Ikke for at argumentere med dig her, men at ‘ er den slags, hvad jeg mente. Hvad betyder køretid rigtigt?Nå, driftstid bestemmes af, hvad der skal behandles på maskinen. Jeg antager, at jeg slags bruger cyklus liberalt her. Efter cyklus skulle jeg vel have sagt iterate-through eller noget lignende. Du har dog ret i den øvre grænse, men det bestemmer ikke gennemsnittet. Derfor accepterer jeg nedgraderingen.