Big-Theta funktioniert auch mit Laufzeit in log (n!) Und log (n) + log (n^2)

Question

log (n!) = Log (n * n (-1) * ... .1) = log (n) + log (n-1) + .... + log (1). So ist es in O (n * logn). Aber ist es auch in groß-Omega (n * logn)? Ich glaube nicht, aber mein automatischer Interviewtest hat es mir so gedacht!

Protokoll (n) + Protokoll (n^2) = Protokoll (n) + 2 * Protokoll (n) = 3 * Protokoll (n). Also, es ist in, Big-O, Big-Omega und Big-Theta (Log (n)). Aber aus irgendeinem Grund dachte mein automatischer Interviewtest anders.

Ist mein Verständnis korrekt oder ist der automatisierte Test korrekt?

S.S .: Ich hasse automatische Interviewtests!

Answer 1

log (n) + log (n^2) = log (n) + 2 * log (n) = 3 * log (n). Also, es ist in, Big-O, Big-Omega und Big-Theta (log (n)). Aber aus irgendeinem Grund mein automatischer Interview-Test dachte anders.

IMO, sind Sie richtig, und der automatische Interview Test nicht (wenn Sie die Frage richtig dargestellt).

log (n!) = Log (n n (-1) .... 1) = log (n) + log (n-1) + .... + log (1) . So ist es in O (n logn). Aber ist es auch in großen Omega (n logn)? Ich denke nicht, aber mein automatischer Interviewtest dachte so!

Der automatische Interviewtest ist korrekt, und Sie sind es nicht. log (n!) = log (n) + log (n-1) + .... + log (1)> = log (n) + ... + log (n/2) = (n/2) log (n/2)> = (n/2) log (sqrt (n)) = n * log (n)/4 (alle "> =" sind für ausreichend große n)

Answer 2

Über log n! und big-Omega:

n! multipliziert die Zahlen von 1 bis n. Die zweite Hälfte dieser Zahlen sind alle ≥ n/2 ≥ sqrt (n), also log n! ≥ (n/2) * log (sqrt (n))) = n/2 * log (n)/2 = (n log n)/4. Diese untere Grenze ist schrecklich schlecht, aber gut genug, um dieses Protokoll leicht zu zeigen n! = großes Omega (n log n).