ich steh total auf der Leitung und hoffe, daß mich da jemand mal runterschubsen kann:
Ich weis, was ein Exponent ist und auch, was ein Logarithmus ist und obendrein sogar, wie man von einem auf’s andere kommt (auch, wenn wir in der Schule nur von Tabellen abgelesen haben).
Lineare Steigerung ist klar (x -> y), exponentielle Steigerung auch (x -> x²).
Aber ich komm partout nicht drauf, was denn nun eine „logarithmische Steigerung“ bedeutet, bzw. wie sie definiert wird.
Mit Google hab ich nur millionen Varianten gefunden, was ein Logarithmus ist und wie man den errechnet…
Ich denke ich bin nicht der einzige, der nicht ganz sicher ist, was eine logarithmische Steigung sein soll, da du das etwas unglücklich formuliert hast!
Aber hier sind ein paar wichtige Funktionen und zu denen kann ich was sagen:
f(x)=x Gerade, die Steigung ist konstant f’(x)=1
f(x)=x^2 Parabel, die Steigung nimmt konstant zu f’(x)=2x
f(x)=e^x e-Funktion, Steigung f’(x)=e^x
f(x)=1/x Hyperbel, Steigung f’(x)=-1/x^2
f(x)=ln(x) Logarithmusfunktion, Steigung f’(x)=1/x
Ich denke ich bin nicht der einzige, der nicht ganz sicher
ist, was eine logarithmische Steigung sein soll, da du das
etwas unglücklich formuliert hast!
hmm - na dann eben nochmal etwas ausführlicher: es geht um Algorithmen und ihre Analyse, insbesondere um die O-Notation. Laut meinem Skript werden „mit der O-Notation Laufzeitfunktionen in gewisse Klassen ‚eingeordnet‘“ und dadrunter steht dann eine Tabelle
O(1) konstant
O(log n) logarithmisch *
O(n) linear
O(n log n) *
O(n log² n) *
…
O(n²) quadratisch
O(n^k), k>=2 polynominell
…
O(2^n) exponentiell
Die drei mit * markierten Laufzeitfunktionen machen mir dabei den größten Streß, was unter Umständen auch damit zusammenhängen kann, daß das Skript nicht das Gelbe vom Ei ist - z.B. wird im Text nicht nur bei O(log n) von einer logarithmischen Steigung gesprochen, sondern auch bei O(n log n), und dann behauptet, daß eine logarithmische Steigung immer kleiner wäre, als eine lineare (was ja Blödsinn ist, wenn man O(n log n) ebenfalls als logarithmische Steigung bezeichnet).
Und nun sind wir wieder bei meiner Frage: wie wird „logarithmische Steigung“ definiert? Alles, was größer als konstant ist, aber kleiner als linear? Alles, was ‚die richtige Form hat‘ (also zunächst stark ansteigend, dann immer flacher)?
hmm - na dann eben nochmal etwas ausführlicher: es geht um
Algorithmen und ihre Analyse, insbesondere um die O-Notation.
Also theoretische Informatik.
Laut meinem Skript werden „mit der O-Notation
Laufzeitfunktionen in gewisse Klassen ‚eingeordnet‘“ und
dadrunter steht dann eine Tabelle
O(1) konstant
O(log n) logarithmisch *
O(n) linear
O(n log n) *
O(n log² n) *
…
O(n²) quadratisch
O(n^k), k>=2 polynominell
…
O(2^n) exponentiell
Damit ist der zeitliche Aufwand zur Bearbeitung eines Algorithmus gemeint. Mit Funktionen wie f(x)=… hat das also nicht viel zu tun. Und das logarithmisch ist ein Mittelding zwischen linear und exponentiell. Trifft man z.B. in der Kryptographie an.
HTH
mfg M.L. (kein Komm. zum Rest unten)
Die drei mit * markierten Laufzeitfunktionen machen mir dabei
den größten Streß, was unter Umständen auch damit
zusammenhängen kann, daß das Skript nicht das Gelbe vom Ei ist
z.B. wird im Text nicht nur bei O(log n) von einer
logarithmischen Steigung gesprochen, sondern auch bei O(n log
n), und dann behauptet, daß eine logarithmische Steigung immer
kleiner wäre, als eine lineare (was ja Blödsinn ist, wenn man
O(n log n) ebenfalls als logarithmische Steigung bezeichnet).
Und nun sind wir wieder bei meiner Frage: wie wird
„logarithmische Steigung“ definiert? Alles, was größer als
konstant ist, aber kleiner als linear? Alles, was ‚die
richtige Form hat‘ (also zunächst stark ansteigend, dann immer
flacher)?
hmm - na dann eben nochmal etwas ausführlicher: es geht um
Algorithmen und ihre Analyse, insbesondere um die O-Notation.
Laut meinem Skript werden „mit der O-Notation
Laufzeitfunktionen in gewisse Klassen ‚eingeordnet‘“ und
dadrunter steht dann eine Tabelle
O(1) konstant
O(log n) logarithmisch *
O(n) linear
O(n log n) *
O(n log² n) *
…
O(n²) quadratisch
O(n^k), k>=2 polynominell
…
O(2^n) exponentiell
Man beachte, dass es sich um Mengen von Funktionen handelt.
f(n)∈O(g(n)) bedeutet: Es gibt ein c>0, so dass f(n)/g(n) f(n) ∈ O(n) => f(n) ∈ O(n log n)
Jede Konstante Funktion ist also z.B. auch Element von O(2^n)
Übrigens, möchte man genau die Funktionen z.B. mit logarithmischen Wachstum berücksichtigen, so lautet die Notation Θ(g(n)).
f(n)∈Θ(g(n)) bedeutet: Es gibt ein c>0, so dass f(n)/g(n)=c für n gegen unendlich.
Das ist oft eine ganz nützliche Größe, weil dabei die Veränderung einer Variablen auf deren Wert bezogen wird, z. B. bei den Börsenkursen, Kursveränderung „± x%“.
Trägt man die y-Achse logarithmisch auf, dann sieht man am Diagramm gleich die log. Abl. Wenn sich die Größe dann immer um den gleichen „Prozentwert“ ändert, dann gibt es im log.-Diagramm eine Gerade (bei linearer Teilung eine Exonentialfunktion).
