Das kommt vom Schreiben eines Programms, finde den Median von zwei sortierten Arrays mit der Größe m bzw. n , mit der zeitlichen Komplexität von O(log(m + n)) .
Ich kann eine Lösung von O(log(m) + log(n)) ausarbeiten. Erfüllt es die obige Zeitanforderung?
Ich denke, es ist positiv, weil:
log(m) + log(n) = log(m*n) <= log((m+n)^2) = 2*log(m+n) = O(log(m+n))
Anders ausgedrückt, existieren k = 2 und m0 = n0 = 1 . Für m > m0 and n > n0 gibt es log(m*n) <= k*log(m + n) .
Gibt es einen Fehler, oder habe ich Recht?
Allgemeiner, können wir bei gegebener Konstante a log(n^a) = O(log(n)) mit derselben Argumentation sagen?
Danke an Davids Antwort. Dies wird auch von Big-O Notation auf Wikipedia erwähnt:
"We may ignore any powers of n inside of the logarithms. The set O(log n) is exactly the same as O(log(n^c))."
Ja, Sie haben in allen Punkten Recht. Log wächst langsam genug, dass die asymptotische Klasse nicht sehr empfindlich auf die Funktion im Inneren reagiert.