2 Wachstumsverhalten von Funktionenernst/Lehre/AD/Folien/...Beispiel: Best-Case-Laufzeit von Insertion-Sort:Ω(n), damit ist die Laufzeit von Insertion-SortΩ(n). 2. Laufzeit von Insertion-Sort

Algorithmen und Datenstrukturen 40

2 Wachstumsverhalten von Funktionen

Beim Vergleich der Worst-Case-Laufzeiten von Algorithmen in Abhängig-keit von der Größe n der Eingabedaten ist oft nur deren Verhalten für großeWerte von n von Interesse, also deren asymptotisches Verhalten.

In diesem Kapitel werden Begriffe und Notation zur Beschreibung die-ses asymptotischen Verhaltens eingeführt sowie einige Hilfsmittel für dieasymptotische Analyse vorgestellt.

2 Wachstumsverhalten von Funktionen TU Bergakademie Freiberg, WS 2005/06


2.1 Asymptotische Notation

Wir betrachten Funktionen f, g, . . . deren Definitionsbereich die natürlichenZahlen (N oder N0) sind mit Werten in R (R+).

2.1.1 Die Θ-Notation

Für eine gegebene Funktion g = g(n) ist Θ(g(n)) definiert als die Mengevon Funktionen

Θ(g(n)) :={f(n) : es existieren positive Konstanten c1, c2 sowie n0,

sodass 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) ∀n ≥ n0}

Somit bezeichnet Θ(g(n)) alle Funktionen, deren asymptotisches Wachs-tumsverhalten bis auf multiplikative Konstanten gleich ist.

2.1 Asymptotische Notation TU Bergakademie Freiberg, WS 2005/06


Bemerkungen 2.11. Obgleich Θ(g(n)) eine Menge ist, wird Enthaltensein von f in Θ(g(n))

nicht durch f ∈ Θ(g(n)) sondern durch f = Θ(g(n)) ausgedrückt.Diese Abweichung von der üblichen Notation hat gewisse Vorteile.

2. Gemäß unserer Definition sind alle Funktionen in Θ(g(n)) asympto-tisch nichtnegativ, d.h. f(n) ≥ 0 für alle hinreichend große n. Fernermuss g selbst asymptotisch nichtnegativ sein, da ansonsten die Men-ge leer wäre. Wir gehen daher bei unseren Betrachtungen stets vonasymptotisch nichtnegativen Funktionen aus.

3. Für jedes Polynom p von exaktem Grad d ∈ N0 gilt p(n) = Θ(nd). Fürjede Konstante c ≥ 0 gilt c = Θ(n0) = Θ(1).



Beispiel: Im vorigen Kapitel hatten wir informell die Θ-Notation so ein-geführt, dass Terme niedriger Ordnung sowie multiplikative Konstanteneinfach ignoriert werden. Wir überprüfen dieses Vorgehen und weisenanhand der Definition nach, dass 12n

2 − 3n = Θ(n2).

Gesucht: c1, c2, n0 sodass

c1n2 ≤ 12n

2 − 3n ≤ c2n2 ∀n ≥ n0.

Division durch n2 (n ≥ 1) führt auf

c1 ≤12− 3

n≤ c2 ∀n ≥ n0,

was z.B. für c1 = 1/14, c2 = 1/2 und n0 = 7 erfüllt ist. (Die genaue Wahl istuninteressant, wesentlich ist nur die Existenz solcher Konstanten.)

Übung: 6n3 6= Θ(n2)



2.1.2 Die O-Notation

Die O-Notationa ist für den Fall, dass lediglich obere asymptotische Schran-ken vorliegen.

Für eine gegebene Funktion g = g(n) ist O(g(n)) definiert als die Funktio-nenmenge

O(g(n)) :={f(n) : ∃ Konstanten c, n0 sodass

0 ≤ f(n) ≤ cg(n) ∀n ≥ n0}

Klar: mengentheoretisch gilt Θ(g(n)) ⊂ O(g(n)), d.h. f = Θ(g(n)) impliziertf = O(g(n)).

agesprochen”groß O von“ bzw. nur

”O von“



Bemerkungen 2.21. O(g(n)) enthält auch alle Funktionen mit niedrigerer Wachstumsord-

nung als g. So liegt neben g1(n) = an2 + bn + c auch die Funktiong2(n) = an + b in O(n2).

2. In der (vor allem älteren) Literatur wird die O-Notation oft anstelle derΘ-Notation verwendet, hier soll O aber ausschließlich asymptotischeobere Schranken beschreiben.

3. Wort-Case-Laufzeit von O(g(n)) impliziert Laufzeit in O(g(n)) für allemöglichen Eingaben. Worst-Case-Laufzeit von Θ(g(n)) heißt dagegennicht notwendig Laufzeit von Θ(g(n)) für alle möglichen Eingaben. (Ge-genbeispiel: Insertion-Sort, mit einer Worst-Case-Laufzeit von Θ(n2),aber einer Laufzeit von Θ(n) für bereits sortierte Eingabe.)



Beispiele:

2n2 = O(n3) mit c = 1 und n0 = 2.

Weitere Funktionen in O(n2):

n2

n2 + n

n2 + 1000n

1000n2 + 1000n

n

n/1000

n1.9999

n2/ log log log n



2.1.3 Die Ω-Notation

Analog der asymptotischen oberen Schranke bei der O-Notation bezeich-net die Ω-Notation eine asymptotische untere Schranke:

Ω(g(n)) :={f(n) : ∃ Konstanten c, n0 sodass

0 ≤ cg(n) ≤ f(n) ∀n ≥ n0}

Gemäß der bisherigen Definitionen folgt sofort

Satz 2.3 Für zwei Funktionen f und g gilt f(n) = Θ(g(n)) genau dann,wenn sowohl f(n) = O(g(n)) als auch f(n) = Ω(g(n)).



Bemerkungen 2.41. Da die Ω-Notation eine untere asymptotische Schranke angibt, setzen

wir sie zur Beschreibung der Best-Case-Laufzeit von Algorithmen ein.Eine Ω-Schranke für die Laufzeit im günstigsten Fall liefert eine ent-sprechende Laufzeit für alle möglichen Eingaben.Beispiel: Best-Case-Laufzeit von Insertion-Sort: Ω(n), damit ist dieLaufzeit von Insertion-Sort Ω(n).

2. Laufzeit von Insertion-Sort somit zwischen Ω(n) und O(n2). DieseSchranken sind asymptotisch bestmöglich.

3. Man kann jedoch sagen: die Worst-Case-Laufzeit von Insertion-Sort istΩ(n2), da für gewisse Eingaben die Laufzeit Ω(n2) ist.

4. Sprechweise”Laufzeit eines Algorithmus ist Ω(g(n))“ bedeutet: egal

welche Eingabe der Länge n, die Laufzeit ist mindestens Konstante·g(n) für n hinreichend groß.



Beispiele:√

n = Ω(log2 n) mit c = 1 und n0 = 16.

Weitere Funktionen in Ω(n2):

n2

n2 + n

n2 − nn2 + 1000n

1000n2 + 1000n

1000n2 − 1000nn3

n2.0001

n2 log log log n

22n



2.1.4 Asymptotische Notation in Gleichungen und Ungleichungen

• Auf der rechten Seite einer (Un-)Gleichung: O(n2) steht für eine belie-bige Funktion f ∈ O(n2).Beispiel: 2n2 +3n+1 = 2n2 +Θ(n) bedeutet 2n2 +3n+1 = 2n2 + f(n)mit f(n) ∈ Θ(n) (etwa f(n) = 3n + 1).

• Auf der linken Seite einer (Un-)Gleichung: Egal wie die anonyme Funk-tion auf der linken Seite gewählt wird, es gibt stets eine Wahl einerFunktion auf der rechten Seite, damit die (UN-)Gleichung wahr ist.

Beispiel: 2n2 + Θ(n) = Θ(n2) bedeutet, dass für alle Funktionen f ∈Θ(n) eine Funktion g(n) ∈ Θ(n2) existiert mit 2n2 + f(n) = g(n).



Verkettung:2n2 + 3n + 1 = 2n2 + Θ(n) = Θ(n2)

Interpretation:

• Erste Gleichung: es existiert f(n) ∈ Θ(n) sodass 2n2 + 3n + 1 =2n2 + f(n).

• Zweite Gleichung: für jede Funktion g(n) ∈ Θ(n) (beispielsweise für dieFunktion f(n) für welche die erste Gleichung gültig ist) existiert eineFunktion h(n) ∈ Θ(n2) sodass 2n2 + g(n) = h(n).



2.1.5 Die o-Notation

Asymptotische obere Schranken ausgedrückt in O-Notation sind nicht not-wendig asymptotisch scharf. Dies ist etwa für 2n2 = O(n2) der Fall, nichtaber für 2n = O(n2).

Die o-Notation beschreibt obere Schranken, die nicht asymptotisch scharfsind. Wir definieren o(g(n)) (

”klein O von g von n“) als die Menge

o(g(n)) :={f(n) : ∀ Konstanten c > 0,∃n0 > 0 sodass

0 ≤ f(n) < cg(n) ∀n ≥ n0}

Beispiel: 2n = o(n2), aber 2n2 6= o(n2).

Intuitiv: für n hinreichend groß wird f(n) beliebig kleiner als g(n), oder

limn→∞

f(n)g(n)

= 0.



Beispiele:

n1.9999 = o(n2)

n2/ log n = o(n2)

n2 6= o(n2)n2/1000 6= o(n2)



2.1.6 Die ω-Notation

Beschreibt nicht asymptotisch scharfe untere Schranken:

ω(g(n)) :={f(n) : ∀ Konstanten c > 0,∃n0 > 0 sodass

0 ≤ cg(n) < f(n) ∀n ≥ n0}

So gilt etwa n2/2 = ω(n), nicht aber n2/2 6= ω(n2).

Die Beziehung f(n) = ω(g(n)) impliziert

limn→∞

f(n)g(n)

= ∞,

d.h. f(n) wird, sofern n hinreichend groß, beliebig größer als g(n).

Beispiele: n2.0001 = ω(n2), n2 log n = ω(n2), n2 6= ω(n2).



2.1.7 Vergleich von Funktionen

Viele Relationen zwischen reellen Zahlen gelten auch für asymptotischeVergleiche.

Zunächst kann man folgende Analogien/Entsprechungen ausmachen:

O ≈ ≤Ω ≈ ≥Θ ≈ =o ≈ <ω ≈ > .

Sprechweisen:

f(n)”asymptotisch kleiner“ als g(n) falls f(n) = o(g(n))

f(n)”asymptotisch größer“ als g(n) falls f(n) = ω(g(n)).



Relationseigenschaften:

Transitivit ät

f(n) = Θ(g(n)) und g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)),analog für O,Ω, o, ω.

Reflexivit ät

f(n) = Θ(f(n)),

analog für O,Ω.

Symmetrie

f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n)).Transponierte Symmetrie

f(n) = O(g(n)) ⇔ g(n) = Ω(f(n)),f(n) = o(g(n)) ⇔ g(n) = ω(f(n)).



Was nicht gilt: Trichotomie, d.h. für zwei reelle Zahlen a, b gilt stets einesvon a < b, a = b oder a > b.

Nicht alle Funktionen sind asymptotisch vergleichbar.

Beispiel: Die Funktionen f(n) = n und g(n) = n1+sin n sind nicht asympto-tisch vergleichbar, da der Wert des Exponenten 1 + sinn zwischen 0 und 2oszilliert und alle dazwischenliegenden Werte annimmt.



2.2 Bezeichnungen und Wissenswertes

Monotonie

• f ist monoton wachsend falls m ≤ n ⇒ f(m) ≤ f(n).

• f ist monoton fallend falls m ≤ n ⇒ f(m) ≥ f(n).

• f ist streng monoton wachsend falls m < n ⇒ f(m) < f(n).

• f ist streng monoton fallend falls m < n ⇒ f(m) > f(n).

2.2 Bezeichnungen und Wissenswertes TU Bergakademie Freiberg, WS 2005/06


2.2.1 Floor- und Ceiling-Funktionen

Für x ∈ R definieren wir die (monoton wachsenden) Funktionen

bxc := max{z ∈ Z : z ≤ x}, dxe := min{z ∈ Z : z ≥ x}.

• Für alle x ∈ R gilt x− 1 < bxc ≤ x ≤ dxe < x + 1.

• Für alle z ∈ Z gilt bz/2c+ dz/2e = z.

• Für alle reellen x ≥ 0 und p, q ∈ Z gelten

ddx/pe/qe = dx/(pq)e,bbx/pc/qc = bx/(pq)c,

dp/qe ≤ (p + (q − 1))/q,bp/qc ≥ (p− (q − 1))/q.



2.2.2 Restklassenarithmetik

Für z ∈ Z und n ∈ N wird die Zahl z mod n definiert als Divisionsrest desQuotienten z/n, d.h.

z mod n = z − bz/ncn.

Man sagt, zwei ganze Zahlen z1, z2 seien kongruent modulo n (für einn ∈ N) falls diese bei Division durch n denselben Rest liefern. Wir schreiben

z1 ≡ z2 mod n falls z1 mod n = z2 mod n

Äquivalent: z1 ≡ z2 mod n genau dann, wenn n die Zahl z2 − z1 teilt.

Wir schreiben z1 6≡ z2 mod n falls z1, z2 nicht kongruent modulo n.



2.2.3 Polynome

Ein Polynom vom Grad d (d ∈ N0) ist ein Ausdruck der Form

p(n) =d∑

j=0

ajnj .

Die Konstanten {aj}dj=0 heißen Koeffizienten des Polynoms. Das Polynomp ist von exaktem Grad d, falls ad 6= 0 und ist in diesem Fall asymptotischpositiv genau dann, wenn ad > 0.

Für ein asymptotisch positives Polynom p von exaktem Grad d gilt p(n) =Θ(nd). Für jede reelle Zahl a ≥ 0 ist die Funktion na monoton wachsend,für jede reelle Zahl a ≤ 0 ist na monoton fallend.

Wir nennen eine Funktion f polynomiell beschränkt, falls f(n) = O(nk) füreine Konstante k.



2.2.4 Exponentialfunktionen

Für alle n ∈ N0 und a ≥ 1 ist an eine monoton wachsende Funktion von n.Wir vereinbaren 00 := 1.

Die Wachstumsraten von Polynomen und Exponentialfunktionen werdendurch folgende Tatsache in Beziehung gesetzt: für alle reelle Konstantena, b mit a > 1 gilt

limn→∞

nb

an= 0, d.h. nb = o(an). (2.1)

Jede Exponentialfunktion zu einer Basis a > 1 wächst somit schneller alsjedes Polynom.



Die Exponentialfunktion ex besitzt die (auf ganz R konvergente) Potenzrei-he

ex =∞∑

k=0

xk

k!= 1 + x +

x2

2+

x3

3!+ . . . .

Für alle x ∈ R gilt ex ≥ 1 + x mit Gleichheit genau für x = 0. Ferner gilt

1 + x ≤ ex ≤ 1 + x + x2 für alle |x| < 1.

Für x → 0 ist die Approximation von ex durch 1 + x recht gut, es gilt

ex = 1 + x + Θ(x2),

wobei mit Θ(x2) hier die Asymptotik im Grenzwert x → 0 gemeint ist.Schließlich gilt für alle x ∈ R

ex = limn→∞

(1 +

x

n

)n.



2.2.5 Logarithmen

Für alle reellen positiven Zahlen a, b, c und n ∈ N gelten

a = blogb a,

logc(ab) = logc a + logc b,

logb an = n logb a,

logb a =logc alogc b

,

logb1a

= − logb a,

logb a =1

loga b,

alogb c = clogb a.

(In allen Gleichungen seien alle Basen 6= 1.)



• logb n = loga n/ loga b, d.h. bei asymptotischen Betrachtungen (n →∞)spielt Basis des Logarithmus keine Rolle.

• Informatik: Basis 2 von besonderer Bedeutung, da viele Algorithmenund Datenstrukturen auf Zerlegung von Problemen in zwei gleich großeTeilprobleme beruhen.

Potenzreihe:

log(1 + x) = x− x2

2+

x3

3!− x

4

4!+− . . . , |x| < 1.

Ferner gilt für x > −1x

1 + x≤ log(1 + x) ≤ x

mit Gleichheit nur für x = 0.



Wir nennen eine Funktion f polylogarithmisch beschränkt, fallsa f(n) =O(logk n) für eine Konstante k.

Der Vergleich zwischen den Wachstumsverhalten von Polynomen undPolylogarithmen ist gegeben durch (ersetze n durch log n in (2.1))

0 = limn→∞

logk n(ea)log n

= limn→∞

logk nna

und somit logk n = o(na)

für jede positive Konstante a.

Somit wächst jede polylogarithmische Funktion langsamer als jedes positi-ve Polynom.

aSchreibweise: logk n := (log n)k



2.2.6 Fakult äten

Die Funktion n! (”n Fakultät“) ist definiert als

n! =

{1 falls n = 0,

n · (n− 1)!, falls n > 0.

M.a.W. : n! = 1 · 2 · 3 · . . . · n.

Eine offensichtliche obere Schranke für n! ist n! ≤ nn.

Eine asymptotisch exakte Schranke liefert die Stirlingsche Approximation

n! =√

2πn(n

e

)n (1 + Θ

(1n

)).

Ferner gelten die asymptotischen Aussagen

n! = o(nn), n! = ω(2n), log(n!) = Θ(n log n).



Schließlich gilt für alle n ≥ 1

n! =√

2πn(n

e

)neαn mit

112n + 1

< αn <1

12n.



2.2.7 Iteration von Funktionen

Mit f (i)(n) bezeichnen die i-malige Anwendung der Funktion f auf dasArgument n:

f (i)(n) =

{n falls i = 0,

f(f (i−1)(n)) falls i > 0.

Beispiel: für f(n) = 2n erhalten wir f (i)(n) = 2in.



2.2.8 Der iterierte Logarithmus

Mit log∗ n (”log Stern von n“) bezeichnen wir den iterierten Logarithmus,

der wie folgt definiert ist:

Sei log(i) n wie oben definiert mit f(n) = log n. Da Logarithmen nur fürpositive Argumente definiert sind, setzen wir

log∗ n := min{i ≥ 0 : log(i) n ≤ 1}.

Beispiele: log∗2 2 = 1,

log∗2 4 = 2,

log∗2 16 = 3,

log∗2 65536 = 4,

log∗2(265536) = 5.



An diesen Beispielen erkennt man, dass der iterierte Logarithmus extremlangsam anwächst.

Da die Anzahl der Atome im beobachtbaren Universum auf etwa 280

geschätzt wird, eine Zahl die wesentlich kleiner ist als 265536, sind Ein-gabegrößen n mit log∗ n > 5 eher selten zu erwarten.



2.2.9 Fibonacci-Zahlen

Die Fibonacci-Zahlen sind definiert durch die Rekursion

Fi =

0 i = 0,

1 i = 1,

Fi−1 + Fi−2, (i ≥ 2).

Ab i = 2 ist also jede Fibonacci-Zahl die Summe ihrer beiden Vorgänger,wir erhalten die Folge

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . .



Fibonacci-Zahlen sind verwandt mit dem goldenen Schnitt φ und dessennegativen Kehrwert φ̂ gegeben durch

φ =1 +

√5

2≈ 1.61803 . . . ,

φ̂ =1−

√5

2≈ −0.61803 . . . .

Genauer:

Fi =φi − φ̂i√

5.

Wegen |φ̂| < 1 folgt |φ̂i|/√

5 < 1/√

5 < 1/2. Somit ist Fi gegeben durchφi/

√5 gerundet zur nächsten ganzen Zahl. Insbesondere wachsen die

Fibonacci-Zahlen exponentiell.


Wachstumsverhalten von FunktionenAsymptotische NotationDie -NotationDie O-NotationDie -NotationAsymptotische Notation in Gleichungen und UngleichungenDie o-NotationDie -NotationVergleich von Funktionen

Bezeichnungen und WissenswertesFloor- und Ceiling-FunktionenRestklassenarithmetikPolynomeExponentialfunktionenLogarithmenFakultätenIteration von FunktionenDer iterierte LogarithmusFibonacci-Zahlen

Documents

2 Wachstumsverhalten von Funktionenernst/Lehre/AD/Folien/...Beispiel: Best-Case-Laufzeit von Insertion-Sort:Ω(n), damit ist die Laufzeit von Insertion-SortΩ(n). 2. Laufzeit von Insertion-Sort