Perché la definizione formale di notazione Big O è formulata come tale?

Questa è una definizione estremamente strana ed è in realtà una novità per me. I simboli, come definiti da Bachmann e Landau, non sono definiti in questo modo.

Sfortunatamente, la Wikipedia wikipedia è l'unica fonte, posso trovare esattamente questo, al momento, ma suppongo che tu possa vedere senza molta traduzione, che è definito come .
(Nota: il french wikipedia ha la seguente definizione simile ,chesuppongofondamentalmentelostesso,anchesepensochenonsiacorretto,datochef(n)èqualcosadicompletamentediversodaf).

Comehospiegatoinrispostaaunadomandadiversa, O significa "l'ordine di" , e quindi O (g) è in realtà l'insieme di tutte le funzioni, che hanno lo stesso ordine di g. Ha senso solo dire:

• f è lo stesso ordine di g (o più esplicitamente: l'ordine di f è l'ordine di g), che è O (f) = O (g)
• f è nell'ordine di g, che si traduce in f ∈ O (g)

Quindi, per motivi di nitpicking (che è la parte divertente della formalizzazione), si può dire che la definizione che si critica è davvero sbagliata.

Wikipedia ha una definizione formale della notazione O grande. Cioè:

f(x) = O(g(x))

se e solo se esiste un numero reale positivo M e un numero reale x0 tale che

|f(x)| <= M * |g(x)|  for all x > x0

La notazione Big-Oh viene utilizzata per correlare due funzioni, f e g . Pertanto, ci devono essere due funzioni nella definizione.

Quando scriviamo

f(n)=O(g(n))

noi non definiamo la funzione f (che è già nota) e = non significa "uguale". Puoi leggere la notazione come " f(n) è (in un certo senso) inferiore o uguale a g(n) " oppure, se ti piacciono gli insiemi, come " f(n) appartiene all'insieme O(g(n)) ".

Detto questo:

f(n) = O(f(n))
f(n) = O(n*f(n))

sono entrambi always true.

I am confused on defining the function f(n) using another function

Non essere confuso, in realtà è piuttosto semplice. La notazione O grande è una diseguaglianza. Ciò significa che possiamo trovare più limiti superiori per f (n) e comunque essere corretti, quindi, sebbene possiamo scrivere f (n) = O (f (n)) ed essere corretti è, a seconda di f (n), spesso non quello che intendiamo esprimere.

È una misura dei tassi di crescita. f (n) = 2n non cresce più velocemente di f (n) = n. Entrambe le crescite sono lineari.

f(n) = O(n*f(n))

Immagino tu intenda che il secondo n sia un costante c.

Per definizione di Big O, questa costante è già nella diseguaglianza. Quindi quando scrivi il solito f (n) uguale a Big O (g (n)) stai effettivamente scrivendo abs(f(n)) <= c * abs(g(n)) . Se riesci a trovare un fattore costante, non devi menzionarlo, perché la definizione di Big O, la disequazione, si occupa già di questo e g (n) viene quindi considerato un limite superiore di f (n).

Forse la formulazione comune può aiutarti: f (n) = O (g (n)) significa che la funzione f non cresce più velocemente di g , tranne forse per un fattore costante c .

Vedi la definizione formale di Big oh states f (n) = O (g (n)) significa che ci sono costanti positive c e k tali che 0 < = f (n) < = cg (n) dove n > = k.

Significa che il valore di f (n) per ogni n > = k è minore o uguale al valore di g (n) moltiplicato per qualche costante. Copre entrambi i casi.

Ciò che vogliamo dire con questa definizione è che esiste qualche funzione g (n) che è sempre maggiore o uguale a f (n) per ogni particolare n. Sappiamo quindi che f (n) ha qualche limite particolare che non può attraversare, che è un bisogno essenziale della notazione di Big Oh in quanto ci dice che qualche particolare programma non può richiedere più tempo della sua Notazione Big oh.

Come diceva jpalecek, la notazione f (n) = O (g (n)) è come insiemi il cui significato f (n) appartiene all'insieme O (g (n)). Possono esserci più funzioni che appartengono all'insieme O (g (n)). Ecco perché abbiamo bisogno di due funzioni per l'analisi Big Oh.

f (n) = O (f (n)) è una dichiarazione banale. È fondamentalmente x = x e non ottieni informazioni da f (n) = O (f (n)). L'intero punto della notazione Big-O consiste nel confrontare una funzione complicata con una molto più semplice per ottenere una migliore comprensione del suo comportamento a lungo termine.