Big-Oh, conseguenza di una definizione

Question

Ho speso un sacco di tempo a leggere domande e risposte su Big-Oh sia qui e math.stackexchange e sembra che questo è il posto migliore per come math.stackexchange non sembrano come le domande di questo tipo. Così mi è stato dato un po 'di corsi presso UNI sul mio corso CS e non capiscono fino in fondo e speravo che voi ragazzi potrebbe aiutare. Capisco che le domande "compiti a casa" sono un po 'visto di buon occhio qui così ho scelto un altro esempio che è non parte del mio corsi, ma di stile simile.

Così qui è la definizione che mi è stato dato nelle note:

E la domanda che mi è stata data è:

Uso Definizione 2.5 mostra che se f (n) è O (g (n)) allora k + f (n) è O (g (n)).

Ho trascorso 3 giorni la ricerca sul Web per qualsiasi tipo di risposta a problemi come questi. Guardando Definizione 2.5 si dice f (n) è O (g (n)) e k + f (n) è O (g (n)). Questo è sufficiente per me, ma sembra devo dimostrare come ciò è derivata. Ho pensato in un primo momento che dovrebbe essere fatto in qualche modo per induzione, ma da allora ha deciso contro quello e ci deve essere un modo più semplice.

Qualsiasi aiuto sarebbe apprezzato. Non mi aspetto di qualcuno che appena eretta darmi la risposta. Vorrei più preferirei sia una metodologia o un riferimento al punto in cui posso imparare la tecnica di fare questo. Potrei Vi ricordo ancora una volta che questo è non il mio corsi effettivo, ma una questione di stile simile.

Grazie in anticipo.

Answer 1

Supponiamo che f (n) è O (g (n))
allora esiste un c e k' S.T. per ogni n> k ': f (n) <= cg (n)
Consideriamo ora f (n) + k
Sia D s.t k <= d * g (n) per ogni n maggiore di k '
che si sa è possibile perché k è in O (1)
poi
f (n) + k <= cg (n) + dg (n) = (d + c) (g (n))
Quindi si utilizza la definizione sostituto d + c per c, ==> f + k è in O (g)

Answer 2

f (n) <= cg (n)

k + f (n) <= c'g (n) dove c'= ck

così k + f (n) è O (g (n))

Answer 3

Poi k è O(1), f(n) è un O(g(n)) poi si può sommare questi valori, allora avete O(1+g(n)) questo è O(g(n));

f(n) è O(g(n)) allora k + f(n) è anche O(g(n)), perché avete writed nella rubrica

  

Ignora aggiunta di una costante

Constant sono sempre ignorato perché non può cambiare Big-O di notazione, ogni costante è O(1) in notazione Big-O.

Answer 4

Per quel che vale, questa è una definizione un po 'artificiosa di notazione O-grande. Il più generale e, a mio parere, definizione più intuitiva è che f(n) ~ O(g(n)) come n->a IFF lim|f(n)/g(n)| <= A come n->a per qualche reale finito A numero.

La parte importante è che è necessario un contesto limite. In CS, tale limite è preso implicitamente di essere infinito (dal momento che questo è ciò che tende a n al crescere della dimensione problema), ma in linea di principio può essere qualsiasi cosa. Ad esempio, come sin(x) ~ O(x) x->0 (in realtà, è esattamente asintotica x, questo è il piccolo angolo di approssimazione)

.