Somma di o-grande

Question

Eventuali duplicati:
Big O when adding together different routines

Cosa significa O(n) + O(log(n)) ridurre al? La mia ipotesi è O(n) ma non posso dare un ragionamento rigoroso.

Capisco O(n) + O(1) dovrebbe ridurre a O(n) dal O(1) è solo una costante.

Answer 1

Beh visto O(f(n)) + O(g(n)) = O (f(n) + g(n)) Stiamo semplicemente cercando di calcolare un f(n) tale che f(n) > n + log(n)

Poiché, come n cresce sufficientemente log(n) < n possiamo dire che f(n) > 2n > n + log(n)

Pertanto O(f(n)) = O(2n) = O(n)

In senso più generale, O(f(n)) + O(g(n)) = O(f(n)) se c*f(n)>g(n) per alcuni costante c. Perché? Perché in questo caso f(n) "domineranno" il nostro algoritmo e ne impongono la complessità temporale.

Answer 2

la risposta è O (n). O (log n) è minore di O (n). quindi la loro somma somma il valore massimo che è O (n).

Answer 3

L'ordine è sempre ridotto a condizioni di ordine superiore. Posso darti un ragionamento intuitivo. Supponiamo di avere O(n + n^2). Quindi quale parte avrebbe avuto un ruolo più importante in fase di esecuzione? n o n^2. Ovviamente n^2. Perché là dove n^2 non noterai l'effetto di n quando n è aumentato o diminuito.

Come esempio,

let n = 100, then n^2 = 10000 
means n is 0.99% and n^2 is 99.01% of total running time. 
What would you consider for runtime? 
if n is increased then this difference is clearer. 

Credo di capire ora,