View
215
Download
0
Category
Preview:
Citation preview
Rekursive Funktionen
I Beispiel fur das “Skelett” einer rekursiven Funktion:
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
I Die Kosten fur einen Aufruf an rek bestehen ausI den Kosten aller Blocke t =
∑i Bi // “aktuelle” Kosten
I den Kosten aller rekursiven Aufrufe.
I Wie konnen wir die Gesamtkosten ubersichtlich bestimmen?
Rekursionsbaume zeigen die Struktur eines rekursiven Algos
Rekursive Funktionen
I Beispiel fur das “Skelett” einer rekursiven Funktion:
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
I Die Kosten fur einen Aufruf an rek bestehen aus
I den Kosten aller Blocke t =∑
i Bi // “aktuelle” KostenI den Kosten aller rekursiven Aufrufe.
I Wie konnen wir die Gesamtkosten ubersichtlich bestimmen?
Rekursionsbaume zeigen die Struktur eines rekursiven Algos
Rekursive Funktionen
I Beispiel fur das “Skelett” einer rekursiven Funktion:
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
I Die Kosten fur einen Aufruf an rek bestehen ausI den Kosten aller Blocke t =
∑i Bi // “aktuelle” Kosten
I den Kosten aller rekursiven Aufrufe.
I Wie konnen wir die Gesamtkosten ubersichtlich bestimmen?
Rekursionsbaume zeigen die Struktur eines rekursiven Algos
Rekursive Funktionen
I Beispiel fur das “Skelett” einer rekursiven Funktion:
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
I Die Kosten fur einen Aufruf an rek bestehen ausI den Kosten aller Blocke t =
∑i Bi // “aktuelle” Kosten
I den Kosten aller rekursiven Aufrufe.
I Wie konnen wir die Gesamtkosten ubersichtlich bestimmen?
Rekursionsbaume zeigen die Struktur eines rekursiven Algos
Rekursive Funktionen
I Beispiel fur das “Skelett” einer rekursiven Funktion:
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
I Die Kosten fur einen Aufruf an rek bestehen ausI den Kosten aller Blocke t =
∑i Bi // “aktuelle” Kosten
I den Kosten aller rekursiven Aufrufe.
I Wie konnen wir die Gesamtkosten ubersichtlich bestimmen?
Rekursionsbaume zeigen die Struktur eines rekursiven Algos
Rekursive Funktionen
I Beispiel fur das “Skelett” einer rekursiven Funktion:
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
I Die Kosten fur einen Aufruf an rek bestehen ausI den Kosten aller Blocke t =
∑i Bi // “aktuelle” Kosten
I den Kosten aller rekursiven Aufrufe.
I Wie konnen wir die Gesamtkosten ubersichtlich bestimmen?
Rekursionsbaume zeigen die Struktur eines rekursiven Algos
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
}
......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ...
......
...
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ...
......
...
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
...
...
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
...
...
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Rekursionsbaume
rek(. . . ){
. . . // Block 1rek(. . . ). . . // Block 2rek(. . . ). . . // Block 3
} ......
......
t0
t1 t2
t3 t4 t5 t6
I fur jeden Aufruf genau ein Knoten // Wurzel ≡ erster Aufruf
I v ′ ist i-tes Kind von v ⇔ Aufruf von v ′ ist i-ter Aufruf aus v
I Knotenmarkierungen: aktuelle Kosten tj =∑
i Bi des Aufrufs
I Gesamtkosten: Summe aller aktuellen Kosten t =∑
j tj .
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechts
I Wie ist die Hohe h des Baums?I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechts
I Wie ist die Hohe h des Baums?I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechts
I Wie ist die Hohe h des Baums?I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechts
I Wie ist die Hohe h des Baums?I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechtsI Wie ist die Hohe h des Baums?
I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechtsI Wie ist die Hohe h des Baums?
I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.
I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechtsI Wie ist die Hohe h des Baums?
I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert.
Wann also gilt ( 12 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.
I Die Gesamtkosten sind∑
j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechtsI Wie ist die Hohe h des Baums?
I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1?
Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechtsI Wie ist die Hohe h des Baums?
I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.
I Die Gesamtkosten sind∑
j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum der binaren Suchebs(A, s): // Suche s im sortierten Array A{
falls A leer ist: return NICHT DA
m = A[“Mitte”]falls s < m:
return bs(linke Halfte von A, s)falls m < s:
return bs(rechte Halfte von A, s)falls m = s:
return VORHANDEN}
Θ(1)
Θ(1)
...
Θ(1)
I die Kosten aller Blocke sind unabhangig von der Grosse von A;sie benotigen insgesamt konstante Laufzeit Θ(1)
I immer nur ein rekursiver Aufruf // entw. links oder rechtsI Wie ist die Hohe h des Baums?
I Nur noch ein rek. Aufruf sobald A nur noch ein Element hat.I Die Lange wird stets halbiert. Wann also gilt ( 1
2 )h · |A| = 1? Gdw. |A| = 2h ⇔ h = log2 |A|.I Die Gesamtkosten sind
∑j tj = h ·Θ(1) = Θ(log2 |A|).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .
= n + n + n + · · · = h · n = O(n log2 n).
Der Rekursionsbaum von MergeSortmergesort(A): // A habe Lange n
wenn A hochstens 1 Schlussel hat: return // schon sortiertmergesort(linke Halfte von A)mergesort(rechte Halfte von A)
mische beide sortierten Halften, so dass A sortiert ist
......
. . .
. . .
n
n2
n2
n4
n4
n4
n4
2
1 1
2
11
// alle aktuellen Kosten verstehen sich in “Θ” geklammert
I Stets genau zwei rekursive Aufrufe.
I Arraylange n: Mischen in Zeit Θ(n) // Ubungsaufgabe
I Die Hohe des Baums ist h = log2 n.// analog zu binarer Suche
I Die Gesamtkosten sind∑
j tj ≈ n + 2 · n2 + 4 · n4 + . . .= n + n + n + · · · = h · n = O(n log2 n).
Recommended