Algorithmen und Datenstrukturen: Thema komplexität

Question

Geben Sie bei jeder der untenstehenden Fragen an, ob die Aussage über die asymptotische Komplexität der angegebenen Funktion richtig ist oder nicht. Begründen Sie Ihre Antwort jeweils.

1) 7n log unten kommt 2  n = O(n)

2) n^3+2^n = O(2^n)

3) 3((n mod 3)+1) = O(1)

4) n^2+15n–3 = O(n^3)

Ich habe kein Plan wie das geht

Answer 1

Hey,

die O-Notation auch Landau Notation ist quasi eine Obere Schranke. D.h. wenn ich einen Algorithmus habe, der 3n^3 + n^2 Schritte benötigt, dann reicht es vereinfacht gesagt, sich die dominantesten Term anzusehen, also der Term, der die Funktion am meisten Beeinflusst, in diesem Fall wäre das z.B. 3n^3 man schreibt dann auch O(n^3) da 3n^3 in O(n) liegt.

O(n) ist also eine Abschätzung nach oben.

Im Bezug auf deine Aufgaben also:

1.) O(n)

2.) O(2^n)

3.) O(1) (alles nur Konstanten)

4.) O(n^2) (Hinweis: Nicht zuweit nach oben Abschätzen)

Hinweis zu 4.) Wenn ich sage mein Algorithmus läuft in O(2^n) dann ist das auf jedenfall eine Abschätzung, das Problem ist hierbei, dass wenn mein Algorithmus aber in Wirklichkeit in O(n) läuft ich meine Abschätzung viel zu grob gemacht habe. Das ist wie beim Kochen es geht hier die Balance zwischen Gewürzen und Bekömmlichkeit zu finden.

Vllt hilft dir das auch etwas:

https://www.mathelounge.de/715566/rechenregeln-fur-die-landau-symbole-beweisen?show=715659#a715659

Comments

Dankeschön :)