Laufzeitabschätzung Algorithmen/Landau'sche Symbole

30.12.2005, 20:54	DeCaY	Auf diesen Beitrag antworten »
Laufzeitabschätzung Algorithmen/Landau'sche Symbole Hi erstmal, hab mich grade erst registriert. Die Suchfunktion hat mir ~4 Beiträge geliefert, die meisten waren im Analysisforum. Sry falls der thread hier fehl am Platze ist. So: ich schreibe bald die Klausur "Datenstrukturen & Algorithmen", die dürfte ja dem einen oder anderen bekannt sein. Ein wichtiger Aspekt ist natürlich, die Laufzeiten von Algorithmen mittels O-Notation angeben und auch Funktionen bezüglich ihres asymptotischen Wachstums vergleichen zu können. Und bei letzterem hab ich so meine Probleme. Ich hab nun wirklich viel mit Logarithmen und Exponentialfunktionen.... rumgerechnet, aber wenn z.B. eine Aufgabe kommt (Ottmann, Widmayer - 1.1 (vi) ): $\begin{eqnarray} f(n) =nlog n + \sqrt{n} \end{eqnarray}$ $\begin{eqnarray} g(n) =nlog² n \end{eqnarray}$ oder $\begin{eqnarray} f(n)=3/2^{n} ,g(n)=n^{3}, h(n)=(log n)^{log n}, k(n)=4^{log n} \end{eqnarray}$ (Übungsaufgabe) und ich bestimmen soll, ob f(n) = O(g(n)).... gilt, bin ich immer relativ lange am rechnen. Wie geht man denn da am besten vor? Bei der ersten Aufgabe würde ich z.B. sagen, dass $\begin{eqnarray} f(n) = O(g(n)) \Rightarrow nlogn+\sqrt{n} \leq c1nlog²n+c2 \end{eqnarray}$ , was für $\begin{eqnarray} c2\geq \sqrt{n} \end{eqnarray}$ auf jeden Fall stimmt (da log²n immer größer ist als log n). Richtig soweit? Und bei der zweiten Aufgabe? Vermutlich wächst $\begin{eqnarray} n^{3} \end{eqnarray}$ am langsamsten und $\begin{eqnarray} 3/2^{n} \end{eqnarray}$ am schnellsten. Aber wie vergleiche ich z.B. $\begin{eqnarray} n^{3} \end{eqnarray}$ und $\begin{eqnarray} (log n)^{log n} \end{eqnarray}$ ? Das Problem ist, dass ich z.B. bei den Potenzgesetzen immernoch nicht richtig firm bin, ich muss mir die oft erst an nem Beispiel herleiten. Das suckt natürlich alles.. Deswegen hab ich z.B. als kleine Übung versucht, $\begin{eqnarray} Y = n * log n * log n \end{eqnarray}$ nach n umzuformen. Da komme ich auf kein Ergebnis, bei $\begin{eqnarray} Y = log² n \end{eqnarray}$ wäre es ja $\begin{eqnarray} n = b^{ \sqrt{y}} \end{eqnarray*}$ . Genauso finde ich es schwierig, irgendwelche Summen abzuschätzen, bsp.weise bei der Analyse von Insertion Sort. Wenn ihr mir da vielleicht Tipps geben könntet, z.B. ein Buch, welches diese Thematik erörtert? Ich hab z.B. schon in dem Cormen gelesen und fand den sehr hilfreich wegen des Kompendiums am Schluß. Ich bin echt ein bisschen verunsichert, leider handelt es sich um meinen Drittversuch (wobei ich beim ersten zu stolz war, mich abzumelden, der Meinung, dass ich die Klausur auf jeden Fall im zweiten Versuch bestehe würde.. leider mit 3 Punkten zuwenig durchgefallen ). Deswegen liegt mir viel am Bestehen der Klausur. Thx für's Lesen €: scheiß Formeln.. ;D
30.12.2005, 21:31	Mazze	Auf diesen Beitrag antworten »
Im Normalfall einfach Grenzwerte bilden $\begin{eqnarray} f(n) \in O(g(n)) <=>0 \leq \limsup_{n \to a} \left\| \frac{f(n)}{g(n)} \right\| \leq \infty \end{eqnarray}$ weiteres hier

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »