Landau: Aufwandsabschätzung numerischer Algorithmen

Question

Im Folgenden wird die Landau Symbolik zur Aufwandsabschätzung numerischer Algorithmen verwendet. Die betrachteten Algorithmen hängen von der Problemgröße n ab. Beispielsweise ist n die Zahl der  zu  sortierenden  Objekte  in  einer  Liste.  Die  Laufzeit  der  Algorithmen  ist  durch  die  Abbildung f: ℕ → ℝ⁺ mit f(n) = a_n gegeben. Zeige

(a) für f(n) = 2n² + 3n + 4  ist f(n) = O(n²), n → ∞

(b) für f(n) = sin(n²) ist f(n) = O(n), n → ∞

(c) für f(n) = (n²)/(ln(n)) ist f(n) = O(n²), n → ∞

Answer 1

Die Definition der O-Notation lautet ja in etwa so:

Es sei $g: \mathbb{N}\rightarrow \mathbb{R}$. Dann ist

$$\mathcal{O}(g):=\{f:\mathbb{N}\rightarrow \mathbb{R}:\exists \alpha>0 \ \exists n \in \mathbb{N} \ \forall n\geq n_0:0\leq f(n) \leq \alpha \cdot g(n) \}$$

die Menge aller Funktion f, die bis auf eine Konstante $\alpha>0$ höchstens so schnell wächst wie g.

Zu a). Du musst also ein $\alpha>0$ und ein $n_0\in \mathbb{N}$ so angeben, sodass nachweislich für alle $n\geq n_0$ diese Abschätzung gilt: $0\leq f(n) \leq \alpha \cdot g(n)$, konkreter hier: $0\leq 2n^2+3n+4 \leq \alpha \cdot n^2$  (*).

Um jetzt an diese beiden Werte ranzukommen, kannst du das (gerade bei Polynomen) schön sukzessive nachoben abschätzen:

$0\stackrel{n\geq 0}{\leq} 2n^2+3n+4\stackrel{n\geq 4}{\leq}2n^2+3n+n=2n^2+4n=4\Big(\frac{1}{2}n^2+n\Big)\stackrel{n\geq 4}{\leq} 4\Big(\frac{1}{2}n^2+\frac{1}{2}n^2\Big)=4n^2$

 sodass mit einem $\alpha=4>0$ und einem $n_0=4$ die Abschätzung (*) gilt und damit $f\in \mathcal{O}(n^2)$ gilt.

EDIT:

Bei b) und c) könntest du auch zb vollständige Induktion benutzen. Aber da solltest du dir vorher ein ,,passendes" $\alpha>0$ und ein $n_0\in \mathbb{N}$ ausgewählt haben.

Comments

Vielen Dank, das hilft mir schon mal sehr. Ich hätte dazu noch kleine Fragen.

ist hier g(n) = n²  weil f(n) = O(n²)

und ich habe folgendes nicht verstanden

0 ≤ 2n² + 3n + 4 ≤ 2n² +3n + n

wieso schätze ich für die 4 ein n? Könnte n nicht theoretisch eine Zahl sein, die kleiner als 4 ist? Woher weiß ich, dass ich das hier so machen kann?

---

ist hier g(n) = n2  weil f(n) = O(n2)

Ja, wobei es eher unschön ist f(n)=O(n²) zu schreiben. O(n²) ist ja eine MENGE von Funktionen (!), welche alle Funktionen enthält die bs auf eine Konstante >0 höchstens quadratisch wachsen. f ist aber bei dir eine Funktion (Element!). Daher würde ich stattdessen die Schreibweise f(n)∈O(n²) vorziehen, weil es einfach konsistenter ist; indem man nicht aufeinmal zwei Begriffe in einen Topf schmeißt.

0 ≤ 2n2 + 3n + 4 ≤ 2n2 +3n + n

Schau nochmal genau hin, was ich über die ≤ Zeichen geschrieben habe. Ansonsten nutze ich die Transitivitätseigenschaft für die Relation ,,≤" aus.

---

die Bemerkungen über dem ,,≤"  habe ich gesehen. Heißt das einfach "unser n welches wir jetzt betrachten, ist größer oder gleich 4" ?

Also kann ich einfach sagen, dass wir alle n die kleiner als 4 sind, in diesem Fall nicht beachten, wenn wir abschätzen?

---

die Bemerkungen über dem ,,≤"  habe ich gesehen. Heißt das einfach "unser n welches wir jetzt betrachten, ist größer oder gleich 4" ?

Richtig

Also kann ich einfach sagen, dass wir alle n die kleiner als 4 sind, in diesem Fall nicht beachten, wenn wir abschätzen?

Richtig. Aber vorsicht! Du musst dann auch für den späteren Verlauf deiner Abschätzungskette das am größten verwendete n benutzen, weil sonst deine Abschätzungen dazwischen teilweise nicht mehr gehen. Es kann zb wie bei meiner Abschätzung vorkommen, dass n=0 erstmal klappt, aber für spätere vielleicht nicht mehr. Aber im Umkehrschluss klappen dann die vorherigen Abschätzungen auch mit dem größtem n, was verwendet wurde.

---

Vielen Dank,

woher weiß ich generell, wie ich abschätzen muss? Warum ist für b und c zB. Induktion am besten geeignet? 

---

Bei a) hätte man auch Induktion machen können, wenn an denn schon genau weiß, wie $\alpha>0$ und $n_0\in \mathbb{N}$ gewählt sein müssen. Wenn du die nämlich weißt, dann hast du schonmal deine Aussage vereinfache können zu:,, Mit einem $\alpha>0$ gilt für alle $n\geq n_0$: $0\leq f(n)\leq \alpha\cdot g(n)$. Und das schreit doch schon nach Induktion, da hier die Aussage für alle n (ab n_0) gezeigt werden muss.

---

Bei b) reicht es sogar einfach mal nur die Eigenschaft vom Sinus auszunutzen.

---

Hallo entschuldigensie,

ich bearbeite genau dieselbe Aufgabe - deswegen gehe ich davon aus, dass wir beide das gleiche Modul an der selben Uni hören. Du kannst mir ja mal schreiben, falls Du zusammen arbeiten möchtest.

Gruß

wusstestduschon