Ce este Big și O în notația Big O? „Am citit definițiile și nu spune ce se pronunță O ca„ oh ”. De exemplu – înțeleg că O (n) este complexitatea unui algoritm liniar în care n ar putea fi numărul de operații. dar ce este un O ?
Comentarii
- Este ‘ s a 15-a literă a alfabetului englez. ‘ este, de asemenea, a 15-a literă din alfabetul grecesc.
- Doar pentru a clarifica: ‘ căutați motivul pentru care O este simbolul folosit (în loc de Q sau E sau altceva) și ce semnificație, dacă există, O are asupra altor simboluri?
- @Joel: De fapt, este ‘ Omicron și acesta este indiciul de ce a fost aleasă această literă.
- acest răspuns respinge (corect, cred) teoria Omicron.
Răspuns
Ei bine, presupun că ar fi o ordine, care coincide cu Wikipedia .
Editați: (propria mea (orice îmbunătățiri apreciate)) traducere din articol wikipedia german
Litera majusculă O (de fapt un omicron cu majusculă la acea vreme) ca simbol pentru ordinea (germană: „Ordnung von”) a fost folosită pentru prima dată de teoreticianul german al numerelor Paul Bachman în al doilea număr al cărții sale despre teoria analitică a numerelor a apărut în 1894. Notația a câștigat popularitate datorită lucrării lui Edmund Landau, un alt teoretician german al numerelor, cu care această nomenclatură este asociată pe scară largă astăzi, în special în Terminologie germană.
Comentarii
- Deși poate fi cazul la care mulți matematicieni s-au referit ca atare, inițial nu era așa. Dacă citiți cărți de teorie a numerelor de la începutul secolului al XX-lea, nu veți găsi o astfel de explicație. Este ceea ce este și nu pot ‘ să citesc limba germană pentru a afla care a fost gândirea sa despre notație.
- @Jonathan: Post actualizat.
- Foarte frumos! M-am uitat în toate cărțile mele de teorie a numerelor și nu am putut ‘ să găsesc nicăieri o explicație a O. +1
- Eu ‘ l-am pronunțat întotdeauna ca ordinea , deoarece doar a spune O nu înseamnă mult.
- Foarte informativ! dar totuși – De ce O pronunțat ca ‘ oh ‘ de către programatori?
Răspuns
„Big” înseamnă „capital”, iar „O” înseamnă ordine, ca în „ordinea complexității”. Așa numit din cauza convenției de a scrie „ordinea complexității” ca O (f (x)), de exemplu, cu o literă mare „O” sau un „O mare”. Nimeni nu vorbește prea mult despre asta, deoarece „toată lumea” înțelege ce înseamnă și înțelegerea ei nu te ajută cu adevărat să înțelegi analiza complexității.
Pentru o înțelegere a analizei complexității, cred că link-ul postat de topgun_ivard este un un loc bun pentru a începe. Un manual introductiv bun care acoperă structuri de date sau algoritmi ar putea ajuta, de asemenea.
Comentarii
- I ‘ îmi pare rău, dar notația Bachmann-Landau a fost inventată de un matematician german, așa că abia cred că ar fi numit-o după un cuvânt englezesc. De fapt, chiar dacă ar fi fost inventat de un matematician american, probabil că ar fi fost încă numit după un cuvânt german, deoarece atunci când a fost inventat (în jurul anului 1920, cred), limba internațională a matematicii era germana. În plus, nu ‘ chiar și de la distanță nu au nimic de-a face cu complexitatea.
- @J ö rg: Da, dar nu ar ‘ T that just be Ordnung , despre care articolul wiki german susține că este originea: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @Ethel ai putea face o modificare minoră a articolului tău, astfel încât să te pot vota? Ești într-adevăr corect. Trebuie să editați înainte de a putea vota.
- @Jonathan, nu ‘ nu știu exact ce schimbare minoră doriți. Poți să mergi mai departe și să faci editarea dorită? Sau am putea lăsa răspunsul back2dos ‘ să se ridice, se pare că oricum ar fi ajuns să aibă cel mai bun răspuns din cauza unor cercetări excelente 🙂
- Hm , interesant. În Suedia, Big Oh este numit de obicei ” ordo ” (latină pentru, bine, ordine) mai degrabă decât ” ordning ” (cuvântul suedez pentru ordine).
Răspuns
O înseamnă ordine.
A fost inițial introdus de matematicianul german Paul Bachmann în al doilea volum al cărților sale despre teoria numerelor Die Analytische Zahlentheorie , publicat în 1894 (p. 401) . El notează, după o formulă în care folosește prima dată notația:
(…) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung in Bezug auf n die Ordnung von n nicht überschreitet (…)
Traducerea mea:
(…) unde cu notația O (n) vom indicați o mărime a cărei ordine cu referire la n nu depășește ordinea n (…)
Spre deosebire de ceea ce au spus alții, nimic din textul său nu indică faptul că acesta este de fapt un omikron cu capital grecesc. El folosește o mulțime de caractere atât grecești, cât și latine, așa că nu există „nici un fel de a spune. Având în vedere utilizarea continuă a„ Ordnung n log n ”etc. în text, este clar că înseamnă „Ordnung” (în germană pentru „comandă” dacă există vreo îndoială) în orice caz, dar asta ar putea lăsa în continuare deschisă o fantezie grecească O.
Cu toate acestea, originea omikronului este mai probabil un retronim datorat lui Donald Knuth care a introdus simbolurile omega (Ω) și theta (Θ) pentru concepte conexe în lucrarea sa Big Omicron și Big Omega și Big Theta , sau, eventual, Hardy și Littlewood care au introdus mai devreme un simbol omega.
Comentarii
- Interesant. Presupun că ai dreptate. Tocmai am căutat definițiile atât în cărțile Landau ‘ cât și în cele ale lui Bachmann ‘ și, într-adevăr, a) folosesc un Oh latin, nu un Omikron grecesc, b) ambele folosesc cuvântul ” Ordnung ” și c) Landau în mod explicit afirmă că înseamnă ” Ordnung „. Sunt corectat.
- Ce cuvânt mai bun s-ar putea găsi? Adică, dintr-un german? Ordnung ist das halbe Leben!
- Cred că prima propoziție a răspunsului dvs. (corect, susținut, minunat) ar trebui să citească: ‘ O înseamnă ” Ordnung ” (semnificație germană ” Comandă „) . ‘ Ar ajuta acest răspuns să atragă atenția altor cititori.
Răspuns
Îmi place acest articol , sperând că veți găsi și voi util!
Citând o secțiune din articol:
Big Greek Letters
Big O este adesea folosit greșit. Big O sau Big Oh este de fapt scurt pentru Big Omicron. Reprezintă limita superioară a complexității asimptotice. Deci, dacă un algoritm este O (n log n) există o constantă c astfel încât limita superioară este cn log n.
Θ (n log n) (Big Theta) este legat mai strâns decât atât. Un astfel de algoritm înseamnă că există două constante c1 și c2 astfel încât c1n log n < f (n) < c2n log n.
Ω (n log n) (Big Omega) spune că algoritmul are o limită inferioară a cn log n.
Există altele, dar acestea sunt cele mai comune și Big O este cel mai comun tuturor. O astfel de distincție este de obicei lipsită de importanță, dar merită menționată. Notarea corectă este notația corectă, la urma urmei.
Ce este Big O?
Notarea Big O încearcă să descrie complexitatea relativă a unui algoritm prin reducerea ratei de creștere la cheie factori atunci când factorul cheie tinde spre infinit. Din acest motiv, veți auzi adesea expresia complexitate asimptotică. Procedând astfel, toți ceilalți factori sunt ignorați. Este o reprezentare relativă a complexității.
Ce nu este Big O?
Big O nu este un test de performanță al unui algoritm. Este, de asemenea, noțional sau abstract prin faptul că tinde să ignore alți factori. Complexitatea algoritmului de sortare este de obicei redusă la numărul de elemente care sunt sortate ca fiind factorul cheie. Este bine, dar nu ia în considerare probleme precum:
Utilizarea memoriei: un algoritm ar putea folosi mult mai multă memorie decât altul. În funcție de situație, acest lucru ar putea fi de la complet irelevant până la critic; Costul comparației: poate fi că compararea elementelor este într-adevăr costisitoare, ceea ce va schimba orice comparație reală între algoritmi; Costul elementelor în mișcare: copierea elementelor este de obicei ieftină, dar acest lucru nu este neapărat cazul; etc.
Comentarii
- Legarea simplă a unui articol nu este prea utilă. ‘ ‘ Este, de obicei, o idee bună să parafrazeze sau să citeze secțiunea pe care o considerați relevantă în special pentru fir.
- Sunt cu adevărat necesare voturile negative? Articolul pe care l-a legat este foarte relevant și IMHO este destul de util.Între timp, răspunsul cel mai votat este un link către un articol Wikipedia. +1 pentru a compensa ipocrizia minții stupului.
- -1, deoarece artice, deși este un articol foarte frumos și bine scris, nu ‘ Nu am nimic de-a face cu întrebarea.
- @Jorg, nu am spus niciodată că articolul va rezolva problema, dar am împărtășit pentru că îl găsisem util când mă uitam la aceste concepte.
- @topgun_ivard: Deci, ce se întâmplă dacă se transformă într-un link mort? Parafrazarea permite 1) publicului acestui fir să obțină o versiune a notelor Coles a linkului dvs. (timpul înseamnă bani) și 2) asigură faptul că postarea dvs. nu este făcută irelevantă pe un link mort.
Răspuns
EDIT: Se dovedește că mă înșel. Cu toate acestea, poate acest lucru ajută pe cineva să-și păstreze simbolurile drepte, așa că „nu am de gând să-l șterg.
De fapt, nu este nu litera latină Oh , este litera greacă Omicron . Din păcate, cei doi au exact același glif, așa că, în timp, versiunea originală a fost coruptă, iar acum este doar Oh .
Alegerea simbolului nu are de fapt nicio semnificație specială, a fost aleasă ca dispozitiv mnemonic :
- Omicron are literele MICRO în ea, iar semantica simbolului Omicron înseamnă aproximativ „mai mică decât”
- Omega are literele MEGA în ea , iar semantica simbolului Omega înseamnă aproximativ „mai mare decât”
- Theta (Θ) arată un pic ca un semn egal , iar semantica simbolului Theta înseamnă aproximativ „egală cu”
Asta este. Nu există un sens real pentru el, este doar un joc de cuvinte, dacă va, pentru a vă ajuta să vă amintiți semantica mai mult e la fel.
Comentarii
- Deși mi-ar plăcea să cred propunerea ta mnemonică (este o idee foarte interesantă), va trebui să văd unele dovezi că aceasta este intenția originală reală a lui Bachmann. Furnizați-l și vă ‘ vă voi da +1.
- @Jonathan Henson: Se pare că am fost indus în eroare de prof. Knuth 🙂
Răspuns
„f (x) este mare-oh de g (x)”
Este un mod matematic de a prezice creșterea funcțiilor.
Fie f și g funcții de la mulțimea de numere întregi sau mulțimea sau numerele reale la mulțimea numerelor reale. Spunem că f (x) este O (g (x)) dacă există constante C și k astfel încât | f (x) | < = C | g (x) | oriunde x> k.
Ați citi acest lucru ca „f (x) este big-oh de g (x)”
Big-O este uneori numit simbol Landau după matematicianul german Edmund Landau. Nu cred că înseamnă nimic dincolo de asta. Aveți, de asemenea, notații similare Big-Omega și Big-Theta. Simbolurile sunt la fel de arbitrare ca întotdeauna folosirea theta pentru a indica unghiurile din triunghiurile dvs. a fost în liceul dvs. Geometria plană class.
Corecția @ back2dos a oferit o explicație satisfăcătoare pentru O în ceea ce privește ordinea. Job. Vezi răspunsul său.
Donald Knuth l-a aplicat studiului complexității programelor de computer.
Dacă vrei să afli motivul pentru care a fost utilizată notația, ar trebui să citești
„Analytische Zahlentheorie” de Paul Bachmann din 1892
Răspuns
UPDATE: Încercarea de a-mi curăța răspunsul și de a fi mai precisă
Notarea Big O este o modalitate de a caracteriza funcțiile în funcție de ratele de creștere. înseamnă ordine (prima ordine fiind n ordinea a doua fiind n-pătrat etc). Și dacă nu sunt greșit, acesta ar fi cel mai rău scenariu pentru un timp de rulare (sau stocare) al metodelor date de N elemente. Cu cât este mai mare ordinul, cu atât este mai slabă metoda.
De exemplu, căutarea unei înregistrări într-o matrice este O (1) (cred că într-o anumită implementare a unui tabel hash este și cazul). Adăugarea unei valori la sfârșitul unei liste de linkuri ar fi O (N) deoarece trebuie să ajungeți la sfârșitul listei înainte de a putea adăuga elementul etc.
Acest răspuns ar trebui să fie puțin mai corect decât prima mea încercare 🙂
Comentarii
- -1 deoarece acest lucru este pur și simplu incorect ȘI a răspuns la o întrebare separată decât cea pusă. Întrebarea a fost de ce se folosește litera ” O „, nu ” cum funcționează Big O lucrare de notare? „. Sunteți ‘ incorect cu privire la modul în care funcționează Big-oh, deși … buclarea printr-o matrice este O (n) unde n este dimensiunea matricei, nu O (1) . Notarea nu are nimic de-a face cu ” cicluri ” ale unui algoritm … it ‘ este o măsurare a limitei superioare a duratei de rulare a unui algoritm.
- Nu pentru a vă discuta aici, ci ‘ este ceea ce am vrut să spun Ce înseamnă timpul de funcționare corect?Ei bine, timpul de funcționare este determinat de ceea ce trebuie procesat pe mașină. Cred că am un fel de ciclu de utilizare liberal aici. După cicl, cred că ar fi trebuit să spun iterate-through sau ceva de genul acesta. Ai dreptate cu privire la limita superioară, totuși, nu determină media. Prin urmare, accept retrogradarea.