Komplexität von Algorithmen und deren Umsetzung

04.10.2019, 22:11	MaPalui	Auf diesen Beitrag antworten »
Komplexität von Algorithmen und deren Umsetzung Hallo liebe Leute ich beschäftige mich im Rahmen meiner Bachelorarbeit mit Primzahltest (wozu sicherlich noch die ein oder andere Frage kommt ). Dazu programmiere ich dann auch die entsprechenden Test in Julia. Meine Frage ist jedenfalls: Wenn ich zwei Algorithmen für das gleiche Problem habe, einer von den beiden liegt in einer "besser" Komplexitätsklasse. Sagen wir, Algorithmus 1 hat die KK $\begin{eqnarray} \mathcal{O} (n) \end{eqnarray}$ und der zweite hat $\begin{eqnarray} \mathcal{O}(\log(n)) \end{eqnarray}$ . Wenn die nun beide korrekt implementiert sind, wird dann der zweite Algorithmus auch immer schneller sein? Ich habe die Komplexitätsklassen noch nicht wirklich verstanden, ich finde es ist sehr "schwammig". Ich beschäftige mich aber noch damit
05.10.2019, 09:32	Huggy	Auf diesen Beitrag antworten »
RE: Komplexität von Algorithmen und deren Umsetzung Mit dieser Thematik bin ich nicht vertraut, aber soviel kann ich sagen: Der zweite Algorithmus wird nicht immer schneller sein. Das wird häufig erst für genügend große $\begin{eqnarray} n \end{eqnarray}$ der Fall sein.
05.10.2019, 10:21	Elvis	Auf diesen Beitrag antworten »
Das ist nicht schwammig sondern sehr konkret. Hier sieht man ein Beispiel mit $\begin{eqnarray} 0,1\cdot n\in O(n) \end{eqnarray}$ und $\begin{eqnarray} 100\cdot log(n)\in O(log(n)) \end{eqnarray}$ für $\begin{eqnarray} n=2 \end{eqnarray}$ bis $\begin{eqnarray} 5000 \end{eqnarray}$ .
05.10.2019, 13:07	Mathe-Novize	Auf diesen Beitrag antworten »
RE: Komplexität von Algorithmen und deren Umsetzung Häufig spricht man bei der Laufzeit von Algortihmen von der Worst-Case-Laufzeit, aber es gibt auch die Best-Case und die Average-Case-Laufzeiten. Vermutlich sind die von dir angegebenen Komplexitätsklassen die für die ungünstigsten Eingabedaten. Es kann also u.U. auch sein, dass der Algorithmus mit der besseren Laufzeit bei einer ungünstigen Verteilung der Eingabedaten im Mittel schlechter läuft, als der andere. Welcher von beiden der absolut beste ist, hängt natürlich stark davon ab, wie vorhersehbar die Struktur deiner Daten ist und ob die Verteilung dieser bekannt ist usw.
12.10.2019, 22:19	MaPalui	Auf diesen Beitrag antworten »
Hallo ihr lieben Jede einzelne Antwort hat mir geholfen. Ich werde mich erstmal tiefer mit dem Thema beschäftigen und dann meine Fragen nochmal stellen, damit ich besser darauf reagieren kann. Ich danke euch sehr

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »