Algorithmen und
Berechnungshomplexitat Übungsblatt
I
Aufgabe 1 .
O
G2G wächst höchstens schnell
:
so
f G wächst langsamer als
O :
ifIG wachst mindestens schnell so wie
W :
GG wachst schneller als
Dif g = wächst
gleich schnell wie wo
fx g wächst nicht vergleichbar
, S(n) ist stückweise definiert :
180 für ungerade Chonstant
n
scn) =
[ n
für geraden (linear (
Dadurch hat s(n) keine einheitliche Wachstumsrate :
Für wächst s(n) schneller
gerade n
als
log(n) und
log(log (n) I
ist s(n) honstant und int
Für
ungerade n
somit kleiner als log(n) und log (log (n)
für hinreichend großes n
der Parität
Da scn)
abhängig von n
(gerade und ungerade) unterschiedliche
Wachstumsraten zeigt ,
gibt es keine einheitliche
Wachstumsregel die s(n) mit log (n) oder
,
log(log(n) in eine klare asymptotische
Beziehung setzt .
Berechnungshomplexitat Übungsblatt
I
Aufgabe 1 .
O
G2G wächst höchstens schnell
:
so
f G wächst langsamer als
O :
ifIG wachst mindestens schnell so wie
W :
GG wachst schneller als
Dif g = wächst
gleich schnell wie wo
fx g wächst nicht vergleichbar
, S(n) ist stückweise definiert :
180 für ungerade Chonstant
n
scn) =
[ n
für geraden (linear (
Dadurch hat s(n) keine einheitliche Wachstumsrate :
Für wächst s(n) schneller
gerade n
als
log(n) und
log(log (n) I
ist s(n) honstant und int
Für
ungerade n
somit kleiner als log(n) und log (log (n)
für hinreichend großes n
der Parität
Da scn)
abhängig von n
(gerade und ungerade) unterschiedliche
Wachstumsraten zeigt ,
gibt es keine einheitliche
Wachstumsregel die s(n) mit log (n) oder
,
log(log(n) in eine klare asymptotische
Beziehung setzt .
