Der Schönhage-Paterson-Pippenger-Median-Algorithmus Der SPP-Algorithmus

Definition: Sei $k \in \mathbbm{N}\backslash\{0\}.\ P_k$ ist die folgende partielle Ordnung:

Spezielle Binomialbäume mit ,,Zentren``.

Definition:

1.

Der Baum H₀ besteht aus einem Knoten und dieser ist auch das Zentrum.

2.

H_2h (h>0) besteht aus zwei H_2h-1, deren Zentren durch eine neue Kante verbunden sind. Das Zentrum des H_2h ist das kleinere der beiden Zentren der H_2h-1.

3.

$H_{2h+1} (h \geq 0)$ besteht aus zwei H_2h, deren Zentren durch eine neue Kante verbunden sind, sein Zentrum ist das größere dieser beiden Zentren.

Das Zerlegungslemma:

a)

H_h hat 2^h Knoten, es werden 2^h-1 Vergleiche benötigt, um H_h zu konstruieren.

b)

H_2h kann zerlegt werden in

• sein Zentrum
• eine Menge $\{H_1, H_3, \ldots, H_{2h-1}\}$ von disjunkten Teilbäumen, deren Zentren alle größer sind als das Zentrum von H_2h.
• eine Menge $\{H_0, H_2, H_4, \ldots, H_{2h-2}\}$ von disjunkten Teilbäumen mit Zentren kleiner als das von H_2h.

c)

H_2k+1 kann so zerlegt werden, daß die Zusammenhangskomponente des Zentrums genau 2^k Knoten $\geq$ dem Zentrum enthält, indem höchstens 2^k+1-1 Kanten entfernt werden.
H_2k kann so zerlegt werden, daß die Zusammenhangskomponente des Zentrums genau 2^k Knoten enthält, die alle $\leq$ dem Zentrum sind, indem höchstens 2^k-1 Kanten entfernt werden.

d)

Falls $k \leq 2^h-1$, dann kann H_2h so zerlegt werden, daß die Zusammenhangskomponente des Zentrums genau 2k+1 Elemente enthält, von denen k größer und k kleiner als das Zentrum sind ($\Rightarrow P_k$).
Dazu genügt es, höchstens 3k+2h Kanten zu entfernen. Die restlichen Zusammenhangskomponenten sind wieder H_i.

Bemerkung: Bei jedem Konstruktionsschritt wird ein Vergleich durchgeführt, um zu bestimmen, welcher der beiden Teilbäume das kleinere Zentrum hat. Im Algorithmus von Schönhage, Paterson und Pippenger werden aus Teilstücken H_r größere Bäume H_r+1 zusammengebaut, wodurch schrittweise eine partielle Ordnung auf den Eingabewerten bestimmt wird. Wurde ein Baum H_2h hinreichender Größe hergestellt, so wird er durch Zerlegung in einen Baum umgewandelt, der nur noch sein altes Zentrum, sowie k darüberliegende und k darunterliegende Elemente enthält, wobei $k \le 2^h-1$. Im folgenden Beispiel wollen wir H₄ zerlegen und wählen k = 3:

Um einen H₄ derart zu zerlegen, müssen wir 5 Kanten aufbrechen. Dabei werden drei H₀, ein H₁ sowie ein H₂ abgespalten.

Übrig bleibt die gewünschte Struktur mit k Knoten über dem Zentrum und k unter dem Zentrum, wodurch eine partielle Ordnung auf 2k+1 Eingabewerten bestimmt wurde:

Die bei der Zerlegung angefallenen Reststücke werden beim Aufbau weiterer Bäume benutzt. So geht das bereits angesammelte Wissen über die Ordnung der Elemente nicht verloren. Beweis der Teile a) bis d) des Zerlegungslemmas:

a)

Lemma 1: H_r hat 2^r Knoten, es werden 2^r-1 Vergleiche benötigt, um H_r aufzubauen.

Beweis: In jedem der r Konstruktionsschritte wird die Anzahl der Knoten verdoppelt. Da wir mit einem Knoten beginnen, hat H_r folglich 2^r Knoten. Die Anzahl der notwendigen Vergleiche C_r unterliegt folgender Rekursionsgleichung ($r\ge 1$): C_r=1+2C_r-1 und C₀=0. Damit folgt sofort C_r=2^r-1. $\Diamond$

b)

Lemma 2: H_r kann in folgende disjunkte Bereiche unterteilt werden:

• sein Zentrum,
• eine Reihe H₁, H₃, ..., H_r-1 (r gerade) bzw. ..., H_r-2 (r ungerade) von Unterbäumen, deren Zentren über dem von H_r liegen,
• eine Reihe H₀, H₂, ..., H_r-2 (r gerade) bzw. ..., H_r-1 (r ungerade) von Unterbäumen, deren Zentren unter dem von H_r liegen.

Beweis: durch Induktion über r. Induktionsanfang: für H₀ gilt die Behauptung. Induktionsannahme: die Behauptung gelte für H_r-1.

1.

Sei r = 2h, h > 0. H_2h besteht aus zwei H_2h-1, wobei das kleinere der beiden alten Zentren das neue Zentrum z bildet. Wende auf den H_2h-1, der z enthält, die Induktionsannahme an. Wir können diesen Unterbaum also in z, sowie H₁, H₃, ..., H_2h-3 (Zentren über z) und H₀, H₂, ..., H_2h-2 (Zentren unter z) partitionieren. Zusammen mit dem H_2h-1, dessen Zentrum über z liegt, ergibt sich die Induktionsbehauptung für H_2h.

2.

Sei $r = 2h+1, h \ge 0$. H_2h+1 besteht aus zwei H_2h, wobei das größere der beiden alten Zentren das neue Zentrum z bildet. Wende auf den H_2h, der z enthält, die Induktionsannahme an. Wir können diesen Unterbaum also in z, sowie H₁, H₃, ..., H_2h-1 (Zentren über z) und H₀, H₂, ..., H_2h-2 (Zentren unter z) partitionieren. Zusammen mit dem H_2h, dessen Zentrum unter z liegt, ergibt sich die Induktionsbehauptung für H_2h+1.

$\Diamond$

Wir bezeichnen im folgenden mit H_2h^- den Baum, der entsteht, wenn wir H_2h so zerlegen, daß alle Elemente oberhalb des Zentrums wegfallen. Mit H_2h+1⁺ bezeichnen wir den Baum, der entsteht, wenn wir H_2h+1 so zerlegen, daß alle Elemente unterhalb des Zentrums wegfallen.

c)

Lemma 3: H_2h^- und H_2h+1⁺ haben jeweils 2^h Knoten. Bei der Herstellung aus H_2h bzw. H_2h+1 werden 2^h-1 bzw. 2^h+1-1 Kanten aufgebrochen. Die wegfallenden Teile haben die Form H_s, s < 2h bzw. s < 2h+1.

Beweis: Durch Induktion über r. Induktionsanfang: für H₀ und H₁ gilt die Behauptung. Induktionsannahme: die Behauptung gilt für alle H_p, p < r.

1.

Sei r = 2h, h > 0. Wir betrachten die Partitionierung von H_2h mit Zentrum z wie in Lemma 2. Die Unterbäume H₁, H₃, ..., H_2h-1 haben ihre Zentren oberhalb von z. Wir trennen sie von H_2h, indem wir h Kanten aufbrechen. Die abgetrennten Teile haben offensichtlich die Form H_s, s < 2h. Bei den Unterbäumen H₀, H₂, ..., H_2h-2, mit Zentren unterhalb von z, wenden wir jeweils die Induktionsannahme an, d.h. wir erzeugen H₀^-, H₂^-, ..., H_2h-2^-. Als Ergebnis erhalten wir H_2h^-. Damit gilt für die Zahl der aufzubrechenden Kanten K^-(2h) zur Herstellung von H_2h^-:

$$K^-(2h) = h + \sum_{i=0}^{h-1}K^-(2i) \stackrel{I.A.}{=} h + \sum_{i=0}^{h-1}(2^i-1) = \sum_{i=0}^{h-1}2^i = 2^h - 1.$$

Für die Zahl E^-(2h) der Elemente in H_2h^- gilt:

$$E^-(2h) = 1 + \sum_{i=0}^{h-1}E^-(2i) \stackrel{I.A.}{=} 1 ... ...2^i = 1 + \underbrace{\sum_{i=1}^{h}2^{i-1}}_{2^h-1} = 2^h.$$

2.

Sei r = 2h+1, h > 0. Wir betrachten die Partitionierung von H_2h+1 mit Zentrum z wie in Lemma 2. Die Unterbäume H₀, H₂, ..., H_2h haben ihre Zentren unterhalb von z. Wir trennen sie von H_2h+1, indem wir h+1 Kanten aufbrechen. Die abgetrennten Teile haben offensichtlich die Form H_s, s < 2h+1. Bei den Unterbäumen H₁, H₃, ..., H_2h-1, mit Zentren oberhalb von z, wenden wir jeweils die Induktionsannahme an, d.h. wir erzeugen H₁⁺, H₃⁺, ..., H_2h-1⁺. Als Ergebnis erhalten wir H_2h+1⁺. Damit gilt für die Zahl der aufzubrechenden Kanten K⁺(2h+1) zur Herstellung von H_2h+1⁺:

$$\begin{split} K^+(2h+1) = & h+1 + \sum_{i=1}^{h}K^+(2(i-1)+... ...um_{i=1}^{h+1}2^{i-1}}_{2^{h+1}-1} - 1 = 2^{h+1}-1.\end{split}$$

Für die Zahl E⁺(2h+1) der Elemente in H_2h+1⁺ gilt:

$$E^+(2h+1) = 1 + \sum_{i=1}^{h}E^+(2(i-1)+1) \stackrel{I.A.}{=} 1 + \underbrace{\sum_{i=1}^{h}2^{i-1}}_{2^h-1} = 2^h.$$

$\Diamond$

d)

Lemma 4: Falls $k \le 2^h-1$, dann kann H_2h so zerlegt werden, daß die Komponente des Zentrums genau 2k+1 Elemente enthält, k davon über und k unter dem Zentrum. Dazu müssen $\le 3k + 2h$ Kanten entfernt werden. Die entfernten Teile sind von der Form H_s, s < 2h.

Beweis: Betrachte die Binärdarstellung von k = k₀ 2⁰ + k₁ 2¹ + ... + k_h-1 2^h-1 und die Partitionierung von H_2h mit Zentrum z wie in Lemma 2.

• Für jedes i mit k_i = 1, betrachte H_2i+1 aus der Sequenz H₁, H₃, ..., H_2h-1 von Unterbäumen deren Zentren oberhalb von z liegen und schneide alle Elemente aus H_2i+1, die kleiner als sein Zentrum sind (bilde also H_2i+1⁺). Dazu müssen höchstens 2k Kanten aufgebrochen werden, denn jedes k_i = 1 steht für 2ⁱ in k, kostet uns aber nach Lemma 2 K⁺(2i+1) = 2ⁱ⁺¹-1 Kanten, also:

  $$\sum_{i=0}^{h-1}k_i K^+(2i+1) \le 2k.$$

  Für jedes i mit k_i = 0, schneide H_2i+1 ganz weg. Dabei werden höchstens h Kanten aufgebrochen. Genau k Elemente oberhalb von z bleiben zurück, da jedes k_i = 1 für 2ⁱ in k steht, und ein H_2i+1⁺ genau E⁺(2i+1) = 2ⁱ Elemente enthält, also:

  $$\sum_{i=0}^{h-1}k_i E^+(2i+1) = k.$$

• Für jedes i mit k_i = 1, betrachte H_2i aus der Sequenz H₀, H₂, ..., H_2h-2 von Unterbäumen, deren Zentren unterhalb von z liegen und schneide alle Elemente aus H_2i, die größer als sein Zentrum sind (bilde also H_2i^-). Dazu müssen höchstens k-1 Kanten aufgebrochen werden, denn jedes k_i = 1 steht für 2ⁱ in k und kostet uns nach Lemma 3 K^-(2i) = 2ⁱ-1 Kanten, also:

  $$\sum_{i=0}^{h-1}k_i(2^i-1) \le k-1.$$

  Für jedes i mit k_i = 0, schneide H_2i ganz weg. Dabei werden höchstens h Kanten aufgebrochen. Genau k Elemente unterhalb von z bleiben zurück, da jedes k_i = 1 für 2ⁱ in k steht, und ein H_2i^- genau E^-(2i) = 2ⁱ Elemente enthält, also:

  $$\sum_{i=0}^{h-1}k_i E^-(2i) = k.$$

Damit ergibt sich für die Gesamtanzahl aufzubrechender Kanten eine obere Schranke von 3k+2h. Lemma 3 liefert uns darüberhinaus die gewünschte Aussage über die Form der abgetrennten Teile. $\Diamond$

Betrachte H_2h

• ,,größer``: $H_{2h-1}, H_{2h-3}, \ldots, H_1$
• ,,kleiner``: $H_{2h-2}, H_{2h-4}, \ldots, H_0$

U(h):= Anzahl der Elemente in $H_{2h} \geq$ Zentrum: U(h)=2U(h-1)=2^hU(0)=2^h
D(h):= Anzahl der Elemente in $H_{2h} \leq$ Zentrum: D(h)=2D(h-1)=2^hD(0)=2^h

Anzahl der Kanten, die entfernt werden müssen:

$$\left. \begin{array} {l} \begin{split} \text{C}_u(h)&\leq... ...ght\} \quad \text{C}_H \leq 2^{h+1}-2+2^h-1 \approx 3\cdot 2^h$$

Kette von P_k's:

Gesamtzahl der Elemente:

$$\begin{split} &n\\ &t(2k+1)\ \text{in den}\ P_k\text{'s}\\ &r=n-t(2k+1)\ \text{Rest} \end{split}$$

Wenn r<t-1, dann wissen wir, daß top größer ist als

$$k+(t-1)(k+1)\gt k+(k+1)\left(\frac{n+1}{2k+2}-1\right)=\frac{n-1}{2}$$

$\Rightarrow$ top > Median

$$\begin{split} &k:=\left\lfloor n^{\frac{1}{4}} \right\rfloor\\ &h\text{ sdg. }2^{h-1}\leq k < 2^h \end{split}$$

Definiere: r:= Anzahl der noch im H_2h Produktionsprozeß steckenden Elemente. (für jedes i<2h höchstens ein $H_i \Rightarrow r \leq \sum\limits^{2h-1}_{i=0} = 2^{2h}-1$)
R:= Anzahl der im letzten Schritt zu sortierenden Elemente. Es gilt: $t \leq r+1$, und damit

$$R=t(2k+1)+r \leq 2^{2h}(2k+1)+2^{2h}-1$$

m:= Gesamtzahl der im Algorithmus produzierten P_k's.

$$m=t+2\frac{n-R}{2(k+1)}= t + \frac{n-R}{k+1}$$

Gesamtzahl der vom Algorithmus durchgeführten Vergleiche =

1.

Anzahl der Kanten in allen P_k's

2.

+ Anzahl der Kanten, die gelöscht werden, um die P_k's zu formen

3.

+ Anzahl der Kanten, die zum Schluß in übriggebliebenen $H_i\text{'s}\ (i < 2h)$ stecken

4.

+ Anzahl der Vergleiche, um jedes Zentrum der P_k's in die (sortierte) Kette einzufügen

5.

+ Anzahl der Vergleiche, um die zum Schluß übriggebliebenenen R Elemente zu sortieren

$$\leq \left( \frac{n-R}{k+1}+t \right) \left[ \underbrace{2k}... ...c{n}{2k+1}}_4 \right] + \underbrace{R\log R}_5+\underbrace{r}_3$$

$k:= \left\lfloor n^{\frac{1}{4}} \right\rfloor$, h so daß $2^{h-1} \leq k < 2^h$

$$\begin{split} \text{Damit } r &= \mathcal{O}(k^2)\\ t &= \m... ...hl der Vergleiche } &= \text{T}(n) \leq 5n + o(n)\\ \end{split}$$

Verbesserte Version: T(n) = 3n + o(n)
Dor/Zwick: 2,95n + o(n)

Bester bekannter Algorithmus: K.Zwick ( 2.95n+o(n) )
Literatur: SPP: Finding the Median. JCSS 13(1976) p.84-199