1 Grundlagen - uni-wuerzburg.de...Praktische Informatik I - Algorithmen und Datenstrukturen Wintersemester 2006/07 3. Behauptung Die while–Schleife terminiert, d.h. die zu iterierende

Praktische Informatik I - Algorithmen und Datenstrukturen Wintersemester 2006/07

1 Grundlagen

1.1 Algorithmen und ihre formalen Eigenschaften,Datenstrukturen

Ein Algorithmusist ein mit formalen Mitteln beschreibbares, mechanisch

nachvollziehbares Verfahren zur Lösung einer Klasse von Problemen.

Er kann in Form einesProgrammsvon einem Computer bearbeitet werden.

Korrektheit von Algorithmen (E. Dijkstra)Man kann durchTestenzwar die Anwesenheit, nicht aber die

Abwesenheit von Fehlern zeigen.

Formale Korrektheitsbeweisewerden häufig mit Hilfe von Schleifen-

und Prozedurinvarianten geführt.

Prof. Dr. Dietmar Seipel 1


Effizienz von AlgorithmenDie wichtigsten Maße für die Effizienz sind der zur Ausführung des

Algorithmus benötigteSpeicherplatzund die benötigteRechenzeit.

• experimentelle Messung mit Hilfe von repräsentativ gewählten

Eingaben,

• formale Abschätzung der Kosten im besten Fall (best case), im

schlechtesten Fall (worst case) und im Mittel (average case). Die

Analyse des Verhaltens im Mittel ist häufig mathematisch schwierig

durchzuführen.

DatenstrukturAufbau von (komplexen) Wertebereichen aus elementaren

Wertebereichen mit Hilfe von Konstruktoren.



1.2 Polynomprodukt

Ein ganzzahliges Polynomvom GradN − 1 ist gegeben durchNganzzahlige Koeffizientena0, . . . , aN−1 ∈ Z:

p(x) = a0 + a1 · x2 + a2 · x

2 + . . . + aN−1 · xN−1

Beispiel

p(x) = 4 + 2 · x − x3 ⇒ a0 = 4, a1 = 2, a2 = 0, a3 = −1, N = 4

Seiq(x) = b0 + b1 · x1 + · · · + bN−1 · x

N−1 ein weiteres Polynom vomGradeN .

FrageWie kann man das Produkt der Polynomer(x) = p(x) · q(x) (effizient)berechnen?



Beispiel

q(x) = 2 − x + x2 (b3 = 0)

⇒ r(x) = p(x) · q(x)

=(4 + 2 · x − x3

)·(2 − x + x2

)

= 8 + (−4 + 4) · x + (4 − 2) · x2 + (−2 + 2) · x3 + x4 − x5

= 8 + 2 · x2 + x4 − x5

• distributives Ausmultiplizieren

• Aufsammeln der Terme mit gleichen Exponenten



Implementierung

In Java deklariert man Polynome als Arrays.

Deklaration in Javaint p[N], q[N], r[2 * N - 1];

doppelt geschachtelte for–Schleifefor (int i = 0; i <= N - 1; i++)

for (int j = 0; j <= N - 1; j++)

r[i + j] = r[i + j] + p[i] * q[j];

Es werdenN2 Koeffizientenprodukteberechnet.



1.2.1 Divide–and–Conquer–Verfahren

Verfahren zur Lösung eines Problems der LängeN .

1. DivideTeile das Problem der GrößeN in (wenigstens) zwei annähernd gleich

große Teilprobleme wennN > 1 ist, sonst löse das Problem der Größe

1 direkt.

2. ConquerLöse die Teilprobleme auf dieselbe Art (rekursiv).

3. MergeFüge die Teillösungen zur Gesamtlösung zusammen.



Wir nehmen nun an, dassN eine Zweierpotenz ist:N = 2k, k ∈ N .

p(x) = pl(x) + xN

2 · pr(x)

mit pl(x) = a0 + a1 · x1 + . . . + aN

2−1 · x

N

2−1,

pr(x) = aN

2+ aN

2+1 · x

1 + . . . + aN−1 · xN

2−1

Ebenso kann man schreiben

q(x) = ql(x) + xN

2 · qr(x)

mit geeigneten Polynomenql(x) undqr(x) vom GradN2 − 1.

Dann ist

r(x) = p(x) · q(x)

= pl(x) · ql(x) + ( pl(x) · qr(x) + pr(x) · ql(x) ) · xN

2

+ pr(x) · qr(x) · xN



Beispiel

N = 4 = 22 ⇒N

2= 2

p(x) = 4 + 2 · x1 − x3

q(x) = 2 − x1 + x2

p(x) = 4 + 2 · x1

︸︷︷︸

pl(x)

+x2 · (0 − 1 · x1)︸︷︷︸

pr(x)

q(x) = 2 − 1 · x1

︸︷︷︸

ql(x)

+x2 · (1 + 0 · x1)︸︷︷︸

qr(x)

⇒ r(x) = 8 − 2 · x2 +(4 + 2 · x + 0 − 2 · x + 1 · x2

)· x2

+ (0 − 1 · x + 0) · x4

= 8 + 2 · x2 + x4 − x5



Berechnung von 4 Produkten von Polynomen vom GradN2 − 1.

M(N) = Anzahl der Multiplikationen von Koeffizienten, die aus-

geführt werden, wenn man zwei Polynome vom Grad

N − 1 mit N Koeffizienten miteinander multipliziert.

Rekursionsformel

M(N) = 4 · M

(N

2

)

,

M(1) = 1

für N = 2k, k ∈ N0

M(N) = M(2k

)= 4 · M

(2k−1

)= 42 · M

(2k−2

)= . . .

= 4k · M(20

)

︸︷︷︸

=1

= 4k =(22

)k= 22k =

(2k

)2= N2



1.2.2 Divide–and–Conquer–Verfahren (nach KARATSUBA)

Man kann aber mit weniger Koeffizientenmultiplikationen auskommen:

zl(x) = pl(x) · ql(x)

zr(x) = pr(x) · qr(x)

zm(x) = ( pl(x) + pr(x) ) · ( ql(x) + qr(x) )

Dann ist:

r(x) = p(x) · q(x)

= zl(x) + ( zm(x) − zl(x) − zr(x) ) · xN

2 + zr(x) · xN



Divide–and–Conquer–Verfahren (nach KARATSUBA)

zur Multiplikation zweier Polynomep(x) undq(x) vom GradN − 1.

1. DivideFallsN = 1 ist, so berechne das Produkt der beiden Koeffizienten

direkt, sonst: Zerlege die Polynomep(x) undq(x):

p(x) = pl(x) + pr(x) · xN

2 ,

q(x) = ql(x) + qr(x) · xN

2

und setze:

pm(x) = pl(x) + pr(x),

qm(x) = ql(x) + qr(x).



2. ConquerWende das Verfahren (rekursiv) an, um die folgenden

Polynomprodukte zu berechnen:

zl(x) = pl(x) · ql(x),

zr(x) = pr(x) · qr(x),

zm(x) = pm(x) · qm(x).

3. MergeSetze:

p(x) · q(x) = zl(x) + ( zm(x) − zl(x) − zr(x) ) · xN

2 + zr(x) · xN .



Rekursionsformel

M(N) = 3 · M

(N

2

)

,

M(1) = 1.

für N = 2k, k ∈ N0 :

M(N) = M(2k

)= 3 · M

(2k−1

)= . . . = 3k · M

(20

)

= 3k =(2log 3

)k=

(2k

)log 3= N log 3 = N1,58...

(log x = Logarithmus zur Basis 2 vonx)

Verbesserung gegenüber dem naiven Verfahren mitN2 Multiplikationen.



1.3 Ein Multiplikationsverfahren

Multiplikation von zwei Dualzahlen.

Beispiel

a = 13 = 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 1101

b = 5 = 1 · 22 + 0 · 21 + 1 · 20 = 101

1.3.1 Multiplikationsschema

1 1 0 1 · 1 0 1

1 1 0 1

0 0 0 0

1 1 0 1

1 0 0 0 0 0 1 = 1 · 26 + 1 · 20 = 65



Implementierung

Multiplikation

int x = a;

int y = b;

int z = 0;

while ( y > 0 )

if ((y % 2) == 0) // (*)

y = y / 2;

x = x + x;

else

y = y - 1;

z = z + x;



Wert derVariablenzu Beginn eines jeden Durchlaufs durch die

while–Schleife:

x y z Anzahl der Schleifeniterationen

1101 101 0 0

1101 100 1101 1

11010 10 1101 2

110100 1 1101 3

110100 0 1000001 4



1.3.2 Beweis für die Korrektheit des Verfahrens

Wir verwenden eineSchleifeninvariante

P = ( y ≥ 0 und z + x · y = a · b )

und zeigen folgende 3 Behauptungen:

1. BehauptungP ist vor Ausführung derwhile–Schleife richtig, d.h. vor erstmaliger

Ausführung derif –Anweisung (*).

2. BehauptungP bleibt bei einmaliger Ausführung derwhile–Schleife richtig, d.h.

gilt die kontrollierende Bedingung(y > 0) derwhile–Schleife und die

BedingungP vor der Ausführung der Anweisung (*), so gilt nach der

Ausführung von (*) ebenfallsP .



3. BehauptungDie while–Schleifeterminiert, d.h. die zu iterierendeif–Anweisungwird nur endlich oft ausgeführt.

Beweise

1. Vor derwhile–Schleife giltx = a, y = b = 0, z = 0 und folglichz + x · y = 0 + a · b = a · b.

2. Wir nehmen an, es gelte vor der Ausführung von (*):

( y ≥ 0 und z + x · y = a · b ) und y > 0.

Ist y gerade, so wirdy halbiert undx verdoppelt. Aber es bleibt beiAusführung von (*) das Produktx · y unverändert, und es gilt nach derAusführung von (*) immer noch

( y ≥ 0 und z + x · y = a · b ).



Ist y ungerade, so wirdy um1 verringert undz umx erhöht. Also giltnach der Ausführung von (*):

z′ +x′ ·y′ = (z +x)+x · (y−1) = z +x+x ·y−x = z +x ·y = a · b,

d.h. die SchleifeninvarianteP ist nach wie vor gültig.

3. Jede Ausführung derif–Anweisung (*) in derwhile–Schleifeverringert den Wert vony um mindestens1 (denn füry > 0 gilt auchy2 ≤ y − 1). Nach höchstensy Iterationen muss alsoy = 0 werden, unddamit die Schleifeterminieren.

Bei Terminierung des Verfahrens gilty = 0 und es gilt immer noch dieSchleifeninvariante

P = ( y ≥ 0 und z + x · y = a · b ).

Folglich gilt y = 0 undz = z + x · y = a · b, d.h. das Produkt vona undb

wird korrekt berechnet.



1.4 Aktienkurs–Analyse

1 5 10 15

1

5

10

1, 4,−3,−3, 1,−2, 3,−1, 4,−1,−4,−3, 0, 1

Eingabereihenfolge: X [1 . . . 14], S ∈ N0

Kurszur Zeiti: S + X [1] + . . . + X [i − 1]



1.4.1 Das Maximum–Subarray–Problem

Maximum–Subarray–ProblemGegeben sei eine FolgeX vonN ganzen Zahlen in einem Array.

Gesucht ist die maximale Summe aller Elemente in einer

zusammenhängenden Teilfolge.

Sie wird als maximale Teilsumme bezeichnet, jede solche Folge als

maximale Teilfolge.

im Beispielmaximale TeilfolgeX [7 . . . 9], Summe:6

zum Vergleich:X [5 . . . 10], Summe:4



1.4.2 Naives Verfahren

Berechne für jedesi ∈ 〈1, N 〉 sukzessive die Teilsummen

X [i] + X [i + 1] + . . . + X [j]

für j = 1, . . . , N und aktualisiere jeweils das Maximum.

Aufwand für jedesi:

• N − i Additionen,

• N − i + 1 Vergleiche



Gesamtaufwand:

• Additionen:

A(N) = (N − 1) + (N − 2) + ... + (N − N)

= 0 + 1 + 2 + . . . + N − 1 =N · (N − 1)

2

• Vergleiche:

V (N) = A(N) + N

• Summe:

T (N) = A(N) + V (N) = 2 · A(N) + N = N · (N − 1) + N = N2



1.4.3 Divide–and–Conquer–Ansatz

1. DivideTeile die FolgeX [1], . . . , X[N ] in zwei Teilfolgen

X [1], . . . , X[M ]

X [M + 1], . . . , X[N ]

Dann liegt die maximale Teilfolge entweder ganz in einem derbeiden

Teile oder sie umfaßt die Trennstelle.

Als linkes (rechtes)Randmaximumbezeichnen wir die Summe der

TeilfolgeX [l], . . . , X[M ] (X [M + 1], . . . , X[r] ), für die die Summe

maximal wird unter allen Teilfolgen, die mitl ∈ 〈0, M 〉 beginnen (mit

r ∈ 〈M + 1, N 〉 enden).



1 l M M+1 r

... ... ... ...

N

Die Randmaximakönnen mit folgendem Aufwand bestimmt werden:

• links: M − 1 + M = 2 · M − 1

• rechts:(N − M − 1) + N − M = 2 · (N − M) − 1

Summe: 2 · N − 2 Schritte

Die Randmaxima seienrl undrr.

Falls die maximale Teilfolge den RandX [M ] umfaßt, so ist

X [l], . . . , X[M ], X [M + 1], . . . , X[r] eine maximale Teilfolge mit

Teilsummerl + rr.



2. ConquerLöse TeilproblemeX [1], . . . , X[M ] undX [M + 1], . . . , X[N ]

rekursiv. Die Maxima seiensl undsr.

3. MergeDie maximale Teilsumme ergibt sich nun als

max_t_sum = maxsl, sr, rl + rr



BeispielDie maximale TeilfogeX [7], X [8], X [9] (3,−1, 4) ist eindeutig.

• M = 7:

maximale Teilfolge umfaßt den Rand:

l = 7 , r = 9

rl = 3 , rr = 3

• M = 8:

maximale Teilfolge umfaßt den Rand:

l = 7 , r = 9

rl = 2 , rr = 4

• M = 6:

maximale Teilfolge liegt ganz im rechten Teil



Sei nunT (N) dieAnzahl der Schritte, die erforderlich ist, um das

Divide–and–Conquer–Verfahren für eine FolgeX [1], . . . , X[N ]

auszuführen.

SeiN = 2k, k ∈ N0, und es werde jeweils in der Mitte geteilt:M = N2 .

Rekursionsformel

T (N) = 2 · T

(N

2

)

+

2·N+1︷︸︸︷

2 · N − 2 + 3

T (1) = 1



Folglich gilt:

T(2k

)= 21 · T

(2k−1

)+ 2 · 2k + 1

= 22 · T(2k−2

)+ 22 · 2k−1 + 21 + 21 · 2k + 1

= 23 · T(2k−3

)+ 23 · 2k−2 + 22 + 22 · 2k−1 + 21 + 21 · 2k + 1

...

= 2k · T (1) + k · 2k+1 +(2k−1 + . . . + 1

)

︸︷︷︸

2k−1

= (k + 1) · 2k+1 − 1

Wennk = log N erhalten wir weiter:

T (N) = 2 · ((log N) + 1) · N − 1

≤ 4 · N · log N − 1 für N ≥ 2



1.4.4 Das Scan–Line–Prinzip

Ein weiteres algorithmisches Prinzip ist dasScan–Line–Prinzip:

• Wir durchlaufen die Eingabe in der durch eine aufsteigend sortierte,

lineare Folge vonImplikationsstellenvorgegebenen Reihenfolge, in

unserem Falle die Positionen1, . . . , N der Eingabefolge.

• Wir führen zugleich eine vom jeweiligen Problem abhängige,

dynamische veränderliche, d.h. an jeder Implikationsstelle

gegebenenfalls zu korrigierende Information mit.

In unserem Falle sind dies

– die maximale SummebisMaxeiner Teilfolge im gesamten bisher

inspizierten Anfangsstück und

– das an der Implikationsstelle endende rechte Randmaximum

ScanMaxdes bisher inspizierten Anfangsstücks.



1 NbisMax ScanMax

a

Scanline

Das rechte Randmaximum der neuen Folge mitM + 1 Elementen enthält

man aus dem rechten Randmaximum der Folge mitM Elementen durch

Hinzunahme vona, falls ScanMaxalt + a > 0, ansonsten ist die leere Folge

das neue rechte Randmaximum.



Implementierung

Scanline

public class Scanline

public static void main(String[] args)

int X[] = 1, 4, -3, -3, 1, -2, 3,

-1, 4, -1, -4, -3, 0, 1;

System.out.println(scanLine(X));

public static int scanLine(int[] X)

// Initialisierung

int N = X.length;

int scanMax = 0;

int bisMax = 0;



Scanline

// Iteration

for (int i = 0; i < N; i++) // 2 Schritte

int a = X[i]; // 2 Schritte

// Update ScanMax und bisMax

if (scanMax + a > 0) // 2 Schritte

scanMax += a; // 1 Schritt

else

scanMax = 0;

bisMax = java.lang.Math.max(bisMax, scanMax);

// 2 Schritte

return bisMax;



Dieser Algorithmus benötigt nur linear (inN ) viele Durchläufe derfor –

Schleife und bei jedem Durchlauf, d.h. an jeder Implikationsstelle, ist der

Aufwand beschränkt durch eine Konstantec ∈ N0 (in unserem Fall z.B.

c = 9).

Der Gesamtaufwand ist alsoT (N) = 9 · N + 3.



1.5 Komplexität von Algorithmen

Der Aufwand oder die Komplexität eines Algorithmus gibt dieAnzahl der

problemrelevanten Elementaroperationen bei seiner Ausführung an. Dazu

gibt man eine FunktionT : N → R an, die von der Problemgrößen

abhängt.

Wie sind in der Regel zufrieden, wenn wir dieGrößenordnungoder die

Wachstumsklassedes Algorithmus bestimmen können. Wachstumsklassen

sind Mengen von Funktionen, die für großen etwa gleichen Verlauf

aufweisen.



Definition (GrößenordnungsmaßeO, Ω, Θ)Seif : N → R eine Funktion.

(i) O(f) = g : N → R | ∃ n0 ∈ N, ∃ c > 0 : ∀ n ≥ n0 : g(n) ≤ c·f(n)

(ii) Ω(f) = g : N → R | ∃ n0 ∈ N, ∃ c > 0 : ∀ n ≥ n0 : g(n) ≥ c ·f(n)

(iii) Θ(f) = O(f) ∩ Ω(f)

Sprechweiseng ist höchstens| mindestens| genauvon der Größenordnungf ,falls g ∈ O(f) | g ∈ Ω(f) | g ∈ Θ(f) ist.

Offensichtlich gilt f ∈ O(f), f ∈ Ω(f), f ∈ Θ(f) sowie

O(g) ⊆ O(f) ⇔ g ∈ O(f) ⇔ f ∈ Ω(g) ⇔ Ω(f) ⊆ Ω(g).

Wir schreiben oft auchg(n) ∈ O(f(n)), u.s.w.. . .



1.5.1 Verhalten wichtiger Funktionen

10

20

30

40

5 10 15

2n n

2

nlog (n)2

n

log (n)2

50



2 4 8 16 . . . 1.024

log2(n) 1 2 3 4 . . . 10

n 2 4 8 16 . . . 1.024

n · log2(n) 2 8 24 64 . . . 10.240

n2 4 16 64 256 . . . 1.048.576

2n 4 16 256 65.536 . . . ≥ 10341

Es gilt:

O(log2(n)) ( O(n) ( O(n · log2(n)) ( O(n2) ( O(2n)



FolgerungSeienf, g : N → R+.

Falls

limn→∞

g(n)

f(n)= c

existiert, so gilt:

(i) Falls c = 0 ist, so giltg ∈ O(f) (undf ∈ Ω(g))

sowief 6∈ O(g) (undg 6∈ Ω(f)).

(ii) Falls c > 0 ist, so giltg ∈ Θ(f) (undf ∈ Θ(g)).

(iii) Falls c = ∞ ist, so giltf ∈ O(g) (undg ∈ Ω(f))

sowieg 6∈ O(f) (undf 6∈ Ω(g)).



FürPolynomeist nur der Grad ausschlaggebend:

f(n) =k∑

i=0

ai · ni, ai ∈ R, 0 ≤ i ≤ k − 1, ak ∈ R+

g(n) =l∑

i=0

bi · ni, bi ∈ R, 0 ≤ i ≤ l − 1, bl ∈ R+

Dann gilt:

f(n) ∈ O(g(n)) ⇔ k ≤ l

O(f(n)) = O(g(n)) ⇔ k = l



Beispiel

f(n) = 2 · n2 + 7 · n − 3

g(n) = n3 − 16 · n2

h(n) = n2

⇒ f(n) ∈ O(g(n)), g(n) 6∈ O(f(n)), f(n) ∈ Θ(h(n))

a2 · n2 + a1 · n + a0 | a2 ∈ R+, a1, a0 ∈ R ⊆ Θ(h(n))



1.5.2 Weitere Rechenregeln

(i) Seig(n) ∈ O(f(n)) unda, b ∈ R und es existiere einn′ ∈ N0 mit

f(n) ≥ 1, für allen ≥ n′. Dann gilta · g(n) + b ∈ O(f(n)).

Füra > 0 gilt: O(a · f(n) + b) = O(f(n)).

Wegenlog2(n) = log2(b) · logb(n) gilt für b > 1 also

O(log2(n)) = O(logb(n)).

(ii) Seienf(n) ∈ O(h1(n)) undg(n) ∈ O(h2(n)) undhi(n) ≥ 0, für alle

n ≥ n′. Dann gilt f(n) + g(n) ∈ O(h1(n) + h2(n)).

(iii) Falls einn′ ∈ N0 existiert mitf(n) ≥ 0, für allen ≥ n′, so gilt auch

f(n) · g(n) ∈ O(h1(n) · h2(n)).



Beweis

(i) Wegeng(n) ∈ O(f(n)) gibt esn0 ∈ N, c > 0 mit g(n) ≤ c · f(n), für

allen ≥ n0. Wegenf(n) ≥ 1, für allen ≥ n′, gilt:

a · g(n) + b ≤ a · c · f(n) + |b| · f(n)︸︷︷︸

(a·c+|b|)·f(n)

,

für allen ≥ maxn0, n′.



(ii) Wegenf(n) ∈ O(h1(n)) undg(n) ∈ O(h2(n)) gibt esn1 ∈ N und

c1 > 0 sowien2 ∈ N undc2 > 0 mit

f(n) ≤ c1 · h1(n) , für allen ≥ n1,

g(n) ≤ c2 · h2(n) , für allen ≥ n2.

Somit gilt:

f(n) + g(n) ≤ maxc1, c2︸︷︷︸

c

·(h1(n) + h2(n))

für allen ≥ maxn1, n2, n′1, n

′2

︸︷︷︸

n0

.



(iii) Für alle n ≥ n′ gilt f(n) ≥ 0 und somit auch

h1(n) ≥1

c1· f(n) ≥ 0 , für allen ≥ maxn1, n

′.

Somit gilt:

f(n) · g(n) ≤ c1 · c2︸︷︷︸

c

·h1(n) · h2(n), für alle n ≥ maxn1, n2, n′

︸︷︷︸

n0

.

2



1.5.3 Rekursionsgleichungen

SatzEs seiena, b ≥ 0, c > 1, n = ck, k ∈ N+ undf(n) beliebig.

Dann hat die Gleichung

T (1) = b,

T (n) = a · T(n

c

)

+ f(n)

die Lösung

T (n) = b · ak +

k−1∑

j=0

aj · f(ck−j

).



BeweisBeweis durch vollständige Induktion überk.Induktionsanfang, k = 0:

T(n0

)= T (1) = b = b · a0 +

−1∑

j=0

aj · f(c0−j

)

Induktionsschluß, k → k + 1:

T(ck+1

)= a · T

(ck

)+ f

(ck−1

)

I.A.= a ·

b · ak +

k−1∑

j=0

aj · f(ck−j

)

+ f(ck+1

)

︸︷︷︸

a0·f(ck+1−0)

= b · ak+1 +k∑

j=0

aj · f(ck+1−j

)

2



Wir interessieren uns nur für zwei spezielle Funktionenf(n):

f(n) = d · n und f(n) = d

SatzEs seiena, b ≥ 0, c > 1, n = ck, k ∈ N+ undd > 0.Dann gilt für die Lösung der Gleichung

T (1) = b,

T (n) = a · T(n

c

)

+ d · n

die Abschätzung

T (n) ∈

O (n) a < c

O (n · logc(n)) falls a = c

O(nlog

c(a)

)a > c (d.h. logc(a) > 1)



BeweisWir wenden den obigen Satz fürf(n) = d · n an:

T (n) = b · ak + d · ck ·k−1∑

j=0

(a

c

)j

Es gilt für die geometrische Reihe∑k−1

j=0

(ac

)j:

k−1∑

j=0

(a

c

)j

=k−1∑

j=0

qj =1 − qk

1 − q

für q = ac6= 1.



1. a < c :

Dann gilt0 ≤ q = ac

< 1 und

k−1∑

j=0

(a

c

)j

≤1

1 − q

unabhängig vonk, d.h. unabhängig von n.Damit gilt

T (n) ≤ b · ak + d · ck ·1

1 − q

≤ b · ck + d · ck ·1

1 − q

= ck ·

(

b +d

1 − q

)

= n ·

(

b +d

1 − q

)

∈ O(n).



2. a = c :

Dann gilt

k−1∑

j=0

(a

c

)j

=

k−1∑

j=0

1 = k,

und somit

T (n) = b · ck + d · ck · k

= ck · (b + d · k)

= n · (b + d · logc(n)) ∈ O (n · logc(n))



3. a > c :

Dann giltq = ac

> 1 und

k−1∑

j=0

(a

c

)j

=qk − 1

q − 1≤ qk ·

1

q − 1,

und somit

T (n) ≤ b · ak + d · ck ·ak

ck·

1

q − 1

= b · ak + d · ak ·1

q − 1

= ak ·

(

b +d

q − 1

)

= alogc(n) ·

(

b +d

q − 1

)

= nlogc(a) ·

(

b +d

q − 1

)

∈ O(

nlogc(a)

)

.

2



BemerkungEs gilt:

logc

(

nlogc(a)

)

= logc(a) · logc(n) = logc(n) · logc(a) = logc

(

alogc(n)

)

und damit folgt

nlogc(a) = alog

c(n)



SatzEs seiena, b ≥ 0, c > 1, n = ck, k ∈ N+ undd > 0.

Dann gilt für die Lösung der Gleichung

T (1) = b,

T (n) = a · T(n

c

)

+ d

die Abschätzung

T (n) ∈

O (logc(n)) falls a = 1

O(nlog

c(a)

)falls a 6= 1 (= O(n) für a = c > 1)



BeweisWir wenden den obigen Satz fürf(n) = d an:

T (n) = b · ak + d ·k−1∑

j=0

aj

1. a = 1 :

Dann gilt

k−1∑

j=0

aj =k−1∑

j=0

1 = k,

und somit

T (n) = b · ak + d · k

= b · 1k + d · k

= b + d · logc(n) ∈ O (logc(n)) .



2. a 6= 1 :

Dann gilt

k−1∑

j=0

aj =ak − 1

a − 1,

und somit

T (n) = b · ak + d ·ak − 1

a − 1≤

b · ak + d · ak

a−1 für a > 1

b · ak + d · 11−a

für a < 1

=

alogc(n) ·

(

b + 1a−1

)

für a > 1

b · alogc(n) + d

1−afür a < 1

=

nlogc(a) ·

(

b + 1a−1

)

für a > 1

b · nlogc(a) + d

1−afür a < 1

∈ O(

nlogc(a)

)

.

2


Documents

1 Grundlagen - uni-wuerzburg.de...Praktische Informatik I - Algorithmen und Datenstrukturen Wintersemester 2006/07 3. Behauptung Die while–Schleife terminiert, d.h. die zu iterierende