[algorithm] Ist log (n!) = Θ (n · log (n))?



3 Answers

Ich weiß, dass dies eine sehr alte Frage mit einer akzeptierten Antwort ist, aber keine dieser Antworten verwendet tatsächlich die durch den Hinweis vorgeschlagene Vorgehensweise.

Es ist ein ziemlich einfaches Argument:

n! (= 1 * 2 * 3 * ... * n) ist ein Produkt von n Zahlen, die jeweils kleiner oder gleich n . Daher ist es kleiner als das Produkt von n Zahlen, die alle gleich n ; dh n^n .

Die Hälfte der Zahlen - also n/2 von ihnen - in der n! Produkt sind größer oder gleich n/2 . Daher ist ihr Produkt größer als das Produkt von n/2 Zahlen, alle gleich n/2 ; dh (n/2)^(n/2) .

Loggen Sie sich durch, um das Ergebnis zu ermitteln.

Question

Ich soll zeigen, dass log ( n !) = Θ ( n · log ( n )) .

Ein Hinweis wurde gegeben, dass ich die obere Schranke mit n n zeigen und die untere Schranke mit ( n / 2) ( n / 2) zeigen sollte . Das scheint mir nicht so intuitiv zu sein. Warum sollte das so sein? Ich kann definitiv sehen, wie man nn zu n · log ( n ) umwandelt (dh beide Seiten einer Gleichung protokolliert), aber das funktioniert irgendwie rückwärts.

Was wäre der richtige Ansatz, um dieses Problem anzugehen? Soll ich den Rekursionsbaum zeichnen? Da ist nichts rekursiv, so dass das nicht als wahrscheinlicher Ansatz erscheint.




Hilft dir weiter, wo Mick Sharpe dich verlassen hat:

Die Ableitung ist ziemlich einfach: siehe http://en.wikipedia.org/wiki/Logarithm -> Gruppentheorie

log (n!) = log (n * (n-1) * (n-2) * ... * 2 * 1) = log (n) + log (n-1) + ... + log (2 ) + log (1)

Denken Sie an n als unendlich groß . Was ist unendlich minus eins? oder minus zwei? etc.

log (inf) + log (inf) + log (inf) + ... = inf * log (inf)

Und dann denke an inf als n.




Für untere Grenze,

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
       >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
       = n/2 lg n - 1/2

lg (n!)> = (1/2) (n lg n - 1)

Beide Grenzen kombinieren:

1/2 (n lg n - 1) <= lg (n!) <= N lg n

Wenn wir die untere Grenze als größer als (1/2) wählen, können wir innerhalb der Klammer -1 kompensieren.

Also lg (n!) = Theta (n lg n)




Dies könnte helfen:

eln(x) = x

und

(lm)n = lm*n



Related