Wenn n groß wird, werden die beiden Funktionen log * (log n) und log (log * n) schneller sein?Welche der Wachstumsraten log (log * n) und log * (log n) ist schneller?
Hier das Protokoll * Funktion wird der iterierten Logarithmus, hier definiert:
Ich vermute, diese gleich sind, nur anders geschrieben, aber gibt es einen Unterschied zwischen ihnen?
log * n die iterated logarithm, die für große n ist definiert als
log* n = 1 + log*(log n)
Daher log * (log n) = (log * n) - 1, da log * ist die Anzahl der Male Sie müssen log auf den Wert anwenden, bevor er eine feste Konstante erreicht (normalerweise 1). Wenn Sie zuerst ein anderes Protokoll ausführen, wird nur ein Schritt aus dem Prozess entfernt.
Daher wird log (log * n) viel kleiner als log * (log n) = log * n - 1 seit log x < x - 1 für jeden vernünftig großen x.
Hoffe, das hilft!
wow. nette Antwort da! ;) –
Wenn Ihre Sternchen "logstar" aka n log n anzeigen sollen, sollten Sie es auf diese Weise neu schreiben, weil SO sie auf eine Weise analysiert hat, wie ich mir vorstelle, dass Sie nicht beabsichtigt haben – mfrankli
log * ist nicht n log n. – templatetypedef
guten Ruf, keine Ahnung, wo ich das von – mfrankli