Algorithmen und Berechnungshomplexität
Präsenzblatt O
Aufgabe 07
.
loga (nlogb(a)) logp (a) loga(n) logp(a)
= =
.
(09 =
logb(n)
6
an bn-m
=
Anlog(a) (flog(a) ,
=
n
= (alog(b) , n
= anlog(b) anlog(b)
=
log(a 64) =
log (ab)") =
wlog(ab) (log(a) log(b)
= +
Aufgabe 02 .
=0
Für zwei Funktionen f g : IN-IR ,
gilt fzg genau
dann , wenn
0(f)0(g) :
↳ zlogllog(n) Glog(n) Logogn
* an
= 2023 .
(n + sin(n) [Inlog(n)) [ n Enz En Eh
!
, dass !- OC22)
Umzuzeigen , n , muss man
zeigen ,
dass das Wachstum der Fakultätn !
asymptotich langsamer wächst als I .
7 atIR und J notI , sodass An zno gilt : n ! 1a .
ga
Induktions an fang
Fürn 1 =
n ! = 11a .
2 = a
.
2 = a
.
4 ,
wähle a
=
1
Induktionsannahme
Esgelte dieBehauptung für ein beliebesen
Induktionsschritt
+7
2n
n > n+ 1
+ zz .
. ist also (n + 1) ! [a 2 -
(n+ 1) ! =
(n +1) n ! (n + 1) -
a
-
22
IA
Präsenzblatt O
Aufgabe 07
.
loga (nlogb(a)) logp (a) loga(n) logp(a)
= =
.
(09 =
logb(n)
6
an bn-m
=
Anlog(a) (flog(a) ,
=
n
= (alog(b) , n
= anlog(b) anlog(b)
=
log(a 64) =
log (ab)") =
wlog(ab) (log(a) log(b)
= +
Aufgabe 02 .
=0
Für zwei Funktionen f g : IN-IR ,
gilt fzg genau
dann , wenn
0(f)0(g) :
↳ zlogllog(n) Glog(n) Logogn
* an
= 2023 .
(n + sin(n) [Inlog(n)) [ n Enz En Eh
!
, dass !- OC22)
Umzuzeigen , n , muss man
zeigen ,
dass das Wachstum der Fakultätn !
asymptotich langsamer wächst als I .
7 atIR und J notI , sodass An zno gilt : n ! 1a .
ga
Induktions an fang
Fürn 1 =
n ! = 11a .
2 = a
.
2 = a
.
4 ,
wähle a
=
1
Induktionsannahme
Esgelte dieBehauptung für ein beliebesen
Induktionsschritt
+7
2n
n > n+ 1
+ zz .
. ist also (n + 1) ! [a 2 -
(n+ 1) ! =
(n +1) n ! (n + 1) -
a
-
22
IA
