Qual è la notazione Big-$ O $ di una somma di un registro?

Question

per: $$ \ Sum \ {n + m} _ {i= n} \ log (i) $$ Mi chiedo cosa sia la grande o notazione e come dimostrarlo ... Credo che possiamo anche scrivere questo come $$ \ log (n) + \ log (n + 1) + \ log (n + 2) + \ ldots + \ log (n + m) $$

Anche $$ \ Log (N + M)! / \ log (n-1)! $$

Grazie

Answer 1

Ricorda che la somma di $ \ log $ 's è equivalente alla $ \ log $ di prodotti.

cioè:

$$ \ log (xy)=log x + \ log y $$

Così possiamo cambiare la tua funzione:

$$ \ Begin {allinea} \ sum_ {i= n} ^ {n + m} ^ {n + m} \ log i &=log \ PROD_ {I= N} ^ {N + M} I \\ &=log (n \ cdot (n + 1) \ cdot (n + 2) \ cdot \ ldots \ cdot (M-1) \ cdot m) \\ &=log (m! \ / \ (n-1)!) \\ \ end {allinea} $$

Quindi possiamo usare in modo simile la regola di divisione per renderli indietro:

$$ \ log (m! \ / \ (n-1)!)=log (m!) - \ log ((n-1)!) $$

Allora usando approssimazione di Stirling possiamo immediatamente vedere:

$$ \ log (m!) - \ log ((n-1)!)= o (m \ log m) $$

Potresti essere in grado di fare meglio anche con i limiti più precisi per ottenere:

$$ \ Begin {allinea} \ log (m!) - \ log ((n-1)!) & \ leqm em ^ {m + \ frac {1} {2}} e ^ {- m} - \ sqrt {2 \ pi} (n -1) ^ {n- \ frac {1} {2}} e ^ {1-N} \\ &=VDOT \ end {allinea} $$

Answer 2

O ((M +1) log (N + M)).È ovviamente un limite superiore.Ma anche la maggior parte dei valori ha un logaritmo vicino al massimo, quindi è anche un buon limite inferiore.

Nel tuo caso particolarmente semplice, la formula Stirling ti darà un risultato migliore, ma hai chiesto solo Big-O.