Zusammenfassung Algorithmen und Berechnungskomplexität1-Übungszettel2-Algo1

Algorithmen und Berechnungshomplexität I


Übungsblatt 2


Aufgabe 27 ,




Wir möchten das:
zeigen ,


log (n ! ) O(nlog(n)) =




Demnach Ja 6 ERt und InoEIN , ,
sodass Un >no
gilt :




a
nlog(n) log (n ! ) <b
nlog(n)
.
.




Obere Schranke
Die Fakultät von n ist definiert als :




n! =
n
·


(n 1) (n-2) .....
-
·




Wendet den
diese Funktion an erhält
man
Logarithmus auf man :
,




log (n !) =

log (n (n 1) (n -2)
· - ·

..... 1)
Dies kann umformen zu loglab) log(a) log(b)
man = +




log(n ! ) log(n) log(n 1) log(n 2) og(t) + + +... +
-
-
=




=
0

, Das kann man auch so darstellen :




log(n ! )
= N logh s

Schaut man sich jeden einzelnen Term
der Summe
log(k) an , so
gilt :




log(k) log (n) ,
FheE1 ,
2
, , ..., n3
3

Das bedeutet , das jeder Loganth mus
log(k) für k In maximal log(n) beträgt .




Und somit gilt :


N ~



log(h) log(n) =

1
n.
log(n)
h =
1 h =
1


Da logans ein honstanter Wert ist ,

kann den Term
man
log (n) aus

der Summe herausziehen ,