[Wachstum v. Fkt.] Komplexitätsklassen |
14.02.2016, 16:02 | loci | Auf diesen Beitrag antworten » |
[Wachstum v. Fkt.] Komplexitätsklassen ich wiederhole gerade eine alte Aufgabe aus der Übung. Mir ist dabei allerdings etwas nicht klar. Es soll eine möglichst einfache Funktion g(n) gesucht werden mit: Zuerst schauen wir uns an. Klar, dass 2^n am schnellsten wächst. Wir schmeißen also das n² einfach weg und betrachten nur noch 2^n. Nun vergleichen wir dies (lt. Lösung der Übung) mit Dies kann man ja auch schreiben als 2*n log (n). Beim Vergleich wird gesagt, dass 2*n log (n) genau so schnell wächst wie 2^n. Schaue ich mir die Graphen aber in Wolfram Alpha an, sehe ich, dass 2^n doch schneller wächst. Wie kommt man daher darauf, dass es gleich schnell wächst? Das verstehe ich nicht. |
||
14.02.2016, 19:48 | loci | Auf diesen Beitrag antworten » |
Kann geschlossen werden - ich habe es so ungünstig aufgeschrieben dass ich nicht gesehen habe, welche beiden Werte er miteinander verglichen hat. Die Kernaussage war nämlich, dass n² + 2^n genauso schnell wächst wie 2^n, und dann macht das ganze mehr Sinn! |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|