Doppelpost! O-Komplexität Datenstrukturen und Algorithmen

28.04.2015, 13:07	anno234	Auf diesen Beitrag antworten »
O-Komplexität Datenstrukturen und Algorithmen Meine Frage: Ich sitze schon seit einiger Zeit an mehreren Komplexitätsberechnungen und weis nicht so recht, wie ich an die folgenden Aufgabe rangehen soll. Kann mir das mal jemand erklären oder vorrechnen, damit ich einen ungefähren Ansatz habe, und kann die anderen Übungen weiter lösen? Meine Ideen: Hier die Aufgabenstellung: Welche der folgenden Beziehungen sind korrekt und welche sind falsch? Beweisen sie jeweils ihre Behauptung! $\begin{eqnarray} n^{5} -\frac{1}{2} n^{3} +1=Theta(n^{5} ) \end{eqnarray}$ LaTeX-Tags eingefügt. Steffen
28.04.2015, 13:24	Elvis	Auf diesen Beitrag antworten »
Meinst du $\begin{eqnarray} O(n^5) \end{eqnarray}$ statt $\begin{eqnarray} \theta(n^5) \end{eqnarray}$ ? Das wäre zweifellos richtig. Zur Notation siehe z.B. hier : http://www.inf.fu-berlin.de/lehre/SS12/A...ration_ALP2.pdf
28.04.2015, 13:38	Captain Kirk	Auf diesen Beitrag antworten »
@Elvis: $\begin{eqnarray} n^{5} -\frac{1}{2} n^{3} +1=\theta(n^{5} ) \end{eqnarray}$ ist auch richtig.
28.04.2015, 13:45	anno234	Auf diesen Beitrag antworten »
Laut Übungsblatt steht dort Theta (das O mit dem Strich durch, finde leider das Zeichen hier nicht). Das die Beziehung richtig ist hab ich mir schon gedacht nur wie ich das auch beweisen soll ist mir nicht ganz klar.
28.04.2015, 13:49	Captain Kirk	Auf diesen Beitrag antworten »
Bei solchen Sachen ist immer die erste Frage: Wie habt ihr $\begin{eqnarray} f \in \theta (g) \end{eqnarray}$ definiert?
28.04.2015, 14:12	anno234	Auf diesen Beitrag antworten »
[attach]37877[/attach]
Anzeige

28.04.2015, 14:15	Captain Kirk	Auf diesen Beitrag antworten »
ja, du sollst also $\begin{eqnarray} k_1,k_2 \end{eqnarray}$ finden mit $\begin{eqnarray} k_1 n^5 \leq n^5-1/2 n^3 +1 \leq k_2 n^5 \end{eqnarray}$ für genügend große n. Fang mit der linken Ungleichung an.
28.04.2015, 15:21	Captain Kirk	Auf diesen Beitrag antworten »
Doppelpost: onlinemathe.de/forum/O-Komplexitaet-Datenstrukturen-und-Algorithmen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »