Wat is O in Big O?

Nou, mijn gok zou de volgorde zijn, die samenvalt met wikipedia .

Bewerken: (mijn eigen (eventuele verbeteringen worden gewaardeerd)) vertaling van het Duitse Wikipedia-artikel

De hoofdletter O (destijds eigenlijk een hoofdletter omicron) als symbool voor de orde van (Duits: “Ordnung von”) werd voor het eerst gebruikt door de Duitse getaltheoreticus Paul Bachman verscheen in het tweede nummer van zijn boek over analytische getaltheorie in 1894. De notatie werd populair dankzij het werk van Edmund Landau, een andere Duitse getaltheoreticus, met wie deze nomenclatuur tegenwoordig veel wordt geassocieerd, vooral in de Duitse terminologie.

Reacties

• Hoewel het kan zijn dat veel wiskundigen hebben verwezen naar als zodanig was het oorspronkelijk niet zo. Als je getaltheorieboeken uit het begin van de 20e eeuw leest, zul je zon verklaring niet vinden. Het is wat het is en ik kan ‘ geen Duits lezen om erachter te komen wat hij dacht over de notatie.
• @Jonathan: Bericht bijgewerkt.
• Heel leuk! Ik heb in al mijn getaltheorieboeken gekeken en ik kon ‘ nergens een verklaring van de O vinden. +1
• Ik ‘ heb het altijd uitgesproken als volgorde van omdat alleen O zeggen niet veel betekent.
• Zeer informatief! maar toch – waarom wordt O uitgesproken als ‘ oh ‘ door programmeurs?

“Groot” betekent “hoofdletter”, en “O” betekent volgorde, zoals in “volgorde van complexiteit”. Zo genoemd vanwege de conventie om “volgorde van complexiteit” te schrijven als O (f (x)), bijvoorbeeld met een hoofdletter “O”, of een “Grote O”. Niemand praat er veel over omdat “iedereen” begrijpt wat het betekent, en begrip ervan helpt je niet echt om complexiteitsanalyse te begrijpen.

Voor een goed begrip van complexiteitsanalyse denk ik dat de link geplaatst door topgun_ivard een goede plek om te beginnen. Een goed inleidend leerboek met gegevensstructuren of algoritmen kan ook helpen.

Opmerkingen

• I ‘ zelfs als het was uitgevonden door een Amerikaanse wiskundige, zou het waarschijnlijk nog steeds genoemd zijn naar een Duits woord, want toen het werd uitgevonden (denk ik rond 1920), was de internationale wiskundetaal Duits. Bovendien is het niet ‘ zelfs op afstand heeft iets te maken met complexiteit.
• @J ö rg: Ja, maar zou niet ‘ Dat is gewoon Ordnung , waarvan het Duitse wiki-artikel beweert dat het de oorsprong is: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel kun je een kleine wijziging in je artikel aanbrengen zodat ik je kan stemmen? Je hebt inderdaad gelijk. Je moet eerst bewerken voordat ik kan stemmen.
• @Jonathan, ik ‘ weet niet precies welke kleine wijziging je wilt. Kun je gewoon doorgaan en de gewenste bewerking maken? Of we kunnen het antwoord van back2dos ‘ gewoon laten staan, het lijkt erop dat hij dankzij uitstekend onderzoek toch het beste antwoord heeft gekregen 🙂
• Hm , interessant. In Zweden wordt Big Oh meestal ” ordo ” (Latijn voor, nou ja, volgorde) genoemd in plaats van ” ordning ” (het Zweedse woord voor order).

O staat voor orde.

Het werd oorspronkelijk geïntroduceerd door de Duitse wiskundige Paul Bachmann in het tweede deel van zijn boeken over getaltheorie Die Analytische Zahlentheorie , gepubliceerd in 1894 (p. 401) . Hij merkt op, na een formule waarin hij voor het eerst de notatie gebruikt:

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

Mijn vertaling:

(…) waar we met de notatie O (n) geef een grootte aan waarvan de volgorde met verwijzing naar n niet groter is dan de volgorde van n (…)

In tegenstelling tot wat anderen hebben gezegd, geeft niets in zijn tekst aan dat dit in feite een Griekse hoofdletter omikron is. Hij gebruikt veel zowel Griekse als Latijnse karakters, dus er is niet echt een manier om het te vertellen. Gezien zijn voortdurende gebruik van “Ordnung n log n ” enz. In de tekst, is het duidelijk dat het staat in ieder geval voor “Ordnung” (Duits voor “order” als er enige twijfel was), maar dat zou nog steeds het gebruik van een mooie Griekse O open kunnen laten.

De oorsprong van de omikron is echter waarschijnlijker een retronym vanwege Donald Knuth die de symbolen omega (Ω) en theta (Θ) introduceerde voor gerelateerde concepten in zijn paper Big Omicron en Big Omega en Big Theta , of mogelijk Hardy en Littlewood die eerder een omega-symbool hebben geïntroduceerd.

Opmerkingen

• Interessant. Ik neem aan dat je gelijk hebt. Ik heb zojuist de definities in beide Landau ‘ s en Bachmann ‘ s boeken opgezocht, en ze gebruiken inderdaad a) een Latijnse Oh, niet a Griekse Omikron, b) gebruiken beide het woord ” Ordnung “, en c) Landau expliciet stelt dat het betekent ” Ordnung “. Ik sta gecorrigeerd.
• Welk beter woord kan worden gevonden? Ik bedoel, van een Duitser? Ordnung ist das halbe Leben!
• Ik denk dat de eerste zin van je (juiste, positieve, geweldige) antwoord zou moeten luiden: ‘ O staat voor ” Ordnung ” (Duits betekent ” Order “) . ‘ Het zou dit antwoord helpen om de aandacht van andere lezers te trekken.

Ik vind dit artikel leuk, in de hoop dat jij het ook nuttig zou vinden!

Een gedeelte uit het artikel citeren:
Grote Griekse letters

Grote O wordt vaak misbruikt. Big O of Big Oh is eigenlijk een afkorting voor Big Omicron. Het vertegenwoordigt de bovengrens van asymptotische complexiteit. Dus als een algoritme O (n log n) is, dan bestaat er een constante c zodat de bovengrens cn log n is.

Θ (n log n) (Big Theta) is strakker gebonden dan dat. Zon algoritme betekent dat er twee constanten c1 en c2 bestaan, zodat c1n log n < f (n) < c2n log n.

Ω (n log n) (Big Omega) zegt dat het algoritme een ondergrens heeft van cn log n.

Er zijn andere, maar deze zijn de meest voorkomende en Big O is de meest voorkomende gemeenschappelijk van allemaal. Een dergelijk onderscheid is doorgaans onbelangrijk, maar het is vermeldenswaard. De juiste notatie is tenslotte de juiste notatie.

Wat is Big O?

Big O-notatie tracht de relatieve complexiteit van een algoritme te beschrijven door de groeisnelheid terug te brengen tot de sleutel factoren wanneer de sleutelfactor naar oneindig neigt. Om deze reden zul je vaak de uitdrukking asymptotische complexiteit horen. Daarbij worden alle andere factoren genegeerd. Het is een relatieve weergave van complexiteit.

Wat is niet Big O?

Big O is geen prestatietest van een algoritme. Het is ook fictief of abstract omdat het de neiging heeft andere factoren te negeren. De complexiteit van het sorteeralgoritme wordt doorgaans teruggebracht tot het aantal elementen dat wordt gesorteerd als de belangrijkste factor. Dit is prima, maar het houdt geen rekening met zaken als:

Geheugengebruik: het ene algoritme gebruikt mogelijk veel meer geheugen dan het andere. Afhankelijk van de situatie kan dit van alles zijn, van volledig irrelevant tot kritiek; Kosten van vergelijking: het kan zijn dat het vergelijken van elementen erg duur is, wat mogelijk elke reële vergelijking tussen algoritmen zal veranderen; Kosten van het verplaatsen van elementen: het kopiëren van elementen is doorgaans goedkoop, maar dit is niet noodzakelijk het geval; etc.

Reacties

• Het simpelweg linken van een artikel is niet ‘ niet overdreven nuttig. Het ‘ is meestal een goed idee om de sectie te parafraseren of te citeren die u bijzonder relevant vindt voor de discussie.
• Zijn de neerwaartse stemmen echt nodig? Het artikel dat hij heeft gelinkt, is zeer relevant en IMHO behoorlijk nuttig.Ondertussen is het meest gestemde antwoord een link naar een Wikipedia-artikel. +1 om de hypocrisie van de bijenkorfgeest te compenseren.
• -1, omdat de artice, hoewel het een erg leuk en goed geschreven artikel is, ‘ ik heb niets met de vraag te maken.
• @Jorg, ik heb nooit gezegd dat het artikel het probleem zou oplossen, maar ik heb het gedeeld omdat ik het nuttig vond toen ik naar deze concepten keek.
• @topgun_ivard: Dus wat gebeurt er als het een dode link wordt? Door te parafraseren kan 1) het publiek van deze thread een Coles notes-versie van je link krijgen (tijd is geld), en 2) zorgt ervoor dat je bericht niet irrelevant wordt gemaakt op een dode link.

EDIT: het blijkt dat ik het mis heb. Desalniettemin helpt dit misschien iemand om zijn symbolen recht te houden, dus ik “ga ze niet verwijderen.

Eigenlijk is het niet de Latijnse letter Oh , het is de Griekse letter Omicron . Helaas hebben die twee exact dezelfde glyph, dus na verloop van tijd raakte de originele versie beschadigd, en nu is het alleen Oh .

De keuze van het symbool heeft eigenlijk geen specifieke betekenis, het is gekozen als een geheugensteun apparaat:

• Omicron bevat de letters MICRO, en de semantiek van het Omicron-symbool betekent ruwweg “kleiner dan”
• Omega heeft de letters MEGA erin , en de semantiek van het Omega-symbool betekent ruwweg “groter dan”
• Theta (Θ) lijkt een beetje op een gelijkteken , en de semantiek van het Theta-symbool betekent ongeveer gelijk aan.

Dat is het. Het heeft geen echte betekenis, het is gewoon een woordspeling, als je wil, om u te helpen de semantiek beter te onthouden e asily.

Opmerkingen

• Hoewel ik je geheugensteuntje graag zou willen geloven (het is echt een gaaf idee), moet ik het zien enig bewijs dat dit de werkelijke oorspronkelijke bedoeling van Bachmann is. Verstrek het, en ik ‘ ll +1 u.
• @Jonathan Henson: Blijkbaar werd ik misleid door Prof. Knuth 🙂

“f (x) is groot-oh van g (x)”

Het is een wiskundige manier om de groei van functies te voorspellen.

Laat f en g functies zijn van de verzameling gehele getallen of de verzameling of reële getallen tot de verzameling reële getallen. We zeggen dat f (x) O (g (x)) is als er constanten C en k zijn zodat | f (x) | < = C | g (x) | waar x> k.

Je zou dit lezen als “f (x) is big-oh of g (x)”

De big-O wordt soms een Landau-symbool genoemd naar de Duitse wiskundige Edmund Landau. Ik denk niet dat het voor iets anders staat. Je hebt ook dezelfde grote-Omega- en grote-Theta-notaties. De symbolen zijn net zo willekeurig als het gebruik van theta om de hoeken in je driehoeken aan te duiden in je Planar Geometry op de middelbare school class.

Correctie @ back2dos heeft een bevredigende verklaring gegeven voor de O als verwijzend naar orde. Job. Zie zijn antwoord.

Donald Knuth paste het toe om de complexiteit van computerprogrammas te bestuderen.

Als je de reden wilt vinden waarom de notatie werd gebruikt, lees dan

“Analytische Zahlentheorie” door Paul Bachmann uit 1892

UPDATE: Ik probeer mijn antwoord op te schonen en nauwkeuriger te zijn

Big O-notatie is een manier om functies te karakteriseren op basis van hun groeipercentages. De O staat voor orde (eerste orde is n tweede orde is n-kwadraat enz.) En als ik dat niet ben ten onrechte zou dit het slechtste scenario zijn voor de runtime (of opslag) van een methode op basis van N-elementen. Hoe groter de volgorde, hoe slechter de methode presteert.
Het opzoeken van een record in een array is bijvoorbeeld O (1) (ik geloof in een implementatie van hashtabellen dat ook het geval is). Het toevoegen van een waarde aan het einde van een lijst met links zou O (N) zijn, omdat je aan het einde van de lijst moet komen voordat je het element etc. kunt toevoegen.

Dit antwoord zou iets correcter moeten zijn dan mijn eerste poging 🙂

Opmerkingen

• -1 omdat dit gewoon oud onjuist is EN een aparte vraag beantwoordde dan werd gesteld. De vraag was waarom de letter ” O ” wordt gebruikt, niet ” hoe werkt Big O notatie werk? “. U ‘ heeft echter ook ongelijk over hoe Big-oh werkt … het doorlopen van een array is O (n) waarbij n de grootte van de array is, niet O (1) . De notatie heeft niets te maken met ” cycli ” van een algoritme … het ‘ is een meting van de bovengrens van de looptijd van een algoritme.
• Niet om hier met u in discussie te gaan, maar dat ‘ is een soort van wat ik bedoelde. Wat betekent looptijd toch?Welnu, de looptijd wordt bepaald door wat er op de machine moet worden verwerkt. Ik denk dat ik de cyclus hier vrijelijk gebruik. Per cyclus denk ik dat ik iteratief had moeten zeggen of zoiets. Je hebt echter gelijk over de bovengrens, het bepaalt niet het gemiddelde. Daarom accepteer ik de downgrade.