Summe der O-Notation

Question

Mögliche Duplizieren:
Big O when adding together different routines

Was O(n) + O(log(n)) zu nicht reduziert? Meine Vermutung ist O(n), aber kann keine strengen Überlegungen geben.

Ich verstehe O(n) + O(1) sollte auf O(n) reduzieren, da O(1) nur eine Konstante ist.

Answer 1

Nun, da O(f(n)) + O(g(n)) = O (f(n) + g(n)) Wir versuchen einfach, eine f(n) so dass f(n) > n + log(n)

Da als n ausreichend log(n) < n berechnen wächst können wir sagen, dass f(n) > 2n > n + log(n)

Deshalb O(f(n)) = O(2n) = O(n)

In einem allgemeineren Sinn, O(f(n)) + O(g(n)) = O(f(n)) wenn c*f(n)>g(n) für einige Konstante c. Warum? Denn in diesem Fall wird f(n) unseren Algorithmus "dominieren" und seine zeitliche Komplexität diktieren.

Answer 2

die Antwort ist O (n). O (log n) ist kleiner als O (n). so addiert ihre Addition den maximalen Wert, der O (n) ist.

Answer 3

Reihenfolge wird immer auf Terme höherer Ordnung reduziert. Ich kann dir intuitives Denken geben. Angenommen, Sie haben O(n + n^2). Welcher Teil würde dann in der Laufzeit eine wichtigere Rolle spielen? n oder n^2. Offensichtlich n^2. Denn wo n^2 ist, wirst du den Effekt von n nicht bemerken, wenn n erhöht oder verringert wird.

Als Beispiel

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. 

Ich glaube, Sie verstehen jetzt,,