Mi a nagy és az O a nagy O jelölésben? Elolvastam a definíciókat, és nem mondja el, hogy mi az, amit O nak “ó” -nak ejtenek. Például – megértem, hogy az O (n) egy lineáris algoritmus összetettsége, ahol n lehet a műveletek száma. de mi az a O ?
Megjegyzések
- Ez ‘ s az angol ábécé 15. betűje. ‘ a görög ábécé 15. betűje is.
- Csak annak tisztázása érdekében: Ön ‘ keresi az oka annak, hogy miért az O az a szimbólum, amelyet használunk (Q vagy E vagy valami más helyett), és ha van, akkor az O jelentése más szimbólumokhoz képest?
- @Joel: Valójában ‘ s az Omicron, és ez a nyom arra, hogy miért ezt a betűt választották.
- ez a válasz cáfolja (szerintem helyesen) az Omicron-elméletet.
Válasz
Nos, a találgatásom rend lenne, ami egybeesik a wikipédiával .
Szerkesztés: (saját (minden fejlesztés értékelhető)) fordítás a német wikipédia cikkből
Az O nagybetűt (akkoriban valójában nagybetűs omicron) a rend nek (németül: “Ordnung von”) szimbólumaként először az elemző számelméletről szóló könyvének második számában, Paul Bachman német számelméletíró 1894-ben jelent meg 1894-ben. A jelölés Edmund Landau, egy másik német számteoretikus munkája révén vált népszerűvé, akivel ez a nómenklatúra ma széles körben kapcsolódik, különösen a Német terminológia.
Megjegyzések
- Bár előfordulhat, hogy sok matematikus utalt rá mint olyan, eredetileg nem az volt. Ha elolvassa a 20. század eleji számelméleti könyveket, nem talál ilyen magyarázatot. Ez az, ami van, és ‘ nem tudok németül olvasni, hogy kiderüljön, mi volt a gondolata a jelöléssel.
- @Jonathan: A bejegyzés frissítve.
- Nagyon szép! Megnéztem az összes számelméleti könyvemet, és sehol nem találtam ‘ az O magyarázatát. +1
- Én ‘ mindig a sorrendnek mondtam, mivel csak az O kimondása nem sokat jelent.
- Nagyon informatív! de mégis – Miért O-t ‘ oh ‘ -nek ejtik a programozók?
Válasz
A “nagy” jelentése “nagybetű”, az “O” pedig rend, mint a “bonyolultsági sorrendben”. Így nevezték el a “bonyolultsági sorrend” O (f (x)) -ként való írásmódja miatt, például nagy “O” vagy “Big O” betűvel. Senki nem beszél róla sokat, mert “mindenki” megérti, hogy mit jelent, és annak megértése nem igazán segít megérteni a bonyolultsági elemzést.
A bonyolultsági elemzés megértéséhez azt gondolom, hogy a topgun_ivard által közzétett link egy jó hely a kezdéshez. Az adatstruktúrákat vagy algoritmusokat bemutató bevezető tankönyv is segíthet.
Megjegyzések
- I ‘ sajnálom, de a Bachmann-Landau jelölést egy német matematikus találta ki, így aligha gondolom, hogy egy angol szó után nevezte volna el. Valójában akkor is, ha amerikai matematikus, valószínűleg még mindig egy német szóról nevezték volna el, mert amikor feltalálták (szerintem 1920 körül), a matematika nemzetközi nyelve német volt. Ráadásul nem ‘ t még távolról is köze van a komplexitáshoz.
- @J ö rg: Igen, de nem lenne ‘ t, hogy csak Ordnung , amelynek eredete a német wiki cikk szerint: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @Ethel tudna kisebb változtatásokat eszközölni a cikkében, hogy megszavazhassalak? Valóban igazad van. Szerkesztenie kell, mielőtt szavazni tudnék.
- @Jonathan, nem vagyok ‘ biztos abban, hogy pontosan milyen kisebb változtatást szeretne. Csak folytathatja a kívánt szerkesztést? Vagy egyszerűen hagyhatnánk a back2dos ‘ válaszállást, úgy tűnik, hogy kiváló kutatások miatt egyébként is a legjobb választ tudta elérni 🙂
- Hm , érdekes. Svédországban a Big Oh-t általában ” ordo ” (latinul, nos, rendre) helyett ordning ” (a svéd sorrend szó).
Válasz
O a rendet jelenti.
Eredetileg Paul Bachmann német matematikus vezette be számelméleti könyveinek második kötetébe Die Analytische Zahlentheorie , megjelent 1894-ben (401. o.) . Megjegyzi egy képlet után, ahol először használja a jelölést:
(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (…)
Az én fordításom:
(…) ahol a O (n) jelöléssel jelezzen egy nagyságrendet, amelynek n re hivatkozó sorrendje nem haladja meg a n (…)
A mások által elmondottakkal ellentétben a szövegében semmi sem utal arra, hogy ez valójában görög fővárosi omikron. Rengeteg görög és latin karaktert használ, így ezt valójában semmilyen módon nem lehet megmondani. Tekintettel arra, hogy a szövegben továbbra is használja az “Ordnung n log n ” stb. Szöveget, egyértelmű, hogy ez minden esetben az “Ordnung” (németül a “rend” -et jelenti, ha kétség merülne fel), de ez továbbra is nyitva hagyhatja a divatos görög O használatát.
Az omikron eredete azonban nagyobb valószínűséggel egy utószó Donald Knuth miatt, aki
Big Omicron, Big Omega és Big Theta cikkében bevezette az omega (Ω) és a theta (Θ) szimbólumokat a kapcsolódó fogalmakra. , vagy esetleg Hardy és Littlewood , akik korábban omega szimbólumot vezettek be.
Megjegyzések
- Érdekes. Gondolom igazad van. Most kerestem meg a definíciókat mind a Landau ‘ s, mind a Bachmann ‘ könyvekben, és valóban a) használnak egy latin Oh, nem egy görög Omikron, b) mindkettő az ” Ordnung ” szót használja, és c) Landau kifejezetten kijelenti, hogy jelentése: ” Ordnung “. Kijavítva állok.
- Milyen jobb szót lehetne találni? Mármint németből? Ordnung ist das halbe Leben!
- Úgy gondolom, hogy a helyes (helyes, felértékelt, félelmetes) válaszod első mondata a következő legyen: ‘ O a ” Ordnung ” (német jelentése ” Order “) . ‘ Ez a válasz segít felkelteni más olvasók figyelmét.
Válasz
Tetszik ez a cikk , remélve, hogy Ön is hasznosnak találja!
Idézve egy szakaszt a cikkből:
Nagy görög levelek
A Big O-t gyakran visszaélik. A Big O vagy a Big Oh valójában a Big Omicron rövidítése. Az aszimptotikus komplexitás felső határát képviseli. Tehát ha egy algoritmus O (n log n), akkor létezik olyan c állandó, hogy a felső határ cn log n.
Θ (n log n) (Big Theta) ennél szorosabban kötött. Egy ilyen algoritmus azt jelenti, hogy két c1 és c2 konstans létezik, így a c1n log n < f (n) < c2n log n.
Ω (n log n) (Big Omega) azt mondja, hogy az algoritmusnak alacsonyabb a cn log n határa.
Vannak mások is, de ezek a leggyakoribbak és a Big O a legtöbb mindennél közös. Egy ilyen megkülönböztetés általában nem fontos, de érdemes megjegyezni. A helyes jelölés végül is a helyes jelölés.
Mi a nagy O?
A Big O jelölés az algoritmus relatív bonyolultságának leírására törekszik azáltal, hogy a növekedési sebességet kulcsra csökkenti. tényezők, amikor a kulcsfontosságú tényező a végtelen felé tart. Emiatt gyakran hallja az aszimptotikus bonyolultság kifejezést. Ennek során az összes többi tényezőt figyelmen kívül hagyják. A komplexitás relatív ábrázolása.
Mi nem a nagy O?
A Big O nem algoritmus teljesítménytesztje. Feltételezett vagy elvont abban a tekintetben is, hogy más tényezőket figyelmen kívül hagy. A rendezési algoritmus bonyolultsága általában a rendezett elemek számára csökken, mint kulcsfontosságú tényező. Ez rendben van, de nem veszi figyelembe az olyan kérdéseket, mint:
Memóriahasználat: az egyik algoritmus sokkal több memóriát használhat, mint a másik. A helyzettől függően ez teljesen irreleváns és kritikus lehet; Összehasonlítás költsége: Előfordulhat, hogy az elemek összehasonlítása valóban drága, ami potenciálisan megváltoztatja az algoritmusok valós összehasonlítását; Az elemek mozgatásának költsége: az elemek másolása általában olcsó, de ez nem feltétlenül így van; stb.
Megjegyzések
- Egy cikk egyszerű összekapcsolása nem túl hasznos.
‘ általában jó átfogalmazni vagy idézni azt a szakaszt, amelyet a szál szempontjából különösen relevánsnak találsz.
Válasz
SZERKESZTÉS: Kiderült, hogy tévedtem. Mindazonáltal, ez talán segít valakinek a szimbólumaikat egyenesen tartani, ezért nem fogom törölni.
Valójában ez nem nem a latin betű Ó , ez a görög Omicron betű. Sajnos ennek a kettőnek pontosan ugyanaz a karakterjele, így idővel az eredeti verzió megsérült, és most csak Oh .
A szimbólumválasztásnak tulajdonképpen nincs különösebb jelentése, memo eszközként választották:
- Omicron a MICRO betűket tartalmazza, és az Omicron szimbólum szemantikája nagyjából azt jelenti, hogy “kisebb, mint”
- Omega MEGA betűket tartalmaz , és az Omega szimbólum szemantikája nagyjából annyit jelent, hogy “nagyobb, mint”
- Theta (Θ) kissé egyenlőségjelnek tűnik , és a Theta szimbólum szemantikája nagyjából annyit jelent, hogy “egyenlő”
Ez az. Ez nincs. Valódi jelentése nincs, csak játék a szavakkal, ha lesz, hogy jobban emlékezzünk a szemantikára e Asszisztensen.
Megjegyzések
- Bár nagyon szeretnék hinni mnemonikus javaslatának (ez nagyon jó ötlet), mégis látnom kell némi bizonyíték arra, hogy ez Bachmann tényleges eredeti szándéka. Adja meg, és én ‘ + 1-ezlek.
- @Jonathan Henson: Nyilvánvalóan Knuth professzor félrevezetett 🙂
Válasz
“f (x) nagy-ó a g (x)”
matematikai módszer a függvények növekedésének előrejelzésére.
Legyenek f és g függvények az egészek halmazától vagy a halmaz vagy a valós számoktól a valós számok halmazáig. Azt mondjuk, hogy f (x) O (g (x)), ha vannak olyan C és k konstansok, amelyek | f (x) | < = C | g (x) | bárhol x> k.
Ezt úgy olvassa el, hogy “f (x) a g (x) nagy-ó”
A nagy-O-t néha Landau szimbólumnak hívják a német matematikus Edmund Landau. Nem hiszem, hogy ezen kívül bármi más is áll. Önnek is vannak hasonló nagy-Omega és nagy-Theta jelölései. A szimbólumok ugyanolyan önkényesek, mint mindig a theta segítségével a háromszögek szögeit jelölték a középiskolai síkgeometriában. osztály.
Javítás @ back2dos kielégítő magyarázatot adott az O-ra, mint a megrendelésre. Job. Lásd a válaszát.
Donald Knuth alkalmazta a számítógépes programok összetettségének tanulmányozására.
Ha meg szeretné találni a jelölés használatának okát, olvassa el a
“Analytische Zahlentheorie”, Paul Bachmann 1892-ből
Válasz
UPDATE: Megpróbálom megtisztítani a válaszomat és pontosabbá tenni
A Big O jelölés a funkciók jellemzésének módja az ottani növekedési ütemek szerint. a rendet jelenti (az első rend n másodrendű, n-es négyzet stb.) És ha nem tévesen ez lenne a legrosszabb forgatókönyv olyan módszerek futásidejéhez (vagy tárolásához), amelyek N elemet kapnak. Minél nagyobb a sorrend, a módszer a legrosszabbul hajtja végre.
Például egy tömbben egy rekordot kereshet az O (1) (hiszek abban, hogy a kivonat táblák néhány megvalósításában ez a helyzet is). Érték hozzáadása a linklista végéhez O (N) lenne, mert az elem stb. Hozzáadása előtt el kell jutnia a lista végére.
Ennek a válasznak valamivel helyesebbnek kell lennie, mint első próbálkozásom 🙂
Megjegyzések
- -1, mert ez egyszerűen régi hibás ÉS külön kérdésre válaszolt, mint feltették. A kérdés az volt, hogy miért használják a ” O ” betűt, és nem a ” betűt? O jelölési munka? “. ‘ tévedsz a Big-oh működéséről, bár … egy tömbön való hurok O (n), ahol n a tömb mérete, nem O (1) . A jelölésnek semmi köze egy algoritmus ” ciklusaihoz ” … ez ‘ az algoritmus futási idejének felső határának mérése.
- Nem azért, hogy itt vitatkozzak veled, hanem hogy ‘ amire gondoltam. Mit jelent a futási idő ugye?Nos, a futási időt az határozza meg, hogy mit kell feldolgozni a gépen. Azt hiszem, itt egyfajta bőséges ciklust használok. Ciklus szerint azt kellett volna mondanom, hogy ismételje meg az egészet, vagy valami hasonló. A felső határral kapcsolatban igazad van, ez nem határozza meg az átlagot. Ezért elfogadom a leminősítést.