Cosè O in Big O?

Beh, la mia ipotesi sarebbe lordine, che coincide con wikipedia .

Modifica: (la mia (eventuali miglioramenti apprezzati)) traduzione dall articolo tedesco di wikipedia

La lettera maiuscola O (in realtà un omicron maiuscolo allepoca) come simbolo per l ordine (tedesco: “Ordnung von”) fu usata per la prima volta da il teorico dei numeri tedesco Paul Bachman nel secondo numero del suo libro sulla teoria analitica dei numeri apparve nel 1894. La notazione guadagnò popolarità grazie al lavoro di Edmund Landau, un altro teorico dei numeri tedesco, a cui questa nomenclatura è ampiamente associata oggi, specialmente nel Terminologia tedesca.

Commenti

• Anche se è possibile che molti matematici abbiano fatto riferimento in quanto tale, in origine non lo era. Se leggi i libri di teoria dei numeri dallinizio del XX secolo, non troverai alcuna spiegazione del genere. È quello che è e non posso ‘ t leggere il tedesco per capire quale fosse il suo pensiero sulla notazione.
• @Jonathan: Post updated.
• Molto carino! Ho guardato in tutti i miei libri di teoria dei numeri e non sono riuscito a ‘ trovare una spiegazione della O da nessuna parte. +1
• I ‘ lho sempre pronunciato come ordine di perché solo dire O non significa molto.
• Molto istruttivo! ma ancora – Perché O pronunciato come ‘ oh ‘ dai programmatori?

“Grande” significa “capitale” e “O” significa ordine, come in “ordine di complessità”. Così chiamato a causa della convenzione di scrivere “ordine di complessità” come O (f (x)), ad esempio, con una lettera maiuscola “O” o una “O grande”. Nessuno ne parla molto perché “tutti” capiscono cosa significa e comprenderlo non “ti aiuta veramente a capire lanalisi della complessità.

Per una comprensione dellanalisi della complessità, penso che il link pubblicato da topgun_ivard sia un buon punto di partenza. Potrebbe essere utile anche un buon libro di testo introduttivo che copra strutture dati o algoritmi.

Commenti

• I ‘ mi dispiace, ma la notazione Bachmann-Landau è stata inventata da un matematico tedesco, quindi difficilmente penso che lavrebbe chiamata dopo una parola inglese. Infatti, anche se fosse stata inventata da un matematico americano, probabilmente avrebbe ancora preso il nome da una parola tedesca, perché quando fu inventato (intorno al 1920, credo), la lingua internazionale della matematica era il tedesco. Inoltre, non ‘ t anche remoto ha qualcosa a che fare con la complessità.
• @J ö rg: Sì, ma ‘ t che sia solo Ordnung , che larticolo tedesco del wiki sostiene essere lorigine: de.wikipedia.org/wiki/Landau-Symbole#Geschichte
• @Ethel potresti apportare una piccola modifica al tuo articolo in modo che io possa votarti? Hai davvero ragione. Devi modificare prima che io possa votare.
• @Jonathan, ‘ non sono sicuro di quale piccola modifica desideri. Puoi semplicemente andare avanti e apportare la modifica che desideri? Oppure, potremmo semplicemente lasciare che back2dos ‘ risponda, sembra che comunque potrebbe aver trovato la risposta migliore a causa di alcune ricerche eccellenti 🙂
• Hm , interessante. In Svezia, Big Oh viene solitamente chiamato ” ordo ” (latino per, beh, order) anziché ” ordning ” (la parola svedese per ordine).

O sta per ordine.

È stato originariamente introdotto dal matematico tedesco Paul Bachmann nel il secondo volume dei suoi libri sulla teoria dei numeri Die Analytische Zahlentheorie , pubblicato nel 1894 (p. 401) . Nota, dopo una formula in cui usa per la prima volta la notazione:

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

La mia traduzione:

(…) dove con la notazione O (n) noi indicare una grandezza di cui lordine con riferimento a n non supera lordine di n (…)

Contrariamente a quanto hanno detto altri, nulla nel suo testo indica che questo sia in realtà un omikron capitale greco. Usa molti caratteri greci e latini, quindi non cè modo di saperlo. Dato il suo continuo uso di “Ordnung n log n ” ecc. Nel testo, è chiaro che sta per “Ordnung” (tedesco per “ordine” se cera qualche dubbio) in ogni caso, ma ciò potrebbe comunque lasciare aperto luso di una fantasia O greca.

Tuttavia, lorigine dellomikron è più probabilmente un retronym dovuto a Donald Knuth che ha introdotto i simboli omega (Ω) e theta (Θ) per concetti correlati in il suo articolo Big Omicron e Big Omega e Big Theta , o forse Hardy e Littlewood che hanno introdotto un simbolo omega in precedenza.

Commenti

• Interessante. Suppongo tu abbia ragione. Ho appena cercato le definizioni in entrambi i libri di Landau ‘ e Bachmann ‘, e in effetti a) usano un latino Oh, no un greco Omikron, b) entrambi utilizzano la parola ” Ordnung ” e c) Landau esplicitamente afferma che significa ” Ordnung “. Sono stato corretto.
• Quale parola migliore si potrebbe trovare? Voglio dire, da un tedesco? Ordnung ist das halbe Leben!
• Penso che la prima frase della tua risposta (corretta, positiva, fantastica) dovrebbe essere: ‘ O sta per ” Ordnung ” (significato tedesco ” Ordine “) . ‘ Aiuterebbe questa risposta ad attirare lattenzione di altri lettori.

Mi piace questo articolo , sperando che lo trovi utile anche tu!

Citando una sezione dellarticolo:
Big Greek Letters

Big O è spesso usato in modo improprio. Big O o Big Oh è in realtà labbreviazione di Big Omicron. Rappresenta il limite superiore della complessità asintotica. Quindi se un algoritmo è O (n log n) esiste una costante c tale che il limite superiore è cn log n.

Θ (n log n) (Big Theta) è più strettamente legato di quello. Un algoritmo di questo tipo significa che esistono due costanti c1 e c2 tali che c1n log n < f (n) < c2n log n.

Ω (n log n) (Big Omega) dice che lalgoritmo ha un limite inferiore di cn log n.

Ce ne sono altri ma questi sono i più comuni e Big O è il più comune a tutti. Una tale distinzione in genere non è importante, ma vale la pena notare. La notazione corretta è la notazione corretta, dopotutto.

Cosè Big O?

La notazione Big O cerca di descrivere la complessità relativa di un algoritmo riducendo il tasso di crescita alla chiave fattori quando il fattore chiave tende verso linfinito. Per questo motivo, sentirai spesso la frase complessità asintotica. In tal modo, tutti gli altri fattori vengono ignorati. È una rappresentazione relativa della complessità.

Che cosa non è Big O?

Big O non è un test delle prestazioni di un algoritmo. È anche nozionale o astratto in quanto tende a ignorare altri fattori. La complessità dellalgoritmo di ordinamento è tipicamente ridotta al numero di elementi ordinati come fattore chiave. Questo va bene ma non prende in considerazione problemi come:

Utilizzo della memoria: un algoritmo potrebbe utilizzare molta più memoria di un altro. A seconda della situazione, questo potrebbe essere qualsiasi cosa, da completamente irrilevante a critico; Costo del confronto: può essere che il confronto degli elementi sia molto costoso, il che potrebbe cambiare qualsiasi confronto nel mondo reale tra algoritmi; Costo dello spostamento di elementi: la copia di elementi è in genere economica, ma non è necessariamente così; ecc.

Commenti

• Il semplice collegamento di un articolo non è ‘ eccessivamente utile. ‘ di solito è una buona idea parafrasare o citare la sezione che trovi particolarmente rilevante per il thread.
• I voti negativi sono davvero necessari? Larticolo che ha collegato è molto pertinente e IMHO molto utile.Nel frattempo, la risposta più votata è un collegamento a un articolo di Wikipedia. +1 per compensare lipocrisia della mente-alveare.
• -1, perché larticolo, pur essendo un articolo molto carino e ben scritto, non ‘ Non ho niente a che fare con la domanda.
• @Jorg, non ho mai detto che larticolo avrebbe risolto il problema, ma lho condiviso perché lavevo trovato utile guardando questi concetti.
• @topgun_ivard: Allora cosa succede se si trasforma in un collegamento morto? La parafrasi consente 1) al pubblico di questo thread di ottenere una versione delle note di Coles del tuo link (il tempo è denaro), e 2) assicura che il tuo post non sia reso irrilevante su un link morto.

EDIT: Si scopre che mi sbaglio. Tuttavia, forse questo aiuta qualcuno a mantenere integri i propri simboli, quindi non ho intenzione di cancellarli.

In realtà, non è la lettera latina Oh , è la lettera greca Omicron . Sfortunatamente, quei due hanno lo stesso identico glifo, quindi, nel tempo, la versione originale è stata danneggiata e ora è solo Oh .

La scelta del simbolo in realtà non ha alcun significato particolare, è stata scelta come dispositivo mnemonico :

• Omicron contiene le lettere MICRO e la semantica del simbolo Omicron significa più o meno “minore di”
• Omega contiene le lettere MEGA e la semantica del simbolo Omega significa più o meno “più grande di”
• Theta (Θ) assomiglia un po a un segno di uguale , e la semantica del simbolo Theta significa più o meno “uguale a”

Questo è tutto. Non cè un vero significato, è solo un gioco di parole, se tu will, per aiutarti a ricordare la semantica più e asily.

Commenti

• Anche se mi piacerebbe credere alla tua proposta mnemonica (è unidea davvero interessante), avrò bisogno di vedere qualche prova che questa è leffettiva intenzione originaria di Bachmann. Forniscilo e io ‘ ti +1.
• @Jonathan Henson: A quanto pare, sono stato ingannato dal Prof. Knuth 🙂

“f (x) è grande-oh di g (x)”

È un modo matematico per prevedere la crescita delle funzioni.

Siano feg funzioni dallinsieme di numeri interi o dallinsieme o dai numeri reali allinsieme dei numeri reali. Diciamo che f (x) è O (g (x)) se ci sono costanti C e k tali che | f (x) | < = C | g (x) | dovunque x> k.

Dovresti leggerlo come “f (x) è grande-oh di g (x)”

La O grande è talvolta chiamata simbolo di Landau dopo il matematico tedesco Edmund Landau. Non penso che stia per qualcosa al di là di questo. Hai anche le simili notazioni Omega grande e Theta grande. I simboli sono arbitrari come sempre luso di theta per denotare gli angoli nei tuoi triangoli era nella tua geometria planare del liceo class.

Correzione @ back2dos ha fornito una spiegazione soddisfacente per la O come riferimento allordine. Ottimo Giobbe. Vedi la sua risposta.

Donald Knuth lha applicata allo studio della complessità dei programmi per computer.

Se vuoi scoprire il motivo per cui è stata usata la notazione, dovresti leggere

“Analytische Zahlentheorie” di Paul Bachmann dal 1892

AGGIORNAMENTO: Tentativo di ripulire la mia risposta e di essere più accurato

La notazione O grande è un modo per caratterizzare le funzioni in base ai tassi di crescita. La O sta per ordine (il primo ordine è n secondo ordine è n-quadrato ecc.) E se non lo sono erroneamente questo sarebbe lo scenario peggiore per un runtime di metodi (o archiviazione) dati N elementi. Più grande è lordine, peggiore è lesecuzione del metodo.
Ad esempio, la ricerca di un record in un array è O (1) (credo che in qualche implementazione di tabelle hash sia anche il caso). Aggiungere un valore alla fine di un elenco di collegamenti sarebbe O (N) perché devi arrivare alla fine dellelenco prima di poter aggiungere lelemento ecc.

Questa risposta dovrebbe essere leggermente più corretta di il mio primo tentativo 🙂

Commenti

• -1 perché questo è semplicemente un vecchio errore E ha risposto a una domanda separata da quella che è stata posta. La domanda era: perché viene utilizzata la lettera ” O ” e non ” come fa Big O la notazione funziona? “. ‘ non sei corretto su come funziona Big-oh anche se … il ciclo attraverso un array è O (n) dove n è la dimensione dellarray, non O (1) . La notazione non ha nulla a che fare con i ” cicli ” di un algoritmo … esso ‘ una misura del limite superiore del tempo di esecuzione di un algoritmo.
• Non per discutere con te qui, ma questo ‘ è il tipo di ciò che intendevo. Cosa significa tempo di esecuzione giusto?Bene, il tempo di esecuzione è determinato da ciò che deve essere elaborato sulla macchina. Immagino di usare il ciclo liberamente qui. Per ciclo immagino che avrei dovuto dire iterazione o qualcosa del genere. Hai ragione sul limite superiore però, non determina la media. Pertanto accetto il downgrade.