Asymptotische Komplexität (nicht-absteigend)

Aufrufe: 202     Aktiv: 12.05.2021 um 07:36

0

Aufgabe:

enter image description here

Problem:

Hallu! :3

Mag mir hier jemand behilflich sein bzw. ein Retter in der Not sein? Und zwar ist mein Problem folgendes: Wie kann ich hier am Schnellsten das ganze Sortieren (nicht absteigend) oder erkennen welches zum Beispiel schneller wächst?

Ich könnte zwar das ganze mittels GeoGebra grafisch darstellen lassen, ist mir aber persönlich zu aufwändig, darum wollte ich Fragen, ob es hier eventuell einen Trick gibt?

Diese Frage melden
gefragt

Punkte: 44

 

Kommentar schreiben

1 Antwort
1

Hallo userbeda0b, jea Analysis! ;-) Wenn Du die Funktionen anschaust, sollte Dir auffallen, dass 6 Funktionstypen vertreten sind. 1) Fakultät, 2) Exponentialfunktionen, 3) Potenzfunktionen, 4)lineare Funktionen, 5)Logarithmusfunktionen und 6) Konstanten. Alle diese Funktionen haben unterschiedliche Anstiege wenn es Richtung unendlich geht. Von groß nach klein sind das 1) bis 6). Die Fakultät steigt am schnellsten an, die Konstante gar nicht. Jetzt gruppierst Du die Funktionen und legst die Reihenfolge innerhalb der Gruppe fest. log(n^2) steigt einfach schneller als log(n). Jetzt noch auf Spezialfälle achten. a hoch n für a < 1 ist streng monoton fallend mit Grenzwert 0. Wenn Du bei zwei Funktionen einer Gruppe nicht sicher bist musst Du halt doch GeoGebra oder einfach den Taschenrechner bemühen. Ich habe jetzt nicht alle nachgerechnet, aber nach erster Sichtung taucht außer u) keine Falle auf. Gruß jobe

Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 275
 

Oh nooo, Analysis... 🤮

Jobe, ich Danke Dir vielmals (again). Sehr schöne und ausführliche Beschreibung, so dass es sogar ich, die hohlste Nuss, das jetzt endlich versteht. Und mein Tag ist wieder gerettet. (/ω\)

  ─   userbeda0b 08.05.2021 um 15:43

1

Hey, Nachtrag: wenn bei der Expo Funktion die Basis groß wird überholt sie die Fakultät. Insbesondere n hoch n geht ab wie Schmitz' Katze. Bei i) und r) aufpassen. Gruß jobe

  ─   jobe 09.05.2021 um 10:50

Diesen Tipp konnte ich gerade echt gut gebrauchen, hab' mich nämlich gerade gefragt, warum das jetzt so ist. 😂

Danköööö!!! (^o^)

  ─   userbeda0b 10.05.2021 um 09:36

Hallo jobe!

Möchtest Du eventuell meine Lösung kontrollieren falls Du Lust und Laune hast? 😅

Also ich habe es vorerst mal aufsteigend sortiert:

2^64 - 1 > 1000x > n^100 > n! > 4^n > n^3 log(n) > n^n > n^3 > n2^n > n^2 log(n) > 2^n > (3/2)^n > n log(n) > 2^log(n) > log(n^2) > log(n) > (1/2)^n > 0.0001n^2

  ─   userbeda0b 10.05.2021 um 22:30

1

Hallo Userbeda0b, ich check das mal heute Abend. Jetzt muss ich erst noch "Brötchen verdienen". Kannst Du mir bitte erläutern wie Du sortiert hast? Ich bin kein Informatiker und kann mit „Asymptotische Komplexität“ nicht wirklich was anfangen. Ich habe lediglich die angegebenen Funktionen mathematisch, analytisch für große n betrachtet. Unter diesem Gesichtspunkt komme ich definitiv auf eine andere Reihenfolge. Was muss man als Informatiker hier noch zusätzlich berücksichtigen? Gruß jobe.

  ─   jobe 11.05.2021 um 08:12

Ich sollte auch mal irgendwann meine "Brötchen verdienen" gehen, aber das kann bei mir noch dauern....😂

Also ich habe folgendes gemacht:

1.) ich habe eine kleine Tabelle gemacht, wo ich die ganzen Funktionen nach ihren Typen sortiert habe, Fakultät, Logarithmus, etc.

2.) Innerhalb dieser Tabelle habe ich die ganzen Funktionstypen sortiert von starker Steigung bis schwache Steigung.

3.) Nachher war ich gezwungen doch GeoGebra zu verwenden...Da habe ich dann immer zwei Funktionstypen hergenommen (z.B. alle Fakultät- und Logarithmusfunktionen) und diese jeweils miteinander verglichen.


Eigentlich ziemlich kompliziert, man kann es sicherlich einfacher irgendwie miteinander vergleichen, daher stimmt bei mir die Lösung wahrscheinlich nicht. (Nicht vergessen, ich habe das ganze vorerst ABSTEIGEND sortiert)

P.S. Man braucht kein Informatiker zu sein für diese Aufgabe, wie Du siehst, ich bin eine Informatikerin und habe dennoch keine Ahnung wie das ganze hier funktioniert... 😂



  ─   userbeda0b 11.05.2021 um 15:27

1

Hallo Userbeda0b, ausgehend von folgendem Artikel: hoffentlich funktioniert der Link.

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwjvnZbxicLwAhUE7aQKHRdqBOUQFjAAegQIAxAD&url=http%3A%2F%2Fwww.informatik.uni-bremen.de%2Fagbs%2Flehre%2Fss05%2Fpi2%2Fhintergrund%2Fkomplexitaet.pdf&usg=AOvVaw23XNPkVtZKiF0eKIghy3qJ

und den dort zu findenden Tabellen habe ich die Funktionen mal mit n=10.000 durchgerechnet (rechnen lassen). Ausgehend davon, dass bei einem großen n sich die Sekantensteigung der Tangentensteigung annähert glaube ich dass die Steigung am Punkt n hinreichend genau erkennbar ist. Für fast alle Funktionen kann man sich die Steigungsfunktion auch durch Ableiten berechnen und dann n= 10.000 einsetzen. Bei Fakultät wird’s allerdings ätzend. Mit diesen Zahlenwerten komme ich auf folgende AUFSTEIGENDE Reihenfolge: u), weil negativ, n), f), q), g), d), h), k), e), l), c), s), b), j), o), a), m), i), p), t), r). Im groben (mit Ausreißern) ergibt sich das erwartete Bild Fakultät zweiter, Expo vor Konstanz (Überraschung) vor Potenz vor Linear vor Logarithmus. Bei noch größerem n wird sich die Konstanz verschieben. Sie kann ja nicht steigen. So, ich hoffe ich habe keine Ablese- oder Abschreibfehler gemacht. Diskutiert werden kann noch über die Konstanten. Mathematisch haben sie ja keine Steigung- hm! Mathematisch sollte es passen. Ob’s auch in die Theorie der Informatik passt kann ich nicht endgültig sagen. Ich hoffe trotzdem es hilft Dir. Gruß jobe.

  ─   jobe 11.05.2021 um 19:42

Oh je, also da ist bei mir wohl etwas schief gelaufen bei meiner Lösung... 😂

Jobe, ich Danke Dir wirklich vielmals für Deine GROßE UND MEGA Unterstützung und dass Du Dir sogar nochmals die Zeit genommen hast,
Dir die Aufgabe anzuschauen. Als Dankeschön dafür gibt es ewige Dankbarkeit! (︶^︶)

  ─   userbeda0b 11.05.2021 um 23:01

1

Gerne, nada problema, jobe

  ─   jobe 12.05.2021 um 07:36

Kommentar schreiben