Zusammenfassung Algorithmen und Berechnungskomplexität1-Präsenzzettel0-Algo1

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