Che cos'è Big e O nella notazione Big O? Ho letto le definizioni e non dice cosa sia O pronunciato come 'oh'. Ad esempio, capisco che O (n) è la complessità di un algoritmo lineare in cui n potrebbe essere il numero di operazioni. ma cos'è un O ?
Bene, la mia ipotesi sarebbe l'ordine, che coincide con wikipedia .
Modifica: la traduzione (la mia (qualsiasi miglioramento apprezzato)) dal articolo tedesco di Wikipedia
The capital letter O (actually a capital omicron at the time) as a symbol for the order of (German: "Ordnung von") was first used by the German number theorist Paul Bachman in the second issue of his book on analytic number theory appeared in 1894. The notation gained popularity due to the work of Edmund Landau, another German number theorist, whom this nomenclature is widely associated with today, especially in the German terminology.
"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 "Big O". Nessuno ne parla molto perché "tutti" capiscono cosa significa, e la sua comprensione non aiuta davvero a capire l'analisi della complessità.
Per capire l'analisi della complessità, penso che il link pubblicato da topgun_ivard sia un buon punto di partenza. Potrebbe anche essere utile un buon manuale introduttivo che copra strutture dati o algoritmi.
O sta per ordine.
È stato originariamente introdotto dal matematico tedesco Paul Bachmann in il secondo volume dei suoi libri sul numero teoria Die Analytische Zahlentheorie , pubblicata nel 1894 (pagina 401) . Osserva, 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:
(...) where with the notation O(n) we indicate a magnitude of which the order with reference to n does not exceed the order of n (...)
In contrasto con ciò che altri hanno detto, nulla nel suo testo indica che questo è in realtà un omikron della capitale greca. Usa molti caratteri greci e latini, quindi non c'è davvero alcun modo di dirlo. Dato il suo uso continuato di "Ordnung n log n " ecc. Nel testo è chiaro che sta per "Ordnung" (in tedesco per "ordinare" se c'era qualche dubbio) in ogni caso, ma che potrebbe ancora lasciare aperto l'uso di un elegante O greco.
Tuttavia, l'origine dell'omikron è più probabilmente un retronime dovuto a Donald Knuth che ha introdotto i simboli omega (Ω) e theta (Θ) per concetti correlati in la sua carta Big Omicron e Big Omega e Big Theta , o forse Hardy e Littlewood che hanno introdotto un simbolo omega in precedenza.
Mi piace questo articolo , sperando che tu possa trovare anche utile!
Citando una sezione dall'articolo:
Grandi lettere greche
Il Big O viene spesso usato in modo improprio. Big O o Big Oh è in realtà l'abbreviazione 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 a quello. Un tale algoritmo 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 l'algoritmo ha un limite inferiore di cn log n.
Ce ne sono altri, ma questi sono i più comuni e Big O è il più comune di tutti. Tale distinzione è tipicamente irrilevante, ma vale la pena di notare. La notazione corretta è la notazione corretta, dopotutto.
Che cos'è Big O?
La notazione di Big O cerca di descrivere la complessità relativa di un algoritmo riducendo il tasso di crescita ai fattori chiave quando il fattore chiave tende all'infinito. 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à dell'algoritmo di ordinamento viene in genere ridotta al numero di elementi ordinati come fattore chiave. Questo va bene, ma non tiene conto di 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 irrilevante a critica; Costo del confronto: può essere che confrontare gli elementi sia davvero costoso, il che potenzialmente cambierà qualsiasi confronto tra gli algoritmi nel mondo reale; Costo degli elementi in movimento: copiare elementi è in genere economico, ma non è necessariamente il caso; ecc.
"f (x) è grande-oh di g (x)"
È un modo matematico per prevedere la crescita delle funzioni.
Sia f e g le funzioni dall'insieme di numeri interi o il numero impostato o reale all'insieme di numeri reali. Diciamo che f (x) è O (g (x)) se ci sono costanti C e k tali che | f (x) | < = C | g (x) | ovunque x > k.
Si leggerà come "f (x) è grande-oh di g (x)"
Il big-O è talvolta chiamato un simbolo Landau dopo il matematico tedesco Edmund Landau. Non penso che significhi qualcosa oltre a questo. Hai anche le notazioni simili a omega grande e grande-Theta. I simboli sono arbitrari come sempre usando theta per indicare gli angoli dei triangoli nella classe Planar Geometry del liceo.
Correzione @ back2dos ha fornito una spiegazione soddisfacente per la O come riferimento all'ordine. Ottimo lavoro. Guarda la sua risposta.
Donald Knuth l'ha applicato allo studio della complessità dei programmi per computer.
Se vuoi trovare il motivo per cui è stata usata la notazione, dovresti leggere
"Analytische Zahlentheorie" di Paul Bachmann del 1892
EDIT: Risulta che ho torto. Tuttavia, forse questo aiuta qualcuno a mantenere i loro simboli dritti, quindi non ho intenzione di cancellarlo.
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 corrotta, e ora è solo Oh .
La scelta del simbolo in realtà non ha alcun significato particolare, è stata scelta come dispositivo mnemonico :
Questo è tutto. Non c'è un vero significato, è solo un gioco di parole, se vuoi, per aiutarti a ricordare la semantica più facilmente.
UPDATE: tentativo di ripulire la mia risposta ed essere più precisi
La notazione Big O è un modo per caratterizzare le funzioni in base ai tassi di crescita esistenti. L'O sta per ordine (il primo ordine è n secondo ordine essendo n-quadrato ecc.). E se non sbaglio, questo sarebbe lo scenario peggiore per un metodo runtime (o storage) dato N elementi. Maggiore è l'ordine peggiore è il metodo eseguito.
Ad esempio, la ricerca di un record in un array è O (1) (credo che in alcune implementazioni di tabelle hash sia anche il caso). Aggiungere un valore alla fine di una lista di link sarebbe O (N) perché devi arrivare alla fine della lista prima di poter aggiungere l'elemento ecc.
Questa risposta dovrebbe essere leggermente più corretta del mio primo tentativo:)
Leggi altre domande sui tag complexity big-o