Lösungen T4 und T5 online (nt)

[MatthiasBein]

.

[thomas_kalbe]

wir haben die Lösungen nochmal leicht verbessert und erneut hochgeladen.

- t

[banshee]

Ich hätte da mal eine Frage zur Lösung der 1b auf dem 4. Übungsblatt. Wieso kann man denn diese Umformung so einfach machen:

\(O(q_u^2 + q_v^2 + q_u^2q_v) < O(q_u^2 + q_v^2 + q_uq_v^2) <=> q_u^2 + q_v^2 + q_u^2q_v < q_u^2 + q_v^2 + q_uq_v^2\)

Denn mal angenommen, ich setze \(q_v = 2q_u\), dann gilt:

\(O(q_u^2 + q_v^2 + q_u^2q_v) = O(q_u^2 + q_v^2) + O(q_u^2q_v)
= O(q_u^2 + q_v^2) + O(2q_u^2q_v)
= O(q_u^2 + q_v^2) + O(4q_u^2q_u)
= O(q_u^2 + q_v^2) + O(q_uq_v^2)
= O(q_u^2 + q_v^2 + q_uq_v^2)\)

womit die Umformung nicht stimmt.

[MatthiasBein]

Wieso kann man denn diese Umformung so einfach machen:
\(O(q_u^2 + q_v^2 + q_u^2q_v) < O(q_u^2 + q_v^2 + q_uq_v^2) <=> q_u^2 + q_v^2 + q_u^2q_v < q_u^2 + q_v^2 + q_uq_v^2\)

Da sind uns einfach formale Fehler unterlaufen. Natürlich ist die wechselseitige Beziehung nicht richtig, wie folgendes Beispiel verdeutlicht:
Sei \(f(x) = 4x\) und
\(g(x) = 7x\), dann gilt
\(f(x) < g(x)\) für \(x > 0\).
Allerdings, wie jedem bekannt sein sollte, gilt auch
\(\mathcal{O}(f(x)) = \mathcal{O}(g(x)) = \mathcal{O}(x)\).

Zumal kann der Beweis nicht in der O-Notation erfolgen, da asymptotisch gesehen, beide Varianten kubische Komplexität besitzen.
Wenn \(q_u \rightarrow \infty\) und \(q_v \rightarrow \infty\), dann gilt
\(\mathcal{O}(q_u^2 q_v) = \mathcal{O}(q_u^3) = \mathcal{O}(q_v^3) = \mathcal{O}(q_u q_v^2)\),
wodurch auch dein zweiter Einwand richtig ist.

Denn mal angenommen, ich setze \(q_v = 2q_u\), dann gilt:
\(O(q_u^2 + q_v^2 + q_u^2q_v) = O(q_u^2 + q_v^2) + O(q_u^2q_v)
= O(q_u^2 + q_v^2) + O(2q_u^2q_v)
= O(q_u^2 + q_v^2) + O(4q_u^2q_u)
= O(q_u^2 + q_v^2) + O(q_uq_v^2)
= O(q_u^2 + q_v^2 + q_uq_v^2)\)

Allerdings war es auch nicht verlangt das asymptotische Verhalten zu analysieren, sondern es galt zu zeigen, dass eine Variante weniger aufwendig ist, sprich weniger Operationen benötigt. Da man mit der O-Notation den Beweis nicht führen kann, ist der Hinweis über die Komplexität in der Aufgabenstellung wohl irreführend. Wir bitten dies zu entschuldigen und werden es für zukünftige Semester ausbessern.

Um möglichst allgemein zu bleiben, definieren wir hier eine Operation als ein gewichtetes Mittel im \(\mathbb{R}^d\). Nun wissen wir, dass eine Casteljau-Auswertung mit Grad \(q\) genau \(\frac{q(q+1)}{2}\) Operationen benötigt. Damit können wir beide Varianten vergleichen:
\(\begin{align*}
\text{Auswertung zuerst mit festem } u &< \text{Auswertung zuerst mit festem } v ~~\Leftrightarrow \\
(q_v+1)\frac{q_u(q_u+1)}{2} + \frac{q_v(q_v+1)}{2} &< (q_u+1)\frac{q_v(q_v+1)}{2} + \frac{q_u(q_u+1)}{2} ~~\Leftrightarrow \\
(q_v+1)q_u(q_u+1)+q_v(q_v+1) &< (q_u+1)q_v(q_v+1)+q_u(q_u+1) ~~\Leftrightarrow \\
q_v q_u(q_u+1) &< q_u q_v(q_v+1) ~~\Leftrightarrow \\
q_u+1 &< q_v+1 ~~\Leftrightarrow \\
q_u &< q_v ~~~~\text{q.e.d.}
\end {align*}\)