Bestimme die asymptotische Komplexität

Question

Wenn mir zwei Funktionen gegeben werden und ich gebeten werde, die asymptotische Komplexität für beide zu finden, was bedeutet das? Ist es O() oder Big Theta? Zum Beispiel f1(n)=a^n und f2(n)=n^3+n^2

Sollte ich sagen, dass f1 O(a^n) ist und f2 O(n^3) ist oder sollte ich Big-Theta verwenden?

Answer 1

O-Notation liefert eine asymptotische obere Schranke; wenn f(n) = O(g(n)) ist, bedeutet es intuitiv, dass f nicht schneller wächst als g.

Θ-Notation hingegen spezifiziert eine enge Grenze. Wenn f(n) = Θ(g(n)) bedeutet es, dass f und g mit der gleichen Rate wachsen, bis zu einem bestimmten konstanten Faktor. Technisch gesehen impliziert f(n) = Θ(n), dass f(n) = O(g(n)), obwohl die Umkehrung nicht immer wahr ist.

Die präziseste Analyse, die man machen kann, wäre die Verwendung der Θ-Notation, obwohl es nicht falsch wäre, die O-Notation zu verwenden.

Hoffentlich hilft das!

Answer 2

Big Oh und Big Theta werden beide in der asymptotischen Analyse verwendet. Zu sagen, dass eine Funktion f(n) = O(n^3) bedeutet, dass sie nicht schneller wächst als n^3. Zu sagen, dass eine Funktion f(n) = (n^3) bedeutet, dass sie genauso schnell wächst wie n^3.