Ich habe gerade gelernt, dass diese Beziehung nicht gilt, weil Protokoll ändert das Verhalten der Funktionen. Aber ist es wahr? Ein Beispiel ist gut.Wenn f (n) = O (g (n)), ist log (f (n)) = 0 (log (g (n))?
Und auch wenn f (n) = Θ (g (n)), wird log (f (n)) = Θ (log (g (n)) halten?
Jede Hilfe sehr geschätzt wird. Vielen Dank im Voraus.
Jetzt, Kommentare haben ergeben, dass diese Frage zu asymptotischen Grenzen eher als algorithmische Komplexität .....
Sie kann die L'Hôpital-Regel verwenden (Information ist in irgendeinem Basistext auf Differentialrechnung) und die Tatsache, dass das Derivat von ln(x) (natürlicher Logarithmus) 1/x ist, um zu zeigen, dass die asymptotische Grenze von f(n)/g(n) gleich der asymptotischen Grenze von log(f(n))/log(g(n)) ist.
Beachten Sie, dass dies jedoch wenig oder nichts mit algorithmischer Komplexität zu tun hat.
Was ist Ihrer Meinung nach die Komplexität der 'log()' Funktion? – Peter
log() reduziert den von f (n) und g (n) zurückgegebenen Wert stark. Also, was ist falsch mit log (f (n)) = O (log (g (n)))? Es sollte auch gelten, denn bei jedem Kostenwert von log (g (n))> log (f (n))! – lU5er
Ich denke, wir sollten klarstellen, sprechen Sie über die Zeit Komplexität zur Berechnung der Funktion (das ist der Kontext, in dem Big O-Notation oft in der Informatik verwendet wird), oder sprechen Sie über das begrenzende Verhalten der Funktion selbst? –