Co je Big a O v notaci Big O? Přečetl jsem definice a neříká, co se O vyslovuje jako „oh“. Například – chápu, že O (n) je složitost lineárního algoritmu, kde n může být počet operací. ale co je to O ?
Komentáře
- Je to ‚ s 15. písmeno anglické abecedy. Je ‚ také 15. písmenem řecké abecedy.
- Jen pro upřesnění: ‚ hledáte důvod, proč je O použitým symbolem (místo Q nebo E nebo něčeho jiného), a jaký význam má O , pokud existuje, nad jinými symboly?
- @Joel: Ve skutečnosti je to ‚ s Omicronem, a to je vodítko, proč byl vybrán tento konkrétní dopis.
- tato odpověď vyvrací (myslím si) teorii Omicron.
Odpověď
Můj odhad by byl řád, který se shoduje s wikipedií .
Upravit: (můj (ocení se jakákoli vylepšení)) překlad z německého článku o wikipedii
Velké písmeno O (v té době vlastně omicron) jako symbol pro řád (německy: „Ordnung von“) bylo poprvé použito německý teoretik čísel Paul Bachman ve druhém vydání své knihy o teorii analytických čísel se objevil v roce 1894. Zápis získal popularitu díky práci Edmunda Landaua, dalšího německého teoretika čísel, s nímž je tato nomenklatura dnes široce spojována, zejména v Německá terminologie.
Komentáře
- Může se stát, že mnoho matematiků odkazovalo na jako takové to původně nebylo. Pokud čtete knihy o teorii čísel z počátku 20. století, takové vysvětlení nenajdete. Je to to, co to je, a nemohu ‚ číst německy, abych zjistil, jaké je jeho myšlení v notaci.
- @Jonathan: Příspěvek aktualizován.
- Velmi pěkné! Nahlédl jsem do všech svých knih o teorii čísel a nemohl jsem ‚ nikde najít vysvětlení O. +1
- Já ‚ jsem to vždy vyslovoval jako pořadí , protože pouhé vyslovení O neznamená moc.
- Velmi informativní! ale přesto – Proč programátoři O vyslovili jako ‚ oh ‚?
Odpověď
„Velký“ znamená „kapitál“ a „O“ znamená řád, jako v „pořadí složitosti“. Pojmenováno podle konvence psaní „pořadí složitosti“ jako O (f (x)), např. S velkým písmenem „O“ nebo „Big O“. Nikdo o tom moc nemluví, protože „každý“ chápe, co to znamená, a jeho pochopení vám opravdu nepomůže pochopit analýzu složitosti.
Pro pochopení analýzy složitosti si myslím, že odkaz zveřejněný topgun_ivard je dobré místo pro začátek. Může také pomoci dobrá úvodní učebnice pokrývající datové struktury nebo algoritmy.
Komentáře
- I ‚ omlouvám se, ale Bachmann-Landauovu notaci vynalezl německý matematik, takže si stěží myslím, že by ji pojmenoval podle anglického slova. Ve skutečnosti i když ji vynalezl americký matematik, pravděpodobně by byl stále pojmenován podle německého slova, protože když byl vynalezen (myslím, že kolem roku 1920), byl mezinárodním jazykem matematiky němčina. Navíc ‚ i vzdáleně mají něco společného se složitostí.
- @J ö rg: Ano, ale ‚ to prostě musí být Ordnung , o kterém německý článek o wiki tvrdí, že je původem: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @Ethel mohli byste ve svém článku udělat malou změnu, abych vás mohl volit? Opravdu máte pravdu. Než budu moci hlasovat, musíte to upravit.
- @Jonathan,
si nejsem jistý, jakou drobnou změnu chcete. Můžete pokračovat a provést požadovanou úpravu? Nebo bychom mohli nechat back2dos ‚ odpověď stát, vypadá to, že i tak mohl díky nejlepšímu výzkumu skončit s nejlepší odpovědí 🙂
Odpověď
O znamená pořádek.
Původně jej představil německý matematik Paul Bachmann ve druhém svazku svých knih o teorii čísel Die Analytische Zahlentheorie , publikováno v roce 1894 (str. 401) . Poznamenává, podle vzorce, kde nejprve použije notaci:
(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (…)
Můj překlad:
(…) kde se zápisem O (n) my uveďte velikost, jejíž pořadí s odkazem na n nepřesahuje pořadí n (…)
Na rozdíl od toho, co řekli ostatní, nic v jeho textu nenaznačuje, že se ve skutečnosti jedná o řecké hlavní město omikron. Používá spoustu řeckých i latinských znaků, takže to vlastně nelze nijak zjistit. Vzhledem k jeho dalšímu používání „Ordnung n log n “ atd. V textu je jasné, že v každém případě znamená „Ordnung“ (německy „order“), ale to by přesto mohlo ponechat otevřené používání fantastického řeckého O.
Původ omikronu je však pravděpodobněji retronym kvůli Donaldu Knuthovi, který v příspěvku uvedl symboly omega (Ω) a theta (Θ) pro související pojmy Big Omicron a Big Omega a Big Theta , případně Hardy a Littlewood , kteří dříve představili symbol omega.
Komentáře
- Zajímavé. Předpokládám, že máte pravdu. Právě jsem vyhledal definice v knihách Landau ‚ s a Bachmann ‚ a opravdu a) používají latinku Oh, ne a řecký Omikron, b) oba používají slovo “ Ordnung “ a c) Landau výslovně uvádí, že to znamená “ Ordnung „. Stojím opravený.
- Jaké lepší slovo lze najít? Myslím od Němce? Ordnung ist das halbe Leben!
- Myslím, že první věta vaší (správné, upvotované, úžasné) odpovědi by měla znít: ‚ O znamená “ Ordnung “ (německý význam “ objednávka „) . ‚ Tato odpověď by pomohla upoutat pozornost ostatních čtenářů.
Odpovědět
Líbí se mi tento článek a doufám, že by vám byl také užitečný!
Cituji část článku:
Velké řecké dopisy
Velké O je často zneužíváno. Big O or Big Oh je ve skutečnosti zkratka pro Big Omicron. Představuje horní hranici asymptotické složitosti. Pokud je tedy algoritmus O (n log n), existuje konstanta c taková, že horní mez je cn log n.
Θ (n log n) (Big Theta) je pevněji svázána než tato. Takový algoritmus znamená, že existují dvě konstanty c1 a c2, takže c1n log n < f (n) < c2n log n.
Ω (n log n) (Big Omega) říká, že algoritmus má spodní hranici cn log n.
Existují i jiné, ale ty jsou nejběžnější a Big O je nejběžnější společné pro všechny. Takový rozdíl je obvykle nedůležitý, ale stojí za zmínku. Správná notace je koneckonců správná notace.
Co je Big O?
Notace Big O se snaží popsat relativní složitost algoritmu snížením rychlosti růstu na klíč faktory, když klíčový faktor směřuje k nekonečnu. Z tohoto důvodu budete často slyšet frázi asymptotická složitost. Přitom jsou ignorovány všechny ostatní faktory. Jedná se o relativní vyjádření složitosti.
Co není Big O?
Big O není testem výkonu algoritmu. Je také pomyslný nebo abstraktní v tom, že má tendenci ignorovat jiné faktory. Složitost algoritmu řazení je obvykle snížena na počet prvků, které jsou tříděny jako klíčový faktor. To je v pořádku, ale nebere to v úvahu problémy jako:
Využití paměti: jeden algoritmus může využívat mnohem více paměti než jiný. V závislosti na situaci by to mohlo být cokoli od zcela irelevantního po kritické; Náklady na srovnání: Může se stát, že porovnávání prvků je opravdu nákladné, což potenciálně změní jakékoli skutečné srovnání mezi algoritmy; Náklady na přesun prvků: kopírování prvků je obvykle levné, ale nemusí to tak být; atd.
Komentáře
- Pouhé propojení článku není ‚ příliš užitečné. Obvykle je dobré ‚ parafrázovat nebo citovat část, která je pro dané vlákno obzvláště relevantní.
- Jsou hlasy skutečně nutné? Článek, na který odkazoval, je velmi relevantní a IMHO docela užitečný.Nejčastěji hlasovanou odpovědí je odkaz na článek na Wikipedii. +1 k vyrovnání pokrytectví včelí mysli.
- -1, protože artice, i když je velmi pěkným a dobře napsaným článkem, ‚ Nemám nic společného s touto otázkou.
- @Jorg, nikdy jsem neřekl, že článek tento problém vyřeší, ale sdílel jsem to, protože mi při pohledu na tyto koncepty připadalo užitečné,
- @topgun_ivard: Co se stane, když se z toho stane mrtvý odkaz? Parafrázování umožňuje 1) publiku tohoto vlákna získat verzi vašeho odkazu s poznámkami Coles (čas jsou peníze) a 2) zajišťuje, že váš příspěvek nebude na mrtvém odkazu vykreslen jako irelevantní.
Odpověď
EDIT: Ukázalo se, že se mýlím. Možná to ale někomu pomůže, aby jeho symboly byly rovné, takže to „nesmažu“.
Ve skutečnosti to není latinské písmeno Oh , je to řecké písmeno Omicron . Bohužel tito dva mají přesně stejný glyf, takže v průběhu času došlo k poškození původní verze a nyní je to jen Oh .
Volba symbolu ve skutečnosti nemá žádný konkrétní význam, byla vybrána jako mnemotechnické zařízení:
- Omicron obsahuje písmena MICRO a sémantika symbolu Omicron zhruba znamená „menší než“
- Omega má písmena MEGA a sémantika symbolu Omega zhruba znamená „větší než“
- Theta (Θ) vypadá trochu jako znaménko rovnosti a sémantika symbolu Theta zhruba znamená „rovná se“
To je ono. Neexistuje pro něj žádný skutečný význam, je to jen slovní hříčka, pokud will, abyste si lépe zapamatovali sémantiku e asily.
Komentáře
- I když bych rád uvěřil vašemu mnemotechnickému výroku (je to opravdu skvělý nápad), budu muset vidět nějaký důkaz, že se jedná o skutečný původní záměr Bachmanna. Poskytněte to a já vám ‚ dám +1.
- @Jonathan Henson: Zjevně mě profesor Knuth uvedl v omyl 🙂
Odpověď
„f (x) je velké – oh g (x)“
Je matematický způsob, jak předpovědět růst funkcí.
Nechť f a g jsou funkce ze sady celých čísel nebo množiny nebo reálných čísel do množiny reálných čísel. Říkáme, že f (x) je O (g (x)), pokud existují konstanty C a k takové, že | f (x) | < = C | g (x) | všude tam, kde x> k.
Toto byste četli jako „f (x) je velký-oh g (x)“
Velký-O se někdy nazývá Landauův symbol po německý matematik Edmund Landau. Nemyslím si, že to překračuje rámec toho. Máte také podobné notace big-Omega a big-Theta. Symboly jsou stejně libovolné, jako kdykoli pomocí theta k označení úhlů ve vašich trojúhelnících bylo ve vaší střední škole Planar Geometry třída.
Oprava @ back2dos poskytla uspokojivé vysvětlení pro O jako odkaz na objednávku. Skvělé Job. Podívejte se na jeho odpověď.
Donald Knuth to použil ke studiu složitosti počítačových programů.
Pokud chcete zjistit důvod, proč byla notace použita, měli byste si přečíst
„Analytische Zahlentheorie“ od Paula Bachmanna z roku 1892
Odpověď
UPDATE: Pokus o vyčištění mé odpovědi a přesnější
Big O notace je způsob, jak charakterizovat funkce podle tam rostoucích rychlostí. znamená řád (první řád je n druhý řád je n-na druhou atd.). A pokud nejsem mylně by to byl nejhorší scénář pro běhové metody (nebo úložiště) dané N prvky. Čím větší je pořadí, které nejhorší metoda provádí.
Například vyhledávání záznamu v poli je O (1) (věřím v nějakou implementaci hash tabulek, což je také případ). Přidání hodnoty na konec seznamu odkazů by bylo O (N), protože před přidáním prvku se musíte dostat na konec seznamu.
Tato odpověď by měla být o něco správnější než můj první pokus 🙂
Komentáře
- -1, protože se jedná o prostý starý nesprávný A odpověděl na samostatnou otázku, než byl položen. Otázkou bylo, proč se používá písmeno “ O „, nikoli “ jak funguje Big O funguje notace? „. ‚ jste nesprávní v tom, jak funguje i Big-oh … smyčka v poli je O (n), kde n je velikost pole, ne O (1) . Zápis nemá nic společného s “ cykly “ algoritmu … it ‚ je měření horní hranice doby běhu algoritmu.
- zde se s vámi nebudu hádat, ale to je ‚ něco, co jsem myslel. Co znamená doba běhu správně?Doba běhu je určena tím, co musí být na stroji zpracováno. Myslím, že tady trochu liberálně používám cyklus. Podle cyklu jsem měl říct iteraci nebo něco podobného. Máte pravdu ohledně horní hranice, neurčuje průměr. Proto přijímám downgrade.