Alda - User contributions [en]

Suchen

2008-06-02T21:35:46Z

Friedrich: /* Rotation */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-) 
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': Im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': Finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google (=Ähnlichkeit zwischen Suchbegriffen und Dokumenten) oder das Suchen des nächstengelegenen Restaurants (Ähnlichkeit zwischen eigener Position und Position des Restaurants). Ein wichtigster Spezialfall ist die ''nächste-nachbar Suche''.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachste Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

foundIndex = sequentialSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex < len(a) wenn key gefunden (erster Eintrag mit diesem Wert)

def sequentialSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen, wobei die Problemgröße durch <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden, wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

a = [...,...] # array
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq</math> foundIndex < len(a) wenn key gefunden (erster Eintrag mit diesem Wert)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten (<math> N = 4,\, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind. Ein anderer ungünstiger Fall ist gegeben, wenn nur sehr wenige Suchanfragen erfolgen (weniger als <math>\mathcal{O}(N)</math> viele). Dann wird der Aufwand durch das Sortieren des Arrays dominiert, ist also <math>\mathcal{O}(N \lg N) </math>. Auch dann ist sequentielle Suche vorzuziehen.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anzusehen, die die sukzessive Belegung der Variablen bei verschiedenen Anfragen beschreibt. Die Testfälle wurden nach dem Prinzip des ''domain partitioning'' gewählt. Das zugehörige Array hat die Einträge

a = [2, 3, 4, 5, 6]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (''Schlüssel''), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum'' hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# Einfügen und Suchen im Baum wechseln sich ab. (Wenn das Suchen erst beginnt, nachdem alle Einfügungen erfolgt sind, wäre ein dynamisches Array mit binärer Suche wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None

root = ... # Wurzel des Suchbaums
nodeFound = treeSearch(root, key) # None, falls nichts gefunden

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

Daraus resultiert der folgende Suchalgorithmus:

def treeSort(node,array): # dynamisches Array als 2. Argument
if node is None: # <math>\mathcal{O}(1)</math>
return None:
treeSort(node.left, array) # rekursiv
array.append(node.key) # <math>\mathcal{O}(1)</math>
treeSort(node.right, array) # rekursiv

Komplexität:

<math>
f(N)=\mathcal{O}(1)+f(N_\mathrm{left})+f(N_\mathrm{right})=\mathcal{O}(1)+\mathcal{O}(1)+f(N_\mathrm{leftleft})+f(N_\mathrm{leftright})+\mathcal{O}(1)+f(N_\mathrm{rightleft})
+f(N_\mathrm{leftright})=N\ast\mathcal{O}(1)=\mathcal{O}(N)
</math>

Sortier-Pseudocode:

Sortieren:
(Array) a # unsortiert
(tree) t # zunächst leer
(dynamisches Array) r # später sortiert
for e in a:
t = treeInsert(t, e)
treeSort(t, r)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None:
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
if node.left is None and node.right is None: # Fall 1
node = None
elif node.left is None: # Fall 2
node = node.right # +
elif node.right is None: # Fall 2
node = node.left
else:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[[Image:Baum_Pfad.png]]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets genau einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]: [[Image:Balance.png]]
*: Tiefe T = 4, Balance = 4
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# Selbstbalancierter Baum:
#* Überprüfen der Balance nach jedem Einfügen
#* Umstrukturieren des Baumes, falls Balance > 1 (Suchbaum-Bedingung muss erhalten bleiben)
#* AVL-Bäume (älteste Variante)
#* Rot-Schwarz-Bäume (verbreiteste Variante)
#* Treaps (flexibelste Variante, siehe Übung)
#* Splay trees
#* Andersson Trees (einfachste Variante)
(#* Skip Lists (schnellste Variante, aber kein Binärbaum))

== Umstrukturieren, so dass Suchbaumbedingung erhalten bleibt: ==

Rotation: elementare Umstrukturierungen

[[Image:Baum_Rotation.png]]

def rotateRight(node):
newRoot = node.left
node.left = newRoot.right
newRoot.right = node
return newRoot

def rotateLeft(node):
newRoot = node.right
node.right = newRoot.left
newRoot.left = node
return newRoot

== Balance eines Suchbaumes ==

===Balance eines Baumes zu definieren:===
[[Image:Abbildung1.jpg|200px|right]]
*betrachte <tt>None</tt> als zusätzlichen Knoten : '''sentinel''' ([[englische Sprache|engl.]] für ''Wächter'')
*oder defeniere speziellen sentinel-Knoten
*RS - Pfades : von <tt>root</tt> → ''sentinel''
*Länge eines Pfades ''P'' '''''|P|'''''
* die Balance eines Baumes zu defenieren:
: '''''B = max P '''''<math> \in </math> '''''{RS} |P| - min |P|'''''
:'''''{RS}''''' Menge aller RS-Pfade
;vollständiger Baum: Balance <math>~=0</math>
:Alle Knoten(außer Blättern) haben 2 Kinder.
;perfect balancierter Baum: Balance <math> \le</math> 1
'''alternative Defenition für perfect balancierte Bäume'''
:Für jeden Teilbaum gilt es: rechtes und linkes Kind (für jeden Knoten) sind auch wieder perfect balancierte Bäume und ihre Höhe unterscheidet sich höchstens um '''1'''.

===Größe===
[[Image:baum-v.png|700px|right]]
====Größe des vollständigen Baumes====
Ebene K hat 2 k Knoten.
Falls Tiefe = d , dann N = 20 + 21.....+ 2d = 2d+1 -1

====Größe des perfect balancierten Baumes====
Die Tiefe d, kann nicht besser sein als vollständiger Baum
:'''=>'''N <math> \le</math> 2 d+1 - 1
;schlechteste perfect balancierter Baum : ist ein vollständiger der Tiefe d - 1 + 1, N <math> \ge</math> 2d

:'''=>''' 2d <math> \le</math> N <math> \le</math> 2d+1 - 1

log22d <math>\le</math> log2N <math>\le</math> log2(2d+1 -1) <math>~<</math> log2(2d+1) 

d <math>\le</math> log2 N <math>\le</math> (d + 1)

*Ergibt die Komplexität der Suche im schlechtesten Fall: Anzahl der Vergleiche pro Knoten( = 2 bzw. = 3)<math>\ast</math>Anzahl der Knoten
:<math>\Rightarrow ~f(N)\le 2d \le 2\log_{2}{ N} = \mathcal{O}(\log_{2}{N})</math>

*'''perfekt balancierter Baum '''=> AVL-Baum
*'''balancierter Baum''':
::<math>\forall N:d(N)\le c \ast d (N)</math> und <math>1 \le c < \mathcal {1}</math>

:: d ist die Tiefe von perfekt balancierten Baum

:''Komplexität der Suche'':<math> ~f(N)\le c\ast 2\log_{2}{ N} = \mathcal{O}(\log_{2}{N})</math>
:algorithmisch einfacher als perfekt balancierter Baum, aber fast genauso schnell

====Selbst-balancierter Baum====

def insertTree(node,key):
if node is sentinel: #(None = sentinel)
return Node(key)
if node.key == key:
return Node
if key < node.key:
Node = insertTree(node.left, key)
else:
node.right = insertTree(node.right, key)
#optimiere Balance:
return node

===Anderson-Bäume===

class Node:
def__init__(self, key):
self.key = key
self.left = selft.right = None
#einfügen:
self.level = 1

:''level'' : kodiert Abstand von sentinel
====Regeln====
Es gibt vertikale Kanten(parent.level == child.level + 1 ) und horizontale Kanten(parent.level == child.level)
:*verfeinerter Regel : ''level kodiert reduzierten Abstand von Setinel'' (d.b. horizontale Kanten werden nicht gezählt)
::(die nächste zwei Regeln sichern die Balance):
::*alle RS-Pfade haben die gleiche reduzierte Länge oder ''root'' hat bei allen Pfaden das gleiche Level
::*kein Pfad hat 2 aufeinanderer folgende horizontale Kanten
:*nur Kanten zum rechten Kind dürfen horizontal sein
:*die reduzierte Höhe jedes Blatts ist '''hr=1'''

====Beweis====
Vereinfachung des Algorithmus
:'''Satz''':ein Anderson-Baum ist balanciert.
*1. Sei '''hr'''- die reduzierte Höhe
:<math>\Rightarrow</math> jeder Teilbaum enthält mindestens <math>N\ge 2^{hr} -1 </math> Knoten

::a). Blätter : reduzierte Höhe 1 => <math> N\ge 2^{1} - 1 = 1</math>

::b). inneren Knoten: jeder Unterbaum hat mindestens reduzierte Höhe <math> ~hr - 1 </math>
::::<math>\Rightarrow</math> jeder Unterbaum hat mindestens <math> ~2^{hr} -1 </math> Knoten
::::<math>\Rightarrow</math> <math>N \ge 2 (2^{hr-1} -1)+1 = 2^w - 2 + 1 = 2^{hr} -1</math>
::::alle RS-Pfade heben gleiche Länge
[[Image:Ander.jpg|450px|right]]

*2. Kein Pfad hat 2 aufeinanderfolgende horizontal Kanten
:::<math>\Rightarrow d \le 2 hr + 1</math>
*3. zusammen:
:<math>N \ge 2^{\frac {d}{2}} - 1 </math>

:<math>log_{2}{ N}+1\ge log 2^{\frac {d}{2}} - 1 \ge \frac {d}{2}</math>

:<math> ~d < 2 log_{2}{(N + 1)}</math> - balancierter Baum

:'''Suchzeit''' : <math> ~ f(N) = \mathcal{O}(log{N})</math>

===Wie erreicht man die Balance===
====Rotation====
[[Image:Abbildung4.jpg|text-top|500px|Illustration von Rotation]]

def rotateRight (node):
root = node.left
node.left = root.right
root.right = node
return root
def rotateLeft(node):
root = node.right
node.right = root.left
root.left = node
return root

====Optimierung der Balance====

if node.left is not sentinel and node.level==node.left.level:
node > rotateRight(node)
if node.right is not sentinel and node.right.right is not sentinel and node.level==rotate.right.right.level:
node = rotateLeft(node)
node.level += 1
[[Image:rotate.jpg|text-top]]

----

[[Image:liste.png]]

Prioritätswarteschlangen

2008-06-02T20:33:57Z

Friedrich: /* Heap */

==Sortieren als Suchproblem==
Systematisches Fragen mit True und False kann auch als Baum dargestellt werden. [[Image:penka.png|400px]]

Hier ein Beispiel.Als Eingabe sind drei Zahlen angegeben a={1,2,3},wobei die Reihenfolge nicht bekannt ist. [[Image:trueFalseBeisp.png|700px]] Also mit Eingabe von drei Elemnten müssen im ungünstigsten Fall drei Schritte vorgenommen werden. Die allgemeine Regel lautet: es gibt N mögliche Lösungen =>der Baum muss N Blätter haben =>ein baum mit N Blättern hat mindestens die Höhe logN [[Image:vollbaum.png|left]]

vollständiger Baum (oder balancierter Baum)[http://hci.iwr.uni-heidelberg.de/alda/index.php/Suchen#Balance_eines_Suchbaumes] 2^d+1 Knoten 2^d Blätter 

==Sortieren==
N = n!wenn das Arrey n Elemente hat Zum Beispiel: 3! = 1*2*3 = 6 log6 <math>\approx</math> 2,6 => d = 3 - bei dem Frage-Baum brauch man im ungünstigsten Fall drei Schritte (True/False) log6 <math>\approx</math> 2,6 - weil nicht jeder Pfad zu Ende durchgelaufen sein soll, um die Lösung zu bekommen. d<math>\ge</math>log<math>_2</math>n! = log<math>_2</math>(1,2...n) = log<math>_2</math>1 + log<math>_2</math>2 + ... + log<math>_2</math>n = <math>\sum_{n=1}^n log_2n
</math> 
===Abschätzung von Summen durch Integrale===

gegeben : f(x) - monoton wachsend [[Image:integralGraph.png|400px|left]] 

<math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lfloor x \big\rfloor)dx</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(x)dx
</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lceil x \big\rceil)dx</math> 

<math>\downarrow</math>

<math>\textstyle \int\limits_{x_1}^{x_1 + 1} \underline{f(x_1)}dx</math> + ...+ <math>\textstyle \int\limits_{x_2-1}^{x_2} f(x_2 - 1)dx
</math> = <math>\sum_{k=x_1}^{x_2-1} f(k)</math> ( angenommen <math>x_1</math> und <math>x_2</math> <math>\in </math> <math>\mathbb{N},\mathbb{Z}</math>
) 

wobei f(<math>x_1</math>) = f(<math>\big\lfloor x \big\rfloor </math><math>)_{x_1}^{x_1 +1}</math> 

<math>\textstyle \int\limits_{x_1}^{x_1 +1} f(x_1)dx</math> = f(<math>x_1</math>) <math>\textstyle \int\limits_{x_1}^{x_1 + 1} 1dx</math> = f(<math>x_1</math>)x<math>\textstyle \int\limits_{x_1}^{x_1 + 1}</math> = f(x_1) 

'''<math>\sum_{k=x_1}^{x_2-1} f(k) \le \textstyle \int\limits_{x_1}^{x_2} f(x)dx</math>''' 

<math>\sum_{k=x_1 +1}^{x_2} f(k) \ge \textstyle \int\limits_{x_1}^{x_2} f(x)dx \iff</math> <math>\sum_{k=x_1}^{x_2} f(x) \ge \textstyle \int\limits_{x_1 - 1}^{x_2} f(x)dx
</math> 

'''für uns gilt: f(x) = log<math>_2</math>(x) '''

'''log<math>_2</math>1 +''' <math>\sum_{k=2}^{n} log_2 x\ge\textstyle \int\limits_{1}^{n} log_2 (x)dx
</math> = <math>\frac{1}{ln2}\textstyle \int\limits_{1}^{n} log(x)dx</math> = <math>\frac{1}{ln2}</math> '''[xlogx - x]<math>_{x = 1}^n</math> = nlog<math>_2</math>(n) - <math>\frac{n - 1}{ln2}</math> = <math>\Omega</math>(nlog<math>_2</math>n)'''
 

'''<math>\Rightarrow</math> d = log<math>_2</math>n! = <math>\Omega</math>(nlogn)'''
kein Sortieralgorithmus auf Basis paarweise Vergleiche ist asymthotisch schneller als Mergesort
==Prioritätswarteschlangen==

* Max Priority Quene : insert(x)
x = largest()
removeLargest()

* Min Priority Quene: smallest()
REMOVEsMALLEST()
===Prioritätswarteschlange als Suchproblem===

*Sequentielle Suche - Array mit Prioritäten : insert(x)<=> a.append(x) ( <math>\mathcal{O}(1)</math>(amortisierte Komplexität))

def largest(a): 
if len (a) == 0: 
raise RuntimeError("...") 
''' max = a[0]''' 
'''k = 0 '''
'''for n in range(1, len(a):''' ''(innere Schleife von SelectionSort)'' 
''' if a[n] > max''' (Das ganze hat die Komplexität:''' N = len(a) =>''' <math>\mathcal{O}(N)</math> 
''' man = a[n]''' 
''' k = n''' 
''' return k''' 
Bei kleine Array ist dies die schnellste Methode
===Binärer (balancierter)Suchbaum===
insert => z.B. wie beim Anderson Baum [http://hci.iwr.uni-heidelberg.de/alda/index.php/Suchen#Anderson-B.C3.A4ume] <math>\mathcal{O}(logN)</math> 
def largest(node): # Wurzel 
'''if node.right is not None:''' #rechts stehen immer die großen 
'''return largest(node.right)''' 
'''return node''' #wenn es nicht mehr nach rechts geht, dann haben wir den größten Knoten gefunden 

Das ganze hat <math>\mathcal{O}(logN)</math> Komplexität 
Ergebnis: gute Komplexität aber komplizierte Datenstruktur
===Heap===
*Datenstruktur optimiert für Prioritätssuche - man sucht nicht effizient alle Knoten, sondern nur einen bestimmten z.B. Heap max 
*Definition: ein linkslastiger Binärbaum ist ein Baum mit <math>d(node.left) \geq d(node.right)</math>

Ein Heap ist ein linkslastiger, perfekt balancierter Baum.
(lässt sich max. um 1 unterscheiden)

Man kann einen Heap leicht als Array implementieren, wie folgende Grafik veranschaulicht:
[[Image:heapArray.png|400px]]

'''index[parent] = [(indexChild - 1)/2]''' #[] heißt abgerundet 
'''index[left] = index[parent]2 + 1''' 
'''index[right] = index[parent]2 + 2 

'''=>''' linkslastiger perfect balancierter Binärbaum kann effizient als Array abgespeichert werden 
'''=>'''verwende Indizes wie oben
====Heap - Bedingung====
* die Wurzel hat höhere Prioriät als die Kinder(gilt für jeden Teilbaum) 
'''=>'''Wurzel = array[0] hat die größte Priorität 
def largest(h): 
return h[0] <math>\mathcal{O}(N)</math> 

====Einfügen in einem Heap====

h - Array #speichrt Haep 
def insert(h,x): 
h.append(x) # wir speichern den Wurzel am Ende, so wird glecih zu einem linkssalstigen perfect balancierten Baum (die Haep - Bedingung ist erfüllt) 
upheap(h, len(h) - 1): 

def upheap(h, k): 
"""k-tes Element evtl. an der falsche Stelle 
""" 
v = h[k] 
while True #endlose Schleife 
if k == 0: 
break 
parent = (k - 1/2) 
if h[parent]>v: 
break 
h[k] = h.parent 
k = parent 
h[k] = v 

def removeLargest(h):
'''h[0] = h[len(h) - 1]''' 
'''del h[len(n) - 1]''' <math>\mathcal{O}(1)</math> 
downHeap(h, 0) <math>\mathcal{O}(logN)</math> 

def downHeap(h, k): 
v = h[k] 
while True 
child = 2k + 1 #linke Kind 
if child <math>\ge</math>len{h): 
break 
if child < and h[child] < h[child + 1] #rechtes Kind 
child = child + 1
if v <math>\ge</math> h[child]: 
break 
h[k] = h[child] 
k = child 
h[k] = v

Suchen

2008-05-22T17:49:46Z

Friedrich: /* Insert */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-) 
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': Im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': Finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google (=Ähnlichkeit zwischen Suchbegriffen und Dokumenten) oder das Suchen des nächstengelegenen Restaurants (Ähnlichkeit zwischen eigener Position und Position des Restaurants). Ein wichtigster Spezialfall ist die ''nächste-nachbar Suche''.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex < len(a) wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen, wobei die Problemgröße durch <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden, wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

a = [...,...] # array
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq</math> foundIndex < len(a) wenn key gefunden (erster Eintrag mit diesem Wert)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten (<math> N = 4,\, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind. Ein anderer ungünstiger Fall ist gegeben, wenn nur sehr wenige Suchanfragen erfolgen (weniger als <math>\mathcal{O}(N)</math> viele). Dann wird der Aufwand durch das Sortieren des Arrays dominiert, ist also <math>\mathcal{O}(N \lg N) </math>. Auch dann ist sequentielle Suche vorzuziehen.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anzusehen, die die sukzessive Belegung der Variablen bei verschiedenen Anfragen beschreibt. Die Testfälle wurden nach dem Prinzip des ''domain partitioning'' gewählt. Das zugehörige Array hat die Einträge

a = [2, 3, 4, 5, 6]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (''Schlüssel''), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum'' hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# Einfügen und Suchen im Baum wechseln sich ab. (Wenn das Suchen erst beginnt, nachdem alle Einfügungen erfolgt sind, wäre ein dynamisches Array mit binärer Suche wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None

root = ... # Wurzel des Suchbaums
nodeFound = treeSearch(root, key) # None, falls nichts gefunden

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

Daraus resultiert der folgende Suchalgorithmus:

def treeSort(node,array): # dynamisches Array als 2. Argument
if node is None: # <math>\mathcal{O}(1)</math>
return None:
treeSort(node.left, array) # rekursiv
array.append(node.key) # <math>\mathcal{O}(1)</math>
treeSort(node.right, array) # rekursiv

Komplexität:

<math>
f(N)=\mathcal{O}(1)+f(N_\mathrm{left})+f(N_\mathrm{right})=\mathcal{O}(1)+\mathcal{O}(1)+f(N_\mathrm{leftleft})+f(N_\mathrm{leftright})+\mathcal{O}(1)+f(N_\mathrm{rightleft})
+f(N_\mathrm{leftright})=N\ast\mathcal{O}(1)=\mathcal{O}(N)
</math>

Sortier-Pseudocode:

Sortieren:
(Array) a # unsortiert
(tree) t # zunächst leer
(dynamisches Array) r # später sortiert
for e in a:
t = treeInsert(t, e)
treeSort(t, r)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None:
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
if node.left is None and node.right is None: # Fall 1
node = None
elif node.left is None: # Fall 2
node = node.right # +
elif node.right is None: # Fall 2
node = node.left
else:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[[Image:Baum_Pfad.png]]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets genau einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]: [[Image:Balance.png]]
*: Tiefe T = 4, Balance = 4
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# Selbstbalancierter Baum:
#* Überprüfen der Balance nach jedem Einfügen
#* Umstrukturieren des Baumes, falls Balance > 1 (Suchbaum-Bedingung muss erhalten bleiben)
#* AVL-Bäume (älteste Variante)
#* Rot-Schwarz-Bäume (verbreiteste Variante)
#* Treaps (flexibelste Variante, siehe Übung)
#* Splay trees
#* Andersson Trees (einfachste Variante)
(#* Skip Lists (schnellste Variante, aber kein Binärbaum))

== Umstrukturieren, so dass Suchbaumbedingung erhalten bleibt: ==

Rotation: elementare Umstrukturierungen

[[Image:Baum_Rotation.png]]

def rotateRight(node):
newRoot = node.left
node.left = newRoot.right
newRoot.right = node
return newRoot

def rotateLeft(node):
newRoot = node.right
node.right = newRoot.left
newRoot.left = node
return newRoot

Effizienz

2008-05-19T20:19:52Z

Friedrich: /* Beweis durch Dividieren */

Bei der Diskussion von Effizienz müssen wir zwischen der Laufzeit eines Algorithmus auf einem bestimmten System und seiner prinzipiellen Leistungsfähigkeit (Algorithmenkomplexität) unterscheiden. Der Benutzer ist natürlich vor allem an der Laufzeit interessiert, denn diese bestimmt letztendlich seine Arbeitsproduktivität. Ein Softwaredesigner hingegen muss eine Implementation wählen, die auf verschiedenen Systemen und in verschiedenen Anwendungen schnell ist. Für ihn sind daher auch Aussagen zur Algorithmenkomplexität sehr wichtig, um den am besten geeigneten Algorithmus auszuwählen.

== Laufzeit ==

Aus Anwendersicht ist ein Algorithmus effizient, wenn er die in der Spezifikation verlangten Laufzeitgrenzen einhält. Ein Algorithmus muss also nicht immer so schnell wie möglich sein, sondern so schnell wie nötig. Dies führt in verschiedenen Anwendungen zu ganz unterschiedliche Laufzeitanforderungen:

* Berechnen des nächsten Steuerkommandos für eine Maschine: ca. 1/1000s
* Berechnen des nächsten Bildes für eine Videopräsentation (z.B. Dekompression von MPEG-kodierten Bildern): ca. 1/25s
: Geringere Bildraten führen zu ruckeligen Filmen.
* Sichtbare Antwort auf ein interaktives Kommando (z.B. Mausklick): ca. 1/2s
: Wird diese Antwortzeit überschritten, vermuten viele Benutzer, dass der Mausklick nicht funktioniert hat, und klicken nochmals, mit eventuell fatalen Folgen. Wenn ein Algorithmus notwendigerweise länger dauert als 1/2s, sollte ein Fortschrittsbalken angezeigt werden.
* Wettervorhersage: muss spätestens am Vorabend des vorhergesagten Tages beendet sein

===Laufzeitvergleich===

Da die Laufzeit für den Benutzer ein so wichtiges Kriterium ist, werden häufig Laufzeitvergleiche durchgeführt. Deren Ergebnisse hängen allerdings von vielen Faktoren ab, die möglicherweise nicht kontrollierbar sind:
* Geschwindigkeit und Anzahl der Prozessoren
* Auslastung des Systems
* Größe des Hauptspeichers und Cache, Geschwindigkeit des Datenbus
* Qualität des Compilers/Optimierers (ist der Compiler für die spezielle Prozessor-Architektur optimiert?)
* Geschick des Programmierers
* Daten (Beispiel Quicksort: Best case und worst case [vorsortierter Input] stark unterschiedlich)
All diese Faktoren sind untereinander abhängig. Laufzeitvergleiche sind daher mit Vorsicht zu interpretieren.
Generell sollten bei Vergleichen möglichst wenige Parameter verändert werden, z.B.
* gleiches Programm (gleiche Kompilierung), gleiche Daten, andere Prozessoren
oder
* gleiche CPU, Daten, andere Programme (Vergleich von Algorithmen)
Zur Verbesserung der Vergleichbarkeit gibt es standardisierte [http://en.wikipedia.org/wiki/Benchmark_(computing) Benchmarks], die bestimmte Aspekte eines Systems unter möglichst realitätsnahen Bedingungen testen. Generell gilt aber: Durch Laufzeitmessung ist schwer festzustellen, ob ein Algorithmus ''prinzipiell'' besser ist als ein anderer. Dafür ist die Analyse der [[Effizienz#Komplexität|Algorithmenkomplexität]] notwendig.

===Optimierung===

Wenn sich herausstellt, dass ein bereits implementierter Algorithmus zu langsam läuft, geht man wie folgt vor:

# Man verwendet einen [http://en.wikipedia.org/wiki/Performance_analysis Profiler], um zunächst den Flaschenhals zu bestimmen. Ein Profiler ist ein Hilfsprogramm, dass während der Ausführung eines Programms misst, wieviel Zeit in jeder Funktion und Unterfunktion verbraucht wird. Dadurch kann man herausfinden, welcher Teil des Algorithmus überhaupt Probleme bereitet. Donald Knuth gibt z.B. als Erfahrungswert an, dass Programme während des größten Teils ihrer Laufzeit nur 3% des Quellcodes (natürlich mehrmals wiederholt) ausführen [http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf]. Es ist sehr wichtig, diese 3% experimentell zu bestimmen, weil die Erfahrung zeigt, dass man beim Erraten der kritischen Programmteile oft falsch liegt. Man spricht dann von "[http://en.wikipedia.org/wiki/Optimization_%28computer_science%29#When_to_optimize premature optimization]", also von voreiliger Optimierung ohne experimentelle Untersuchung der wirklichen Laufzeiten, was laut Knuth "the root of all evil" ist. Der Python-Profiler wird in [http://docs.python.org/lib/profile.html Kapitel 25] der Python-Dokumentation beschrieben.
# Man kann dann versuchen, die kritischen Programmteile zu optimieren.
# Falls der Laufzeitgewinn durch Optimierung zu gering ist, muss man einen prinzipiell schnelleren Algorithmus verwenden, falls es einen gibt.

Einige wichtige Techniken der Programmoptimierung sollen hier erwähnt werden. Wenn man einen optimierenden Compiler verwendet, werden einige Optimierungen automatisch ausgeführt [http://en.wikipedia.org/wiki/Compiler_optimization]. In Python trifft dies jedoch nicht zu. Um den Sinn einiger Optimierungen zu verstehen, benötigt man Grundkenntnisse der Computerarchitektur.

;Elimination von redundantem Code: Es ist offensichtlich überflüssig, dasselbe Ergebnis mehrmals zu berechnen, wenn es auch zwischengespeichert werden könnte. Diese Optimierung wird von vielen automatischen Optimierern unterstützt und kommt im wesentlichen in zwei Ausprägungen vor:
:; common subexpression elimination: In mathematischen Ausdrücken wird ein Teilergebnis häufig mehrmals benötigt. Man betrachte z.B. die Lösung der quadratischen Gleichung <math>x^2+p\,x+q</math>:
x1 = - p / 2.0 + sqrt(p*p/4.0 - q)
x2 = - p / 2.0 - sqrt(p*p/4.0 - q)
::Die mehrmalige Berechnung von Teilausdrücken wird vermieden, wenn man stattdessen schreibt:
p2 = - p / 2.0
r = sqrt(p2*p2 - q)
x1 = p2 + r
x2 = p2 - r
:; loop invariant elimination: Wenn ein Teilausdruck sich in einer Schleife nicht ändert, muss man ihn nicht bei jedem Schleifendurchlauf neu berechnen, sondern kann dies einmal vor Beginn der Schleife tun. Ein typisches Beispiel hierfür ist die Adressierung von Matrizen, die als 1-dimensionales Array gespeichert sind. Angenommen, wir speichern eine NxN Matrix <tt>m</tt> in einem Array <tt>a</tt> der Größe N2, so dass das Matrixelement <tt>mij</tt> durch <tt>a[i + j*M]</tt> indexiert wird. Wir betrachten die Aufgabe, eine Einheitsmatrix zu initialisieren. Ein nicht optimierter Algorithmus dafür lautet:
for j in range(N):
for i in range(N):
if i == j:
a[i + j*N] = 1.0
else:
a[i + j*N] = 0.0
::Der Ausdruck <tt>j*N</tt> wird hier in jedem Schleifendurchlauf erneut berechnet, obwohl sich <tt>j</tt> in der inneren Schleife gar nicht verändert. Man kann deshalb optimieren zu:
for j in range(N):
jN = j*N
for i in range(N):
if i == j:
a[i + jN] = 1.0
else:
a[i + jN] = 0.0
;Vereinfachung der inneren Schleife: Generell sollte man sich bei der Optimierung auf die innere Schleife eines Algorithmus konzentrieren, weil dieser Code aum häufigsten ausgeführt wird. Insbesondere sollte man die Anzahl der Befehle in der inneren Schleife so gering wie möglich halten und teure Befehle vermeiden. Früher waren vor allem Floating-Point Befehle teuer, die man oft durch die schnellere Integer-Arithmetik ersetzt hat, falls dies algorithmisch möglich war (diesen Rat findet man noch oft in der Literatur). Heute hat sich die Hardware so verbessert, dass im Allgemeinen nur noch die Floating-Point Division deutlich langsamer ist als die anderen Operatoren. Im obigen Beispiel der quadratischen Gleichung ist es daher sinnvoll, den Ausdruck
p2 = -p / 2.0
:durch
p2 = -0.5 * p
:zu ersetzen. Dadurch spart man das Negieren von <tt>p</tt>, da der Compiler direkt mit <tt>-0.5</tt> multipliziert, und man ersetzt eine Division durch eine Multiplikation.
;Ausnutzung der Prozessor-Pipeline: Moderne Prozessoren führen mehrere Befehle parallel aus. Dies ist möglich, weil jeder Befehl in mehrere Teilschritte zerlegt werden kann. Eine generische Unterteilung in vier Teilschritte ist z.B.:
:# Dekodieren des nächsten Befehls
:# Beschaffen der Daten, die der Befehl verwendet (aus Prozessorregistern, dem Cache, oder dem Hauptspeicher)
:# Ausführen des Befehls
:# Schreiben der Ergebnisse
:Man bezeichnet dies als die "[http://en.wikipedia.org/wiki/Instruction_pipeline instruction pipeline]" des Prozessors (heutige Prozessoren verwenden wesentlich feinere Unterteilungen). Prozessoren werden nun so gebaut, dass mehrere Befehle parallel, auf verschiedenen Ausführungsstufen ausgeführt werden. Wenn Befehl 1 also beim Schreiben der Ergebnisse angelangt ist, kann Befehl 2 die Hardware zum Ausführen des Befehls benutzen, während Befehl 3 seine Daten holt, und Befehl 4 soeben dekodiert wird. Unter bestimmten Bedingungen funktioniert diese Parallelverarbeitung jedoch nicht. Dies gibt Anlass zu Optimierungen:
:;Vermeiden unnötiger Typkonvertierungen: Der Prozessor verarbeitet Interger- und Floating-Point-Befehle in verschiedenen Pipelines, weil die Hardwareanforderungen sehr verschieden sind. Wird jetzt ein Ergebnis von Integer nach Floating-Point umgewandelt oder umgekehrt, muss die jeweils andere Pipeline warten, bis die erste Pipeline ihre Berechnung beendet. Es kann dann besser sein, Berechnungen in Floating-Point zu Ende zu führen, auch wenn sie semantisch eigentlich Integer-Berechnungen sind.
:;Reduzierung der Anzahl von Verzweigungen: Wenn der Code verzweigt (z.B. durch eine <tt>if</tt>- oder <tt>while</tt>-Anweisung), ist nicht klar, welcher Befehl nach der Verzweigung ausgeführt werden soll, bevor Stufe 3 der Pipiline die Verzweigungsbedingung ausgewertet hat. Bis dahin wären die ersten beiden Stufen der Pipeline unbenutzt. Moderne Prozessoren benutzen zwar ausgefeilte Heuristiken, um das Ergebnis der Bedingung vorherzusagen, und führen den hoffentlich richtigen Zweig des Codes spekulativ aus, aber dies funktioniert nicht immer. Man sollte deshalb generell die Anzahl der Verzweigungen minimieren. Als Nebeneffekt führt dies meist auch zu besser lesbarem, verständlicherem Code. Im Matrixbeispiel kann man
for j in range(N):
jN = j*N
for i in range(N):
if i == j:
a[i + jN] = 1.0
else:
a[i + jN] = 0.0
::durch
for j in range(N):
jN = j*N
for i in range(N):
a[i + jN] = 0.0
a[j + jN] = 1.0
ersetzen. Die Diagonalelemente <tt>a[j + jN]</tt> werden jetzt zwar zweimal initialisiert (in der Schleife auf Null, dann auf Eins), aber durch Elimination der <tt>if</tt>-Abfrage wird dies wahrscheinlich mehr als ausgeglichen, zumal dadurch die innere Schleife wesentlich vereinfacht wurde.
;Ausnutzen des Prozessor-Cache: Zugriffe auf den Hauptspeicher sind sehr langsam. Deshalb werden stets ganze Speicherseiten auf einmal in den [http://en.wikipedia.org/wiki/Cache Cache] des Prozessors geladen. Wenn unmittelbar nacheinander benutzte Daten auch im Speicher nahe beieinander liegen (sogenannte "[http://en.wikipedia.org/wiki/Locality_of_reference locality of reference]"), ist die Wahrscheinlichkeit groß, dass die als nächstes benötigten Daten bereits im Cache sind und damit schnell gelesen werden können. Bei vielen Algorithmen kann man die Implementation so umordnen, dass die locality of reference verbessert wird, was zu einer drastischen Beschleunigung führt. Im Matrix-Beispiel ist z.B. die Reihenfolge der Schleifen wichtig. Für konstanten Index <tt>j</tt> liegen die Indizes <tt>i</tt> im Speicher hintereinander. Deshalb ist es günstig, in der inneren Schleife über <tt>i</tt> zu iterieren:
for j in range(N):
jN = j*N
for i in range(N):
a[i + jN] = 0.0
a[j + jN] = 1.0
:Die umgekehrte Reihenfolge der Schleifen ist hingegen ungünstig
for i in range(N):
for j in range(N):
a[i + j*N] = 0.0
a[i + i*N] = 1.0
:Jetzt werden in der inneren Schleife stets N Datenelemente übersprungen. Besonders bei großem N muss man daher häufig den Cache neu füllen, was bei der ersten Implementation nicht notwendig war. (Ausserdem verliert man hier die Optimierung <tt>jN = j*N</tt>, die jetzt nicht mehr möglich ist.)

Als Faustregel kann man durch Optimierung eine Verdoppelung der Geschwindigkeit erreichen (in Ausnahmefällen auch mehr). Benötigt man stärkere Verbesserungen, muss man wohl oder übel einen besseren Algorithmus oder einen schnelleren Computer verwenden.

== Komplexität ==
Komplexitätsbetrachtungen ermöglichen den Vergleich der prinzipiellen Eigenschaften von Algorithmen unabhängig von einer Implementation, Umgebung etc.

Eine einfache Möglichkeit ist das Zählen der Aufrufe einer Schlüsseloperation. Beispiel Sortieren:
* Anzahl der Vergleiche
* Anzahl der Vertauschungen

=== Beispiel: Selection Sort ===

for i in range(len(a)-1):
max = i
for j in range(i+1, len(a)):
if a[j] < a[max]:
max = j
a[max], a[i] = a[i], a[max] # swap

*Anzahl der Vergleiche: Ein Vergleich in jedem Durchlauf der inneren Schleife. Es ergibt sich folgende Komplexität:
*:Ingesamt <math>\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1}1 = \frac{N}{2} (N-1) \!</math> Vergleiche.

*Anzahl der Vertauschungen (swaps): Eine Vertauschung pro Durchlauf der äußeren Schleife:
*:Insgesamt <math>N-1 \!</math> Vertauschungen

Die Komplexität wird durch die Operationen bestimmt, die am häufigsten ausgeführt werden, hier also die Anzahl der Vergleiche. Die Anzahl der Vertauschungen ist hingegen kein geeignetes Kriterium für die Komplexität von selection sort, weil der Aufwand in der inneren Schleife ignoriert würde.

=== Fallunterscheidung: Worst und Average Case ===

Die Komplexität ist in der Regel eine Funktion der Eingabegröße (Anzahl der Eingabebits, Anzahl der Eingabeelemente). Sie kann aber auch von der Art der Daten abhängen, nicht nur von der Menge, z.B. vorsortierte Daten bei Quicksort. Um von der Art der Daten unabhängig zu werden, kann man zwei Fälle der Komplexität unterscheiden:

* Komplexität im ungünstigsten Fall
*: Der ungünstigste Fall ist die Eingabe gegebener Länge, für die der Algorithmus am langsamsten ist. Der Nachteil dieser Methode besteht darin, dass dieser ungünstige Fall in der Praxis vielleicht gar nicht oder nur selten vorkommt, so dass sich der Algorithmus in Wirklichkeit besser verhält als man nach dieser Analyse erwarten würde. Beim Quicksort-Algorithmus mit zufälliger Wahl des Pivot-Elements müsste z.B. stets das kleinste oder größte Element des aktuellen Intervalls als Pivot-Element gewählt werden, was äußerst unwahrscheinlich ist.
* Komplexität im durchschnittlichen/typischen Fall
*: Der typische Fall ist die mittlere Komplexität des Algorithmus über alle möglichen Eingaben. Dazu muss man die Wahrscheinlichkeit jeder möglichen Eingabe kennen, und berechnet dann die mittlere Laufzeit über dieser Wahrscheinlichkeitsverteilung. Leider ist die Wahrscheinlichkeit der Eingaben oft nicht bekannt, so dass man geeignete Annahmen treffen muss. Bei Sortieralgorithmen können z.B. alle möglichen Permutationen des Eingabearrays als gleich wahrscheinlich angenommen werden, und der typische Fall ist dann die mittlere Komplexität über alle diese Eingaben. Oft hat man jedoch in der Praxis andere Wahrscheinlichkeitsverteilungen, z.B. sind die Daten oft "fast sortiert" (nur wenige Elemente sind an der falschen Stelle). Dann verhält sich der Algorithmus ebenfalls anders als vorhergesagt.

Wir beschränken uns in dieser Vorlesung auf die Komplexität im ungünstigseten Fall. '''Exakte''' Formeln für Komplexität sind aber auch dann schwer zu gewinnen, wie das folgende Beispiel zeigt:

=== Beispiele aus den Übungen (Gemessene Laufzeiten für Mergesort/Selectionsort) ===

* Mergesort: <math>\frac{0,977N\log N}{\log 2} + 0,267N-4.39 \!</math>
*: andere Lösung: <math>1140 N\log(N) - 1819N + 6413 \!</math>
* Selectionsort: <math>\frac{1}{2}N^2 - \frac{1}{2N} - 10^{-12} \!</math>
*: andere Lösung: <math>1275N^2 - 116003^N + 11111144 \!</math>

Aus diesen Formeln wird nicht offensichtlich, welcher Algorithmus besser ist.
Näherung: Betrachte nur '''sehr große Eingaben''' (meist sind alle Algorithmen schnell genug für kleine Eingaben). Dieses Vorgehen wird als '''Asymptotische Komplexität''' bezeichnet (N gegen unendlich).

=== Asymptotische Komplexität am Beispiel Polynom ===

Polynom: <math>a\,x^2+b\,x+c=p\!</math>

<math>x \!</math> sei die Eingabegröße, und wir betrachten die Entwicklung von <math>p \!</math> in Abhängigkeit von <math>x \!</math>.

* <math>x=0 \!</math>
*: <math>p=c \!</math>
* <math>x=1 \!</math>
*: <math>p=a+b+c \!</math>
* <math>x=1000 \!</math>
*: <math>p=1000000a+1000b+c \approx 1000000a\!</math>
* <math>x \to \infty \!</math>
*: <math>p \approx x^2a\!</math>

Für sehr große Eingaben verlieren also ''b'' und ''c'' immer mehr an Bedeutung, so dass am Ende nur noch ''a'' für die Komplexitätsbetrachtung wichtig ist.

== O-Notation ==
* Intuitiv: Für große N dominieren die am schnellsten wachsenden Terme.
* Formale Definition:
*; Asymptotische Komplexität: Für zwei Funktionen f(x) und g(x) definiert man
*::<math>f(x) \in \mathcal{O}(g(x))</math>
*:(sprich "f ist in O von g" oder "f ist von derselben Größenordnung wie g") genau dann wenn es eine Konstante <math>c>0</math> und ein Argument <math>x_0</math> gibt, so dass
*::<math>\forall x \ge x_0:\quad f(x) \le c\,g(x)</math>.
*:Die Menge <math>\mathcal{O}(g(x))</math> aller durch g(x) abschätzbaren Funktionen ist also formal definiert durch
*::<math>\mathcal{O}(g(x)) = \{ f(x)\ |\ \exists c>0: \forall x_0 \ge x: f(x) \le c\,g(x)\}</math>
:Die Idee hinter dieser Definition ist, dass g(x) eine wesentlich einfachere Funktion ist als f(x), die sich aber nach geeigneter Skalierung (Multiplikation mit c) und für große Argumente x im wesentlichen genauso wie f(x) verhält. Man kann deshalb in der Algorithmenanalyse f(x) durch g(x) ersetzen. <math>f(x) \in \mathcal{O}(g(x))</math> spielt für Funktionen eine ähnliche Rolle wie der Operator ≤ für Zahlen: Falls a ≤ b gilt, kann bei einer Abschätzung von oben ebenfalls a durch b ersetzt werden.
=== Ein einfaches Beispiel ===

[[Image:Sqsqrt.png]]

Rot = <math>x^2 \!</math>
Blau = <math>\sqrt{x} \!</math>

<math>\sqrt{x} \in \mathcal{O}(x^2)\!</math> weil <math>\sqrt{x} \le c\,x^2\!</math> für alle <math>x \ge x_0 = 1 \!</math> und <math>c = 1\!</math>, oder auch für <math>x \ge x_0 = 4 \!</math> und <math>c = 1/16</math> (die Wahl von c und x0 in der Definition von O(.) ist beliebig, solange die Bedingungen erfüllt sind).

=== Komplexität bei kleinen Eingaben ===

Algorithmus 1: <math>\mathcal{O}(N^2) \!</math> 
Algorithmus 2: <math>\mathcal{O}(N\log{N}) \!</math>

Algorithmus 2 ist schneller (von geringerer Komplexität) für große Eingaben, aber bei kleinen Eingaben (insbesondere, wenn der Algorithmus in einer Schleife immer wieder mit kleinen Eingaben aufgerufen wird) könnte Algorithmus 1 schneller sein, falls der in der <math>\mathcal{O}</math>-Notation verborgene konstante Faktor ''c'' bei Algorithmus 2 einen wesentlich größeren Wert hat als bei Algorithmus 1.

=== Eigenschaften der O-Notation (Rechenregeln) ===

# Transitiv:
#: <math>f(x) \in \mathcal{O}(g(x)) \land g(x) \in \mathcal{O}(h(x)) \to f(x) \in \mathcal{O}(h(x)) \!</math>
# Additiv:
#: <math>f(x) \in \mathcal{O}(h(x)) \land g(x) \in \mathcal{O}(h(x)) \to f(x) + g(x) \in \mathcal{O}(h(x)) \!</math>
# Für Monome gilt:
#: <math>x^k \in \mathcal{O}(x^k)) \land x^k \in \mathcal{O}(x^{k+j}), \forall j \ge 0 \!</math>
# Multiplikation mit einer Konstanten:
#: <math>f(x) \in \mathcal{O}(g(x)) \to c\,f(x) \in \mathcal{O}(g(x))\!</math>
#: andere Schreibweise:
#: <math>f(x) = c\,g(x) \to f(x) \in \mathcal{O}(g(x))\!</math>
# Folgerung aus 3. und 4. für Polynome:
#: <math>a_0+a_1\,x + ... + a_n\,x^n \in \mathcal{O}(x^n)\!</math>
#: Beispiel: <math>a\,x^2+b\,x+c \in \mathcal{O}(x^2)\!</math>
# Logarithmus:
#: <math>a, b \neq 1\!</math>
#: <math>\log_{a}{x} \in \mathcal{O}(\log_{b}{x})\!</math>
#: Die Basis des Logarithmus spielt also keine Rolle.
#: Beweis hierfür:
#:: <math>\log_{a}{x} = \frac{\log_{b}{x}}{\log_{b}{a}}\!</math>
#:: Mit <math>c = 1 / \log_{b}{a}\,</math> gilt: <math>\log_{a}{x} = c\,\log_{b}{x}\!</math>.
#:: Wird hier die (zweite) Regel für Multiplikation mit einer Konstanten angewendet, fällt der konstante Faktor weg, also <math>\log_{a}{x} \in \mathcal{O}(\log_{b}{x})\!</math>.
#: Insbesondere gilt auch <math>\log_{a}{x} \in \mathcal{O}(\log_{2}{x})\!</math>, es kann also immer der 2er Logarithmus verwendet werden.

== O-Kalkül ==

Das O-Kalkül definiert wichtige Vereinfachungsregeln for Ausdrücke in O-Notation:

# <math>f(x) \in \mathcal{O}(f(x))\!</math>
# <math>\mathcal{O}(\mathcal{O}(f(x))) \in \mathcal{O}(f(x))\!</math>
# <math>c\,\mathcal{O}(f(x)) \in \mathcal{O}(f(x))\,</math> für jede Konstante ''c''
# <math>\mathcal{O}(f(x))+c \in \mathcal{O}(f(x))\,</math> für jede Konstante ''c''
# Sequenzregel:
#: Wenn zwei nacheinander ausgeführte Programmteile die Komplexität <math>\mathcal{O}(f(x))</math> bzw. <math>\mathcal{O}(g(x))</math> haben, gilt für beide gemeinsam:
#: <math>\mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(f(x))</math> falls <math>g(x) \in \mathcal{O}(f(x))</math> bzw.
#: <math>\mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(g(x))\!</math> falls <math>f(x) \in \mathcal{O}(g(x))</math>.
#: Informell schreibt man auch: <math>\mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(max(f(x), g(x)))\!</math>
# Schachtelungsregel bzw. Aufrufregel:
#: Wenn in einer geschachtelten Schleife die äußere Schleife die Komplexität <math>\mathcal{O}(f(x))</math> hat, und die innere <math>\mathcal{O}(g(x))</math>, gilt für beide gemeinsam:
#: <math>\mathcal{O}(f(x)) * \mathcal{O}(g(x)) \in \mathcal{O}(f(x) * g(x))\!</math>.
#: Gleiches gilt wenn eine Funktion <math>\mathcal{O}(f(x))</math>-mal aufgerufen wird, und die Komplexität der Funktion selbst <math>\mathcal{O}(g(x))</math> ist.

=== O-Kalkül auf das Beispiel des Selectionsort angewandt ===
Selectionsort: Wir hatten gezeigt dass <math>f(N) = \frac{N^2}{2} - \frac{N}{2}</math>. Nach der Regel für Polynome vereinfacht sich dies zu <math>f(N) \in \mathcal{O}\left(\frac{N^2}{2}\right) \in \mathcal{O}(N^2)\!</math>.

Alternativ via Schachtelungsregel:
: Die äußere Schleife wird (''N''-1)-mal durchlaufen: <math>N-1 \in \mathcal{O}(N)</math>
: Die innere Schleife wird (''N-i''-1)-mal durchlaufen. Das sind im Mittel ''N''/2 Durchläufe: <math>N/2 \in \mathcal{O}(N)</math>
: Zusammen: <math>\mathcal{O}(N)*\mathcal{O}(N) \in \mathcal{O}(N^2)</math>

Nach beiden Vorgehensweisen kommen wir zur Schlussfolgerung, dass der Selectionsort die asymptotische Komplexität <math>\mathcal{O}(N^2)\!</math> besitzt.

=== Zusammenhang zwischen Komplexität und Laufzeit ===

Wenn eine Operation 1ms dauert, erreichen Algorithmen verschiedener Komplexität folgende Leistungen (wobei angenommen wird, dass der in der <math>\mathcal{O}</math>-Notation verborgene konstante Faktor immer etwa gleich 1 ist):

{| class="wikitable" style="text-align:left" cellpadding="7"
|+
|-
! Komplexität !! Operationen in 1s !! Operationen in 1min !! Operationen in 1h
|-
! <math>\mathcal{O}(N)</math>
| 1000 || 60.000 || 3.600.000
|-
! <math>\mathcal{O}(N\log_2{N})</math>
| 140 || 4895 || 204094
|-
! <math>\mathcal{O}(N^2)</math>
| 32 || 245 || 1898
|-
! <math>\mathcal{O}(N^3)</math>
| 10 || 39 || 153
|-
! <math>\mathcal{O}(2^N)</math>
| 10 || 16 || 21
|}

=== Exponentielle Komplexität ===
Der letzte Fall <math>\mathcal{O}(2^N)</math> ist von exponentieller Komplexität. Das bedeutet, dass eine Verdopplung des Aufwands nur bewirkt, dass die maximale Problemgröße um eine Konstante wächst. Algorithmen mit exponentieller (oder noch höherer) Komplexität werden deshalb als '''ineffizient''' bezeichnet. Algorithmen mit höchstens polynomieller Komplexität gelten hingegen als effizient.

In der Praxis sind allerdings auch polynomielle Algorithmen mit hohem Exponenten meist zu langsam. Als Faustregel kann man eine praktische Grenze von <math>\mathcal{O}(N^3)</math> ansehen. Bei einer Komplexität von <math>\mathcal{O}(N^3)</math> bewirkt ein verdoppelter Aufwand immer noch eine Steigerung der maximalen Problemgröße um den Faktor <math>\sqrt[3]{2}</math> (also eine ''multiplikative'' Vergrößerung um ca. 25%, statt nur einer additiven Vergrößerung wie bei exponentieller Komplexität).



(Vorlesung 8.5.)

==Beispiel: Gleitender Mittelwert (Running Average)==

Wir berechnen für ein gegebenes Array <tt>a</tt> einen gleitenden Mittelwert über <tt>k</tt> Elemente: 
::<math>r_i = \frac{1}{k} \sum_{j=i-k+1}^i a_j</math> 
Das heisst, für jedes <tt>i</tt> mitteln wir die letzten <tt>k</tt> Elemente von <tt>a</tt> und schreiben das Ergebnis in <tt>r[i]</tt>. Diese Operation ist z.B. bei Börsenkursen wichtig: Neben dem aktuellen Kurs für jeden Tag wird dort meist auch der gleitende Mittelwert der letzten 30 Tage sowie der letzten 200 Tage angegeben. In diesen Mittelwerten erkennt man besser die langfristige Tendenz, weil die täglichen Schwankungen herausgemittelt werden. Wir nehmen außerdem an, dass
* Array-Zugriff hat eine Komplexität von O(1)
* <math>k \ll N</math>, d.h. <math>N-k\approx N</math>.

Die beiden folgenden Algorithmen berechnen die Mittelwerte auf unterschiedliche Art. Der linke folgt der obigen Definition durch eine Summe, während der rechte inkrementell arbeitet: Man kann den Bereich der <tt>k</tt> letzten Werte als Fenster betrachten, das über das Array <tt>a</tt> geschoben wird. Schiebt man das Fenster ein Element weiter, fällt links ein Element heraus, und rechts kommt eins hinzu. Man muss also nicht jedes Mal die Summe neu berechnen, sondern kann den vorigen Wert aktualisieren. Wir werden sehen, dass dies Folgen für die Komplexität des Algorithmus hat.

{| border="1" cellspacing="0" cellpadding="2"
|-
! Schritte
! Version 1: O(N * k)
! Komplexität
! Version 2: O(N)
! Komplexität
|-
|
1.
|
<tt>r = [0] * len(a)</tt>
|
'''<center>O(N)</center>'''
|
<tt>r = [0] * len(a)</tt>
|
'''<center>O(N)</center>'''
|-
|
2.
|
<tt>if k > len(a):</tt>
|
'''<center>O(1)</center>'''
|
<tt>if k > len(a):</tt>
|
'''<center>O(1)</center>'''
|-
|
3.
|
:: <tt>raise RuntimeError ("k zu groß")</tt>
|

|
:: <tt>raise RuntimeError ("k zu groß")</tt>
|

|-
|
4.
|
<tt>for j in range(k, len(a)):</tt>
|
<center>O(N-k) = '''O(N)'''</center>
|
<tt>for i in range(k):</tt>
|
'''<center>O(k)</center>'''
|-
|
5.
|
:: <tt>for i in range(j-k+1, j+1):</tt>
|
'''<center>O(k)</center>'''
|
:: <tt>r[k] += a[i]</tt>
|
'''<center>O(1)</center>'''
|-
|
6.
|
:::: <tt>r[j] += a[i]</tt>
|
'''<center>O(1)</center>'''
|
<tt>for j in range(k+1, len(a)):</tt>
|
<center>O(N-k) = '''O(N)'''</center>
|-
|
7.
|
:: <tt>r[j] /= float(k)</tt>
|
'''<center>O(1)</center>'''
|
:: <tt>r[j] = (a[j] - a[j-k] + r[j-1])</tt>
|
'''<center>O(1)</center>'''
|-
|
8.
|
<tt>return r</tt>
|
'''<center>O(1)</center>'''
|
<tt>for j in range(len(a)):</tt>
|
'''<center>O(N)</center>'''
|-
|
9.
|

|

|
:: <tt>r[j] /= float(k)</tt>
|
'''<center>O(1)</center>'''
|-
|
10.
|

|

|
<tt>return r</tt>
|
'''<center>O(1)</center>'''
|}

Obwohl Version 2 mehr Zeilen benötigt, besitzt das Programm eine geringere Komplexität.

===Berechnung der Komplexität===

====Berechnung der Komplexität von Version 1====

(Wiederholung der Rechenregeln:siehe Vorlesung 7.5.)

Zuweisungen 
äußere Schleife = f(x) 
innere Schleife = g(x)

4. Schritt: for j in range(k, len(a)) = äußere Schleife 
:: f(x) = O(N)(siehe Tabelle)
5. Schritt: for i in range(j-k+1, j+1) = innere Schleife 
:: g(x) = O(k) 

Multiplikationsregel (für geschachtelte Schleifen): 
O(f(x)) * O(g(x)) ∈ O(f(x) * g(x)) 

Multiplikationsregel angewendet auf Version 1 
O(N) * O(k) ∈ O(N * k) 
Komplexität von Version 1 = O(N * k)

====Berechnung der Komplexität von Version2====

siehe Tabelle

Zuweisungen 

6.Schritt: for j in ange(k+1, len(a)): 
:: f1(x) = O(N)

8.Schritt: for j in range(len(a)): 
:: f2(x) = O(N)

4.Schritt: for i in range(k): 
:: g(x) = O(k)

Additionsregel (für nacheinander ausgeführte Programmteile): 
O(f(x) + g(x)) = O(f(x)) falls g(x) ∈ O(f(x)) 
O(f(x) + g(x)) ∈ O(g(x)) falls f(x) ∈ O(g(x)) 
oder kurz O(f(x) + g(x)) = O(max(f(x),g(x)))

Anwendung der Additionsregel auf Version 2 
O(f1(x)) + O(f2(x)) + O(g(x)) 
O(N) + O(N) +O(k) = O(N), weil O(k) ∈ O(N) [O(max(O(N),O(k)))] 
(da wir wissen O(k) < O(N): 
if k > len(a):
:: raise RuntimeError("k zu groß") 
Daraus folgt: 
→ k < len(a) → for-Schleifen die über k iterieren haben eine kleinere Komplexität als for-Schleifen die über len(a) iterieren)

Komplexität von Version 2 = O(N)

====Fazit====

Obwohl Version 2 mehr Schritte benötigt hat sie eine geringere Komplexität, da die for-Schleifen nicht wie bei Version 1 verschachtelt/untergeordnet sind. Bei verschachtelten for-Schleifen muss die Multiplikationsregel angewendet → höhere Komplexität

Die gerade berechnete Komplexität gilt nur unter der Annahme, dass Array-Zugriffe eine Komplexität von O(1) besitzen

{| border="1" cellspacing="0" cellpadding="5"
|Allgemein:
Algorithmen-Analysen beruhen auf der Annahme, dass Zugriff auf die Daten optimal schnell sind, dass heißt dass die geeigneteste Datenstruktur verwendetet wird. → Ansonsten: Komplexitätsverschlechterung!
|}

===Beispiel für eine Verschlechterung der Komplexität durch Verwendung einer nicht optimalen Datenstruktur===

Beispiel: Verwende eine verkettete Liste anstalle eines Arrays. Um auf das j-te Element der Liste zuzugreifen, muss die Liste bis dahin durchlaufen werden

{| border="1" cellspacing="0" cellpadding="5" align="left"
!Implementation von L[j] für verkettete Liste
!Komplexität
|-
|
: <tt>r = L.head</tt>
|
O(1)
|-
|
<tt>while j > 0:</tt>
|
O(j)
|-
|
:: <tt>r = r.next</tt>
|
O(1)
|-
|
:: <tt>j -= 1</tt>
|
O(1)
|-
|
<tt>return r.data</tt>
|
O(1)
|}

'''<math> \Bigg\rbrace </math> O(j)''' 
r[j] = r[j] + a[i] '''→''' O(1) → O(N), falls a[i]= O[N]

====Fazit:====
Wegen der Schleife hat der Array-artige Zugriff bei einer verketteten Liste eine Komplexität von O(N). 
Würden wir in unserem running Average-Beispiel(siehe oben) auf eine verkettete Liste zugreifen hätten wir anstatt O(1) eine Komplexität von O(N) für den Zugriff auf unser Array.

Beispiel: Running-Average mit verketteter Liste

{| border="1" cellspacing="0" cellpadding="5"
! Schritte
! Version 1 mit verketteter Liste: O(N2 * k)
! Komplexität
|-
|
1.
|
<tt></tt>
|
'''<center>O(N)</center>'''
|-
|
2.
|
<tt>if k > len(a):</tt>
|
'''<center>O(1)</center>'''
|-
|
3.
|
:: <tt>raise RuntimeError ("k zu groß")</tt>
|

|-
|
4.
|
<tt>for j in range(k, len(a)):</tt>
|
<center>O(N-k) = '''O(N)'''</center>
|-
|
5.
|
:: <tt>for i in range(j-k+1, j+1):</tt>
|
'''<center>O(k)</center>'''
|-
|
6.
|
:::: <tt>r[j] += a[i]</tt>
|
'''<center>O(i) = '''O(N)'''</center>'''
|-
|
7.
|
:: <tt>r[j] /= float(k)</tt>
|
'''<center>O(1)</center>'''
|-
|
8.
|
<tt>return r</tt>
|
'''<center>O(1)</center>'''
|-
|}

Die Änderung gegenüber der ursprünglichen Version ist in Zeile 6. Der Zugriff <tt>a[i]</tt> erfolgt jetzt auf eine Liste, nicht auf ein Array. Aufgrund der obigen Implementation dieses Zugriffs verbirgt sich dahinter ''eine weitere Schleife''. Das heisst, wir haben jetzt '''drei''' geschachtelte Schleifen.
Zuweisungen 
äußere Schleife = f2(x) 
innere Schleife = g(x)

verkettete Liste 
:: f1(x) = O(N)
4. Schritt: for j in range(k, len(a)) = äußere Schleife 
:: f2(x) = O(N)(siehe Tabelle)
5. Schritt: for i in range(j-k+1, j+1) = innere Schleife 
:: g(x) = O(k) 

Multiplikationsregel ohne Konstante: 
O(f(x) * O(g(x)) ∈ O(f(x) * g(x)) 

Multiplikationsregel angewendet auf Version 1 mit einer verketteten Liste 

O(N) * O(N) * O(k) ∈ O(N2 * k) 

Die Komplexität von Version 1 mit einer verketteten Liste wäre O(N2 * k)

'''→ Die richtige Datenstruktur ist wichtig, da es sonst zu einer Komplexitätsverschlechterung kommen kann!'''

Auf Version 2 unseres runningAverage-Beispiels hätte eine verkettete Liste allerdings keine Auswirkungen, da die Additionsregel bei der Komplexitätsberechnung angewendet würde und somit Version 2 immer noch eine Komplexität von O(N) hätte.

==Amortisierte Komplexität==

Bis jetzt wurde die Komplexität nur im schlechtesten Fall(Worst Case) betrachtet, die Komplexität im schlechtesten Fall schwankt jedoch. 
Die amortisierte Komplexität beschäftigt sich mit der Komplexität im durschnittlichen/typischen Fall(Average Case)

Zum weiter Lesen: [[http://de.wikipedia.org/wiki/Amortisierte_Laufzeitanalyse Wikipedia: Amortisierte Laufzeitanalyse]]

===Beispiel: Inkrementieren von Binärzahlen===

Frage: Was kostet eine Operation im Durchschnitt?

Annahme: Bei jeder Operation wird ein Gehalt vom Wert 1 bezahlt, dass dem Guthaben zugeschrieben wird, wenn die Kosten das Gehalt decken. 
:: Kosten <= Gehalt → es wird gespart
:: Kosten > Gehalt → Guthaben - Gehalt werden für die Kosten verbraucht

{| border="1" cellspacing="0" cellpadding="5" align="left"
!Schritte
!Zahlen
!Kosten
!Kosten + Sparen
!Guthaben
|-
|1.
|00001
|1
|'''2'''
|'''1'''
|-
|2.
|00010
|2
|'''2'''
|'''1'''
|-
|3.
|00011
|1
|'''2'''
|'''2'''
|-
|4.
|00100
|3
|'''2'''
|'''1'''
|-
|}

Die Kosten ergeben sich aus der Anzahl der Ziffern die von 1 nach 0, bzw. von 0 nach 1 verändert werden

Rechnung:

1. Schritt: Kosten: 1 <= Gehalt: 1 
:: → es wird gespart 

2. Schritt: Kosten: 2 > Gehalt: 1 
:: → es wird nicht gespart 
:: → Guthaben bleibt so wie es ist 

3. Schritt: Kosten: 1 <= Gehalt: 1 
:: → es wird gespart 

4. Schritt: Kosten: 3 > Gehalt: 1 
:: → Guthaben: 2 - Gehalt: 1 = 1 
:: → es wird eine 1 vom Guthaben genommen um die Kosten zu zahlen 

Zum weiter Lesen: [[http://de.wikipedia.org/wiki/Account-Methode Wikipedia Account-Methode]]

====Fazit====
Die amortisierte Komplexität beschäftigt sich mit dem Durchschnitt aller Operation im ungünstigsten Fall. Operationen mit hohen Kosten, die aber nur selten ausgeführt werden, fallen bei der amortisierten Komplexität nicht so ins Gewicht. Bei Algorithmen, die gelegentlich eine "teure" Operation benutzen, ansonsten jedoch "billigen" Operationen aufrufen, kann die amortisierte Komplexität niedriger sein also die Komplexität im schlechtesten (Einzel-)Fall.

In unserem Beispiel fällt der 4. Schritt bei den Kosten schlußendlich nicht so ins Gewicht, da wir die Kosten aus unserem Guthaben mitbezahlen können → tatsächliche Kosten = 3, Kosten + Sparen = 2 
:: → Der Algorithmus besitzt durch dieses Verfahren eine niedrigere Komplexität

==statisches Array==

Ein statisches Array hat eine feste Größe N und besitzt eine Komplexität von O(N). 
Wird das Array um ein Element erweitert, muss ein neues Array mit der Größe N+1 erzeugt werden. 

Anhängen eines weiteren Elements an ein statisches Array:

{| border="1" cellspacing="0" cellpadding="5" align="right"
!Schritte
|'''Array'''
(wie es aussehen könnte)
!Komplexität
|-
|<center>altes Array</center>
|<center>[0,1,2,3]</center>
|<center>-</center>
|-
|1. Array N+1
|<center>[None,None,None,None,None]</center>
|<center>O(N+1) = '''O(N)'''</center>
|-
|2. Kopieren
|<center>[0,1,2,3,None]</center>
|<center>'''O(N)'''</center>
|-
|3. append von "x"
|<center>[0,1,2,3,'x']</center>
|<center>'''O(1)'''</center>
|-
|}

altesArray = [0,1,2,3] 
altesArray.append('x')

1. Es wird ein neues Array der Größe N+1 erzeugt 
2. Die Daten aus dem alten Array werden in das neue Array mit der Länge N+1 kopiert 
(Die Operation besitzt nur eine Komplexität von O(N), wenn das Kopieren eines Elements eine Komplexität von O(1) besitzt) 
3. 'x' wird an die letzte Stelle des neuen Arrays geschrieben

Additionsregel: 
O(N) + O(N) + O(1) ∈ O(N), falls O(1) ∈ O(N) [O(max(O(N),O(1))] (Bedingung: N > 1)

==dynamisches Array==

Beim dynamischen Array werden mehr Speicherelemente reserviert als zur Zeit benötigt. Es gibt verschiedene Möglichkeiten wie ein dynamisches Array realisiert werden kann.

capacity = Anzahl der möglichen Elemente, die in das Array passen 
size = Anzahl der Elemente, die im Array gespeichert sind 
data = statisches Array der Größe "capacity" 
A

Beispiele für mögliche Vorgehensweisen eines dynamischen Arrays beim Zufügen eines neuen Elements: (size == capacity)
* Ein neues statisches Array der Größe size == capacity wird erzeugt
* capacity wird verdoppelt 
: → neue capacity = 2 * alte capacity
* capacity wird um einen Prozentsatz vergrößert 
: → neue capacity = alte capacity * c, c > 1
* ...

'''Folge:''' Das Hinzufügen eines neuen Elements in ein dynamisches Array ist amortisiert, die Operation besitzt eine Komplexität von O(1).

==Analyse des dynamischen Arrays==

Durchschnitt der Gesamtkosten für N-maliges append = <math>\frac{1}{N} \sum_{i = 1}^N Kosten(i)</math> 

Fall 1: Array ist nicht voll 
Es wird kein Umkopieren benötigt, da das Array noch nicht voll ist → size < capacity

Kosten: 1 
Potenzial vor append: Φi-1 = 2(i - 1) - capacity 
Potenzial nach append: Φi - capacity 

amortisierte Kosten = Kosteni + Φ(i) - Φ(i-1)
::::: = 1 + (2i - capacity) - [2(i - 1) - capacity]
::::: = 1 + 2i - capacity - 2i + 2 + capacity
::::: = 1 + <del>2i</del> - <del>capacity</del> - <del>2i</del> + 2 + <del>capacity</del>
::::: = 1 + 2
::::: = 3 = O(1) → konstant

Fall 2: Array ist voll 
Umkopieren wird nach i-tem append benötigt → size == capacity

Kosten: (i-1) + 1 
Potenzial vor append = Φi-1 = 2(i - 1) - capacity 
Potenzial nach append = Φi = 2i - 2 * capacity 
::::: = 2i - 2i , da capacity = i
::::: = 0
amortisierte Kosten = Kosteni + Φ(i) - Φ(i-1)
::::: = ((i - 1) + 1) + 0 - [2(i-1) - capacity]
::::: = i - 2i - 2 - capacity
::::: = <del>i</del> - <del>2</del>i - 2 - capacity
::::: = <del>i</del> - 2 - <del>capacity</del> , da capacity = i
::::: = 2 = O(1) → konstant

'''Damit wurde bewiesen, dass die Operation append beim dynamischen Array amortisiert ist → O(1)'''

{| border="1" cellspacing="0" cellpadding="5" align="left"
!Array 
(wie es aussehen könnte)
!size
!capacity
!Kosten 1.append
!Summe Kosten
!Durchschnittskosten
!Φi = 2 * size - capacity 
(i = size)
!Potenzialdifferenz 
Δ Φi = Φi - Φi-1
!amortisierte Kosteni 
= Kosteni + Δ Φi
|-
| <center>[None]</center>
| <center>0</center>
| <center>1</center>
| <center>-</center>
| <center>-</center>
| <center>-</center>
| <center>-1</center>
| <center>-</center>
| <center>-</center>
|-
| <center>[a]</center><center>Array ist voll!</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b]</center><center>Array ist voll!</center>
| <center>2</center>
| <center>2</center>
| <center>1 + 1</center>
| <center>3</center>
| <center>3/2</center>
| <center>2</center>
| <center>1</center>
| <center>3</center>
|-
| <center>[a,b,c,None]</center>
| <center>3</center>
| <center>4</center>
| <center>2 + 1</center>
| <center>6</center>
| <center>6/3</center>
| <center>2</center>
| <center>0</center>
| <center>3</center>
|-
| <center>[a,b,c,d]</center><center>Array ist voll!</center>
| <center>4</center>
| <center>4</center>
| <center>1</center>
| <center>7</center>
| <center>7/4</center>
| <center>4</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,None,None,None]</center>
| <center>5</center>
| <center>8</center>
| <center>4 + 1</center>
| <center>12</center>
| <center>12/5</center>
| <center>2</center>
| <center>-2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,None,None]</center>
| <center>6</center>
| <center>8</center>
| <center>1</center>
| <center>13</center>
| <center>13/6</center>
| <center>4</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,g,None]</center>
| <center>7</center>
| <center>8</center>
| <center>1</center>
| <center>14</center>
| <center>14/7</center>
| <center>6</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,g,h]</center><center>Array ist voll!</center>
| <center>8</center>
| <center>8</center>
| <center>1</center>
| <center>15</center>
| <center>15/8</center>
| <center>8</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,g,h,j,None,None,None, 
None,None,None,None,None,None]</center>
| <center>9</center>
| <center>16</center>
| <center>8 + 1</center>
| <center>24</center>
| <center>24/9</center>
| <center>2</center>
| <center>-6</center>
| <center>3</center>
|-

== Landau-Symbole ==

Um die asymptotische Komplexität verschiedener Algorithmen miteinander vergleichen zu können, verwendet man die sogenannten [http://de.wikipedia.org/wiki/Landau-Symbole Landau-Symbole]. Das wichtigste Landau-Symbol ist <math>\mathcal{O}</math>, mit dem man eine ''obere Schranke'' für die Komplexität angeben kann.

Schreibt man <math>f \in \Omega(g)</math>, so stellt dies eine asymptotische ''untere Schranke'' für die Funktion f dar.

Schließlich bedeutet <math>f \in \Theta(g)</math>, dass die Funktion f genauso schnell wie die Funktion g wächst, das heißt man hat eine asymptotisch ''scharfe Schranke'' für f. Hierzu muss sowohl <math>f\in\mathcal{O}(g)</math> als auch <math>g\in\mathcal{O}(f)</math> erfüllt sein.

Im nun folgenden soll auf die verschiedenen Landau-Symbole noch näher eingegeangen werden.

===<math>\mathcal{O}</math> - Notation===

<math>f \in \mathcal{O}(g)</math> ist eine Abschätzung der asymptotischen Komplexität der Funktion f von oben. Per Definition gilt <math>f(N) \in \mathcal{O}(g(N))</math> genau dann, falls eine Konstante

<math> c > 0 </math> existiert, so dass

<math> f(N) \le c \cdot g(N) </math> für <math> N \ge N_0 </math>

erfüllt ist.

Im Prinzip ist <math>f \in \mathcal{O}(g)</math> also ein <-Operator für Funktionen, analog zum <-Operator für Zahlen.

===<math>\Omega</math>- Notation===

<math>f \in \Omega(g) </math> schätzt die asymptotische Komplexität der Funktion f nach unten ab.

Formal kann man <math>f(N) \in \Omega(g(N)) </math> genau dann schreiben, falls es eine Konstante <math> c > 0 </math> gibt, so dass

<math> f(N) \ge c \cdot g(N) </math> für <math> N \ge N_0 </math>

gilt.
Man verwendet diese Notation also um abzuschätzen, wie groß der Aufwand (die Komplexität) für einen bestimmten Algorithmus ''mindestens'' ist und nicht ''höchstens'', was man mit der <math>\mathcal{O}</math> - Notation ausdrücken würde.

Ein praktisches Beispiel für eine Anwendung der <math>\Omega</math>- Notation wäre die Fragestellung, ob es ''prinzipiell'' einen besseren Algorithmus für ein bestimmtes Problem gibt. Wie später in der Vorlesung gezeigt werden wird, ist das Sortieren eines Arrays beispielsweise immer mindestens von der Komplexität <math> \Omega(N\cdot \ln N) </math>, was konkret bedeutet, dass kein Sortieralgorithmus jemals eine geringere Komplexität als Merge-Sort beispielsweise haben wird. Natürlich kann man den entsprechenden Sortieralgorithmus, also Merge-Sort zum Beispiel, unter Umständen noch optimieren, aber die Komplexität wird erhalten bleiben. Mit diesem Wissen kann man sich viel (vergebene) Arbeit sparen.

===<math>\Theta</math>- Notation===

<math>f(N) \in \Theta(g(N))</math> ist eine scharfe Abschätzung der asymptotischen Komplexität einer Funktion f.

Damit dies gilt, muss <math>f(N) \in \mathcal{O}(g(N))</math> und ''gleichzeitig'' <math>f(N) \in \Omega(g(N))</math> erfüllt sein.

Dies ist natürlich auch die beste Abschätzung der asymptotischen Komplexität einer Funktion f. Formal bedeutet <math>f(N) \in \Theta(g(N))</math> dass es zwei Konstanten <math> c_1 </math> und <math> c_2 </math>, beide größer als Null, gibt, so dass für alle <math> N \geq N_0 </math> gilt:

<math> c_1 \cdot g(N) \leq f(N) \leq c_2 \cdot g(N) </math>.

In der Praxis verwendet man jedoch statt der <math>\Theta</math>- Notation oft die <math>\mathcal{O}</math> - Notation.

== Komplexitätsvergleich zweier Algorithmen ==

In diesem Abschnitt wollen wir der Frage nachgehen, wie ein formaler Beweis für die Behauptung <math> f(N) \in \mathcal{O}(g(N))</math> geschehen kann. Hierbei werden zwei Beweismethoden vorgestellt werden, und zwar der '''Beweis über die Definition der Komplexität''' sowie der '''Beweis durch Dividieren'''.
===Beweis über die Definition der asymptotischen Komplexität===

Die Definition der asymptotischen Komplexität <math>f(N) \in \mathcal{O}(g(N))</math> war:

Es gibt eine Konstante <math> c > 0 </math>, so dass <math> f(N) \le c \cdot g(N) </math> für <math> N \ge N_0 </math> erfüllt ist.

Um also die die asymptotische Komplexität <math>f(N) \in \mathcal{O}(g(N))</math> zu beweisen, muss man die oben erwähnten Konstanten c und <math> N_0 </math> finden, so dass

<math> f(N) \leq g(N) </math> für alle <math> N \ge N_0 </math> erfüllt ist.

Dies geschieht zweckmäßigerweise mit dem Beweisprinzip der ''vollständigen Induktion''. Hierbei ist zu zeigen, dass
# <math> f(N_0) \leq g(N_0) </math> für die eine zu bestimmende Konstante <math> N_0 </math> gilt (''Induktionsanfang'') und
# falls <math> f(N) \leq g(N) </math>, dann auch <math> f(N+1) \leq g(N+1) </math> (''Induktionsschritt'') gilt.

===Beweis durch Dividieren===

Hierbei wählt man eine Konstante c und zeigt, dass <math> \lim_{N \rightarrow \infty} \frac{f(N)}{c \cdot g(N)} \leq 1 </math> gilt. Man kann dies als eine alternative Definition von Komplexität ansehen.

Als Beispiel betrachten wir die beiden Funktionen <math> f(N) = N \,\lg N </math> und <math> g(N) = N^2 </math> und wollen zeigen, dass <math>f(N) \in \mathcal{O}(g(N))</math> gilt.

Als Konstante c wählen wir <math> c = 1 </math>

<math> \lim_{N \rightarrow \infty} \frac{f(N)}{g(N)} = \lim_{N \rightarrow \infty} \frac{\lg N}{N} = \frac{\infty}{\infty} </math>

Unbestimmte Ausdrücke der Form
<math> \lim_{x \rightarrow x_0} \frac{f(x)}{g(x)} </math>,
in denen sowohl <math> f(x) </math> als auch <math> g(x) </math> mit <math> x \rightarrow x_0 </math> gegen Null oder gegen Unendlich streben, kann man manchmal mit den Regeln von [http://de.wikipedia.org/wiki/L%27Hospital%27sche_Regel ''l'Hospital''] berechnen. Danach darf man die Funktionen f und g zur Berechnung des unbestimmten Ausdrucks durch ihre k-ten Ableitungen ersetzen:

<math> \lim_{x \rightarrow x_0} \frac{f(x)}{g(x)} = \lim_{x \rightarrow x_0} \frac{f^{(k)}(x)}{g^{(k)}(x)} </math>

In unserem Fall verwenden wir die erste Ableitung und erhalten:
<math> \lim_{N \rightarrow \infty} \frac{f'(x)}{g'(x)} = \lim_{N \rightarrow \infty} \frac{1/N}{1} \rightarrow 0 </math>

Damit wurde <math>f(N) \in \mathcal{O}(g(N))</math>, also <math>N \lg N \in \mathcal{O}(N^2)</math> gezeigt.

Man beachte hierbei, dass <math>N \lg N \in \mathcal{O}(N^2)</math> keine enge Grenze für die Komplexität von <math>N \,\lg N</math> darstellt, da der Grenzwert <math> \lim_{N \rightarrow \infty} \frac{f'(x)}{g'(x)}\, </math> gegen 0 und nicht gegen eine von Null verschiedene Konstante strebt. In diesem Fall haben wir also die Komplexität von <math>N \cdot \lg N </math> also nur nach oben abschätzen können.

Effizienz

2008-05-19T20:18:19Z

Friedrich: /* Beweis durch Dividieren */

Bei der Diskussion von Effizienz müssen wir zwischen der Laufzeit eines Algorithmus auf einem bestimmten System und seiner prinzipiellen Leistungsfähigkeit (Algorithmenkomplexität) unterscheiden. Der Benutzer ist natürlich vor allem an der Laufzeit interessiert, denn diese bestimmt letztendlich seine Arbeitsproduktivität. Ein Softwaredesigner hingegen muss eine Implementation wählen, die auf verschiedenen Systemen und in verschiedenen Anwendungen schnell ist. Für ihn sind daher auch Aussagen zur Algorithmenkomplexität sehr wichtig, um den am besten geeigneten Algorithmus auszuwählen.

== Laufzeit ==

Aus Anwendersicht ist ein Algorithmus effizient, wenn er die in der Spezifikation verlangten Laufzeitgrenzen einhält. Ein Algorithmus muss also nicht immer so schnell wie möglich sein, sondern so schnell wie nötig. Dies führt in verschiedenen Anwendungen zu ganz unterschiedliche Laufzeitanforderungen:

* Berechnen des nächsten Steuerkommandos für eine Maschine: ca. 1/1000s
* Berechnen des nächsten Bildes für eine Videopräsentation (z.B. Dekompression von MPEG-kodierten Bildern): ca. 1/25s
: Geringere Bildraten führen zu ruckeligen Filmen.
* Sichtbare Antwort auf ein interaktives Kommando (z.B. Mausklick): ca. 1/2s
: Wird diese Antwortzeit überschritten, vermuten viele Benutzer, dass der Mausklick nicht funktioniert hat, und klicken nochmals, mit eventuell fatalen Folgen. Wenn ein Algorithmus notwendigerweise länger dauert als 1/2s, sollte ein Fortschrittsbalken angezeigt werden.
* Wettervorhersage: muss spätestens am Vorabend des vorhergesagten Tages beendet sein

===Laufzeitvergleich===

Da die Laufzeit für den Benutzer ein so wichtiges Kriterium ist, werden häufig Laufzeitvergleiche durchgeführt. Deren Ergebnisse hängen allerdings von vielen Faktoren ab, die möglicherweise nicht kontrollierbar sind:
* Geschwindigkeit und Anzahl der Prozessoren
* Auslastung des Systems
* Größe des Hauptspeichers und Cache, Geschwindigkeit des Datenbus
* Qualität des Compilers/Optimierers (ist der Compiler für die spezielle Prozessor-Architektur optimiert?)
* Geschick des Programmierers
* Daten (Beispiel Quicksort: Best case und worst case [vorsortierter Input] stark unterschiedlich)
All diese Faktoren sind untereinander abhängig. Laufzeitvergleiche sind daher mit Vorsicht zu interpretieren.
Generell sollten bei Vergleichen möglichst wenige Parameter verändert werden, z.B.
* gleiches Programm (gleiche Kompilierung), gleiche Daten, andere Prozessoren
oder
* gleiche CPU, Daten, andere Programme (Vergleich von Algorithmen)
Zur Verbesserung der Vergleichbarkeit gibt es standardisierte [http://en.wikipedia.org/wiki/Benchmark_(computing) Benchmarks], die bestimmte Aspekte eines Systems unter möglichst realitätsnahen Bedingungen testen. Generell gilt aber: Durch Laufzeitmessung ist schwer festzustellen, ob ein Algorithmus ''prinzipiell'' besser ist als ein anderer. Dafür ist die Analyse der [[Effizienz#Komplexität|Algorithmenkomplexität]] notwendig.

===Optimierung===

Wenn sich herausstellt, dass ein bereits implementierter Algorithmus zu langsam läuft, geht man wie folgt vor:

# Man verwendet einen [http://en.wikipedia.org/wiki/Performance_analysis Profiler], um zunächst den Flaschenhals zu bestimmen. Ein Profiler ist ein Hilfsprogramm, dass während der Ausführung eines Programms misst, wieviel Zeit in jeder Funktion und Unterfunktion verbraucht wird. Dadurch kann man herausfinden, welcher Teil des Algorithmus überhaupt Probleme bereitet. Donald Knuth gibt z.B. als Erfahrungswert an, dass Programme während des größten Teils ihrer Laufzeit nur 3% des Quellcodes (natürlich mehrmals wiederholt) ausführen [http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf]. Es ist sehr wichtig, diese 3% experimentell zu bestimmen, weil die Erfahrung zeigt, dass man beim Erraten der kritischen Programmteile oft falsch liegt. Man spricht dann von "[http://en.wikipedia.org/wiki/Optimization_%28computer_science%29#When_to_optimize premature optimization]", also von voreiliger Optimierung ohne experimentelle Untersuchung der wirklichen Laufzeiten, was laut Knuth "the root of all evil" ist. Der Python-Profiler wird in [http://docs.python.org/lib/profile.html Kapitel 25] der Python-Dokumentation beschrieben.
# Man kann dann versuchen, die kritischen Programmteile zu optimieren.
# Falls der Laufzeitgewinn durch Optimierung zu gering ist, muss man einen prinzipiell schnelleren Algorithmus verwenden, falls es einen gibt.

Einige wichtige Techniken der Programmoptimierung sollen hier erwähnt werden. Wenn man einen optimierenden Compiler verwendet, werden einige Optimierungen automatisch ausgeführt [http://en.wikipedia.org/wiki/Compiler_optimization]. In Python trifft dies jedoch nicht zu. Um den Sinn einiger Optimierungen zu verstehen, benötigt man Grundkenntnisse der Computerarchitektur.

;Elimination von redundantem Code: Es ist offensichtlich überflüssig, dasselbe Ergebnis mehrmals zu berechnen, wenn es auch zwischengespeichert werden könnte. Diese Optimierung wird von vielen automatischen Optimierern unterstützt und kommt im wesentlichen in zwei Ausprägungen vor:
:; common subexpression elimination: In mathematischen Ausdrücken wird ein Teilergebnis häufig mehrmals benötigt. Man betrachte z.B. die Lösung der quadratischen Gleichung <math>x^2+p\,x+q</math>:
x1 = - p / 2.0 + sqrt(p*p/4.0 - q)
x2 = - p / 2.0 - sqrt(p*p/4.0 - q)
::Die mehrmalige Berechnung von Teilausdrücken wird vermieden, wenn man stattdessen schreibt:
p2 = - p / 2.0
r = sqrt(p2*p2 - q)
x1 = p2 + r
x2 = p2 - r
:; loop invariant elimination: Wenn ein Teilausdruck sich in einer Schleife nicht ändert, muss man ihn nicht bei jedem Schleifendurchlauf neu berechnen, sondern kann dies einmal vor Beginn der Schleife tun. Ein typisches Beispiel hierfür ist die Adressierung von Matrizen, die als 1-dimensionales Array gespeichert sind. Angenommen, wir speichern eine NxN Matrix <tt>m</tt> in einem Array <tt>a</tt> der Größe N2, so dass das Matrixelement <tt>mij</tt> durch <tt>a[i + j*M]</tt> indexiert wird. Wir betrachten die Aufgabe, eine Einheitsmatrix zu initialisieren. Ein nicht optimierter Algorithmus dafür lautet:
for j in range(N):
for i in range(N):
if i == j:
a[i + j*N] = 1.0
else:
a[i + j*N] = 0.0
::Der Ausdruck <tt>j*N</tt> wird hier in jedem Schleifendurchlauf erneut berechnet, obwohl sich <tt>j</tt> in der inneren Schleife gar nicht verändert. Man kann deshalb optimieren zu:
for j in range(N):
jN = j*N
for i in range(N):
if i == j:
a[i + jN] = 1.0
else:
a[i + jN] = 0.0
;Vereinfachung der inneren Schleife: Generell sollte man sich bei der Optimierung auf die innere Schleife eines Algorithmus konzentrieren, weil dieser Code aum häufigsten ausgeführt wird. Insbesondere sollte man die Anzahl der Befehle in der inneren Schleife so gering wie möglich halten und teure Befehle vermeiden. Früher waren vor allem Floating-Point Befehle teuer, die man oft durch die schnellere Integer-Arithmetik ersetzt hat, falls dies algorithmisch möglich war (diesen Rat findet man noch oft in der Literatur). Heute hat sich die Hardware so verbessert, dass im Allgemeinen nur noch die Floating-Point Division deutlich langsamer ist als die anderen Operatoren. Im obigen Beispiel der quadratischen Gleichung ist es daher sinnvoll, den Ausdruck
p2 = -p / 2.0
:durch
p2 = -0.5 * p
:zu ersetzen. Dadurch spart man das Negieren von <tt>p</tt>, da der Compiler direkt mit <tt>-0.5</tt> multipliziert, und man ersetzt eine Division durch eine Multiplikation.
;Ausnutzung der Prozessor-Pipeline: Moderne Prozessoren führen mehrere Befehle parallel aus. Dies ist möglich, weil jeder Befehl in mehrere Teilschritte zerlegt werden kann. Eine generische Unterteilung in vier Teilschritte ist z.B.:
:# Dekodieren des nächsten Befehls
:# Beschaffen der Daten, die der Befehl verwendet (aus Prozessorregistern, dem Cache, oder dem Hauptspeicher)
:# Ausführen des Befehls
:# Schreiben der Ergebnisse
:Man bezeichnet dies als die "[http://en.wikipedia.org/wiki/Instruction_pipeline instruction pipeline]" des Prozessors (heutige Prozessoren verwenden wesentlich feinere Unterteilungen). Prozessoren werden nun so gebaut, dass mehrere Befehle parallel, auf verschiedenen Ausführungsstufen ausgeführt werden. Wenn Befehl 1 also beim Schreiben der Ergebnisse angelangt ist, kann Befehl 2 die Hardware zum Ausführen des Befehls benutzen, während Befehl 3 seine Daten holt, und Befehl 4 soeben dekodiert wird. Unter bestimmten Bedingungen funktioniert diese Parallelverarbeitung jedoch nicht. Dies gibt Anlass zu Optimierungen:
:;Vermeiden unnötiger Typkonvertierungen: Der Prozessor verarbeitet Interger- und Floating-Point-Befehle in verschiedenen Pipelines, weil die Hardwareanforderungen sehr verschieden sind. Wird jetzt ein Ergebnis von Integer nach Floating-Point umgewandelt oder umgekehrt, muss die jeweils andere Pipeline warten, bis die erste Pipeline ihre Berechnung beendet. Es kann dann besser sein, Berechnungen in Floating-Point zu Ende zu führen, auch wenn sie semantisch eigentlich Integer-Berechnungen sind.
:;Reduzierung der Anzahl von Verzweigungen: Wenn der Code verzweigt (z.B. durch eine <tt>if</tt>- oder <tt>while</tt>-Anweisung), ist nicht klar, welcher Befehl nach der Verzweigung ausgeführt werden soll, bevor Stufe 3 der Pipiline die Verzweigungsbedingung ausgewertet hat. Bis dahin wären die ersten beiden Stufen der Pipeline unbenutzt. Moderne Prozessoren benutzen zwar ausgefeilte Heuristiken, um das Ergebnis der Bedingung vorherzusagen, und führen den hoffentlich richtigen Zweig des Codes spekulativ aus, aber dies funktioniert nicht immer. Man sollte deshalb generell die Anzahl der Verzweigungen minimieren. Als Nebeneffekt führt dies meist auch zu besser lesbarem, verständlicherem Code. Im Matrixbeispiel kann man
for j in range(N):
jN = j*N
for i in range(N):
if i == j:
a[i + jN] = 1.0
else:
a[i + jN] = 0.0
::durch
for j in range(N):
jN = j*N
for i in range(N):
a[i + jN] = 0.0
a[j + jN] = 1.0
ersetzen. Die Diagonalelemente <tt>a[j + jN]</tt> werden jetzt zwar zweimal initialisiert (in der Schleife auf Null, dann auf Eins), aber durch Elimination der <tt>if</tt>-Abfrage wird dies wahrscheinlich mehr als ausgeglichen, zumal dadurch die innere Schleife wesentlich vereinfacht wurde.
;Ausnutzen des Prozessor-Cache: Zugriffe auf den Hauptspeicher sind sehr langsam. Deshalb werden stets ganze Speicherseiten auf einmal in den [http://en.wikipedia.org/wiki/Cache Cache] des Prozessors geladen. Wenn unmittelbar nacheinander benutzte Daten auch im Speicher nahe beieinander liegen (sogenannte "[http://en.wikipedia.org/wiki/Locality_of_reference locality of reference]"), ist die Wahrscheinlichkeit groß, dass die als nächstes benötigten Daten bereits im Cache sind und damit schnell gelesen werden können. Bei vielen Algorithmen kann man die Implementation so umordnen, dass die locality of reference verbessert wird, was zu einer drastischen Beschleunigung führt. Im Matrix-Beispiel ist z.B. die Reihenfolge der Schleifen wichtig. Für konstanten Index <tt>j</tt> liegen die Indizes <tt>i</tt> im Speicher hintereinander. Deshalb ist es günstig, in der inneren Schleife über <tt>i</tt> zu iterieren:
for j in range(N):
jN = j*N
for i in range(N):
a[i + jN] = 0.0
a[j + jN] = 1.0
:Die umgekehrte Reihenfolge der Schleifen ist hingegen ungünstig
for i in range(N):
for j in range(N):
a[i + j*N] = 0.0
a[i + i*N] = 1.0
:Jetzt werden in der inneren Schleife stets N Datenelemente übersprungen. Besonders bei großem N muss man daher häufig den Cache neu füllen, was bei der ersten Implementation nicht notwendig war. (Ausserdem verliert man hier die Optimierung <tt>jN = j*N</tt>, die jetzt nicht mehr möglich ist.)

Als Faustregel kann man durch Optimierung eine Verdoppelung der Geschwindigkeit erreichen (in Ausnahmefällen auch mehr). Benötigt man stärkere Verbesserungen, muss man wohl oder übel einen besseren Algorithmus oder einen schnelleren Computer verwenden.

== Komplexität ==
Komplexitätsbetrachtungen ermöglichen den Vergleich der prinzipiellen Eigenschaften von Algorithmen unabhängig von einer Implementation, Umgebung etc.

Eine einfache Möglichkeit ist das Zählen der Aufrufe einer Schlüsseloperation. Beispiel Sortieren:
* Anzahl der Vergleiche
* Anzahl der Vertauschungen

=== Beispiel: Selection Sort ===

for i in range(len(a)-1):
max = i
for j in range(i+1, len(a)):
if a[j] < a[max]:
max = j
a[max], a[i] = a[i], a[max] # swap

*Anzahl der Vergleiche: Ein Vergleich in jedem Durchlauf der inneren Schleife. Es ergibt sich folgende Komplexität:
*:Ingesamt <math>\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1}1 = \frac{N}{2} (N-1) \!</math> Vergleiche.

*Anzahl der Vertauschungen (swaps): Eine Vertauschung pro Durchlauf der äußeren Schleife:
*:Insgesamt <math>N-1 \!</math> Vertauschungen

Die Komplexität wird durch die Operationen bestimmt, die am häufigsten ausgeführt werden, hier also die Anzahl der Vergleiche. Die Anzahl der Vertauschungen ist hingegen kein geeignetes Kriterium für die Komplexität von selection sort, weil der Aufwand in der inneren Schleife ignoriert würde.

=== Fallunterscheidung: Worst und Average Case ===

Die Komplexität ist in der Regel eine Funktion der Eingabegröße (Anzahl der Eingabebits, Anzahl der Eingabeelemente). Sie kann aber auch von der Art der Daten abhängen, nicht nur von der Menge, z.B. vorsortierte Daten bei Quicksort. Um von der Art der Daten unabhängig zu werden, kann man zwei Fälle der Komplexität unterscheiden:

* Komplexität im ungünstigsten Fall
*: Der ungünstigste Fall ist die Eingabe gegebener Länge, für die der Algorithmus am langsamsten ist. Der Nachteil dieser Methode besteht darin, dass dieser ungünstige Fall in der Praxis vielleicht gar nicht oder nur selten vorkommt, so dass sich der Algorithmus in Wirklichkeit besser verhält als man nach dieser Analyse erwarten würde. Beim Quicksort-Algorithmus mit zufälliger Wahl des Pivot-Elements müsste z.B. stets das kleinste oder größte Element des aktuellen Intervalls als Pivot-Element gewählt werden, was äußerst unwahrscheinlich ist.
* Komplexität im durchschnittlichen/typischen Fall
*: Der typische Fall ist die mittlere Komplexität des Algorithmus über alle möglichen Eingaben. Dazu muss man die Wahrscheinlichkeit jeder möglichen Eingabe kennen, und berechnet dann die mittlere Laufzeit über dieser Wahrscheinlichkeitsverteilung. Leider ist die Wahrscheinlichkeit der Eingaben oft nicht bekannt, so dass man geeignete Annahmen treffen muss. Bei Sortieralgorithmen können z.B. alle möglichen Permutationen des Eingabearrays als gleich wahrscheinlich angenommen werden, und der typische Fall ist dann die mittlere Komplexität über alle diese Eingaben. Oft hat man jedoch in der Praxis andere Wahrscheinlichkeitsverteilungen, z.B. sind die Daten oft "fast sortiert" (nur wenige Elemente sind an der falschen Stelle). Dann verhält sich der Algorithmus ebenfalls anders als vorhergesagt.

Wir beschränken uns in dieser Vorlesung auf die Komplexität im ungünstigseten Fall. '''Exakte''' Formeln für Komplexität sind aber auch dann schwer zu gewinnen, wie das folgende Beispiel zeigt:

=== Beispiele aus den Übungen (Gemessene Laufzeiten für Mergesort/Selectionsort) ===

* Mergesort: <math>\frac{0,977N\log N}{\log 2} + 0,267N-4.39 \!</math>
*: andere Lösung: <math>1140 N\log(N) - 1819N + 6413 \!</math>
* Selectionsort: <math>\frac{1}{2}N^2 - \frac{1}{2N} - 10^{-12} \!</math>
*: andere Lösung: <math>1275N^2 - 116003^N + 11111144 \!</math>

Aus diesen Formeln wird nicht offensichtlich, welcher Algorithmus besser ist.
Näherung: Betrachte nur '''sehr große Eingaben''' (meist sind alle Algorithmen schnell genug für kleine Eingaben). Dieses Vorgehen wird als '''Asymptotische Komplexität''' bezeichnet (N gegen unendlich).

=== Asymptotische Komplexität am Beispiel Polynom ===

Polynom: <math>a\,x^2+b\,x+c=p\!</math>

<math>x \!</math> sei die Eingabegröße, und wir betrachten die Entwicklung von <math>p \!</math> in Abhängigkeit von <math>x \!</math>.

* <math>x=0 \!</math>
*: <math>p=c \!</math>
* <math>x=1 \!</math>
*: <math>p=a+b+c \!</math>
* <math>x=1000 \!</math>
*: <math>p=1000000a+1000b+c \approx 1000000a\!</math>
* <math>x \to \infty \!</math>
*: <math>p \approx x^2a\!</math>

Für sehr große Eingaben verlieren also ''b'' und ''c'' immer mehr an Bedeutung, so dass am Ende nur noch ''a'' für die Komplexitätsbetrachtung wichtig ist.

== O-Notation ==
* Intuitiv: Für große N dominieren die am schnellsten wachsenden Terme.
* Formale Definition:
*; Asymptotische Komplexität: Für zwei Funktionen f(x) und g(x) definiert man
*::<math>f(x) \in \mathcal{O}(g(x))</math>
*:(sprich "f ist in O von g" oder "f ist von derselben Größenordnung wie g") genau dann wenn es eine Konstante <math>c>0</math> und ein Argument <math>x_0</math> gibt, so dass
*::<math>\forall x \ge x_0:\quad f(x) \le c\,g(x)</math>.
*:Die Menge <math>\mathcal{O}(g(x))</math> aller durch g(x) abschätzbaren Funktionen ist also formal definiert durch
*::<math>\mathcal{O}(g(x)) = \{ f(x)\ |\ \exists c>0: \forall x_0 \ge x: f(x) \le c\,g(x)\}</math>
:Die Idee hinter dieser Definition ist, dass g(x) eine wesentlich einfachere Funktion ist als f(x), die sich aber nach geeigneter Skalierung (Multiplikation mit c) und für große Argumente x im wesentlichen genauso wie f(x) verhält. Man kann deshalb in der Algorithmenanalyse f(x) durch g(x) ersetzen. <math>f(x) \in \mathcal{O}(g(x))</math> spielt für Funktionen eine ähnliche Rolle wie der Operator ≤ für Zahlen: Falls a ≤ b gilt, kann bei einer Abschätzung von oben ebenfalls a durch b ersetzt werden.
=== Ein einfaches Beispiel ===

[[Image:Sqsqrt.png]]

Rot = <math>x^2 \!</math>
Blau = <math>\sqrt{x} \!</math>

<math>\sqrt{x} \in \mathcal{O}(x^2)\!</math> weil <math>\sqrt{x} \le c\,x^2\!</math> für alle <math>x \ge x_0 = 1 \!</math> und <math>c = 1\!</math>, oder auch für <math>x \ge x_0 = 4 \!</math> und <math>c = 1/16</math> (die Wahl von c und x0 in der Definition von O(.) ist beliebig, solange die Bedingungen erfüllt sind).

=== Komplexität bei kleinen Eingaben ===

Algorithmus 1: <math>\mathcal{O}(N^2) \!</math> 
Algorithmus 2: <math>\mathcal{O}(N\log{N}) \!</math>

Algorithmus 2 ist schneller (von geringerer Komplexität) für große Eingaben, aber bei kleinen Eingaben (insbesondere, wenn der Algorithmus in einer Schleife immer wieder mit kleinen Eingaben aufgerufen wird) könnte Algorithmus 1 schneller sein, falls der in der <math>\mathcal{O}</math>-Notation verborgene konstante Faktor ''c'' bei Algorithmus 2 einen wesentlich größeren Wert hat als bei Algorithmus 1.

=== Eigenschaften der O-Notation (Rechenregeln) ===

# Transitiv:
#: <math>f(x) \in \mathcal{O}(g(x)) \land g(x) \in \mathcal{O}(h(x)) \to f(x) \in \mathcal{O}(h(x)) \!</math>
# Additiv:
#: <math>f(x) \in \mathcal{O}(h(x)) \land g(x) \in \mathcal{O}(h(x)) \to f(x) + g(x) \in \mathcal{O}(h(x)) \!</math>
# Für Monome gilt:
#: <math>x^k \in \mathcal{O}(x^k)) \land x^k \in \mathcal{O}(x^{k+j}), \forall j \ge 0 \!</math>
# Multiplikation mit einer Konstanten:
#: <math>f(x) \in \mathcal{O}(g(x)) \to c\,f(x) \in \mathcal{O}(g(x))\!</math>
#: andere Schreibweise:
#: <math>f(x) = c\,g(x) \to f(x) \in \mathcal{O}(g(x))\!</math>
# Folgerung aus 3. und 4. für Polynome:
#: <math>a_0+a_1\,x + ... + a_n\,x^n \in \mathcal{O}(x^n)\!</math>
#: Beispiel: <math>a\,x^2+b\,x+c \in \mathcal{O}(x^2)\!</math>
# Logarithmus:
#: <math>a, b \neq 1\!</math>
#: <math>\log_{a}{x} \in \mathcal{O}(\log_{b}{x})\!</math>
#: Die Basis des Logarithmus spielt also keine Rolle.
#: Beweis hierfür:
#:: <math>\log_{a}{x} = \frac{\log_{b}{x}}{\log_{b}{a}}\!</math>
#:: Mit <math>c = 1 / \log_{b}{a}\,</math> gilt: <math>\log_{a}{x} = c\,\log_{b}{x}\!</math>.
#:: Wird hier die (zweite) Regel für Multiplikation mit einer Konstanten angewendet, fällt der konstante Faktor weg, also <math>\log_{a}{x} \in \mathcal{O}(\log_{b}{x})\!</math>.
#: Insbesondere gilt auch <math>\log_{a}{x} \in \mathcal{O}(\log_{2}{x})\!</math>, es kann also immer der 2er Logarithmus verwendet werden.

== O-Kalkül ==

Das O-Kalkül definiert wichtige Vereinfachungsregeln for Ausdrücke in O-Notation:

# <math>f(x) \in \mathcal{O}(f(x))\!</math>
# <math>\mathcal{O}(\mathcal{O}(f(x))) \in \mathcal{O}(f(x))\!</math>
# <math>c\,\mathcal{O}(f(x)) \in \mathcal{O}(f(x))\,</math> für jede Konstante ''c''
# <math>\mathcal{O}(f(x))+c \in \mathcal{O}(f(x))\,</math> für jede Konstante ''c''
# Sequenzregel:
#: Wenn zwei nacheinander ausgeführte Programmteile die Komplexität <math>\mathcal{O}(f(x))</math> bzw. <math>\mathcal{O}(g(x))</math> haben, gilt für beide gemeinsam:
#: <math>\mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(f(x))</math> falls <math>g(x) \in \mathcal{O}(f(x))</math> bzw.
#: <math>\mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(g(x))\!</math> falls <math>f(x) \in \mathcal{O}(g(x))</math>.
#: Informell schreibt man auch: <math>\mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(max(f(x), g(x)))\!</math>
# Schachtelungsregel bzw. Aufrufregel:
#: Wenn in einer geschachtelten Schleife die äußere Schleife die Komplexität <math>\mathcal{O}(f(x))</math> hat, und die innere <math>\mathcal{O}(g(x))</math>, gilt für beide gemeinsam:
#: <math>\mathcal{O}(f(x)) * \mathcal{O}(g(x)) \in \mathcal{O}(f(x) * g(x))\!</math>.
#: Gleiches gilt wenn eine Funktion <math>\mathcal{O}(f(x))</math>-mal aufgerufen wird, und die Komplexität der Funktion selbst <math>\mathcal{O}(g(x))</math> ist.

=== O-Kalkül auf das Beispiel des Selectionsort angewandt ===
Selectionsort: Wir hatten gezeigt dass <math>f(N) = \frac{N^2}{2} - \frac{N}{2}</math>. Nach der Regel für Polynome vereinfacht sich dies zu <math>f(N) \in \mathcal{O}\left(\frac{N^2}{2}\right) \in \mathcal{O}(N^2)\!</math>.

Alternativ via Schachtelungsregel:
: Die äußere Schleife wird (''N''-1)-mal durchlaufen: <math>N-1 \in \mathcal{O}(N)</math>
: Die innere Schleife wird (''N-i''-1)-mal durchlaufen. Das sind im Mittel ''N''/2 Durchläufe: <math>N/2 \in \mathcal{O}(N)</math>
: Zusammen: <math>\mathcal{O}(N)*\mathcal{O}(N) \in \mathcal{O}(N^2)</math>

Nach beiden Vorgehensweisen kommen wir zur Schlussfolgerung, dass der Selectionsort die asymptotische Komplexität <math>\mathcal{O}(N^2)\!</math> besitzt.

=== Zusammenhang zwischen Komplexität und Laufzeit ===

Wenn eine Operation 1ms dauert, erreichen Algorithmen verschiedener Komplexität folgende Leistungen (wobei angenommen wird, dass der in der <math>\mathcal{O}</math>-Notation verborgene konstante Faktor immer etwa gleich 1 ist):

{| class="wikitable" style="text-align:left" cellpadding="7"
|+
|-
! Komplexität !! Operationen in 1s !! Operationen in 1min !! Operationen in 1h
|-
! <math>\mathcal{O}(N)</math>
| 1000 || 60.000 || 3.600.000
|-
! <math>\mathcal{O}(N\log_2{N})</math>
| 140 || 4895 || 204094
|-
! <math>\mathcal{O}(N^2)</math>
| 32 || 245 || 1898
|-
! <math>\mathcal{O}(N^3)</math>
| 10 || 39 || 153
|-
! <math>\mathcal{O}(2^N)</math>
| 10 || 16 || 21
|}

=== Exponentielle Komplexität ===
Der letzte Fall <math>\mathcal{O}(2^N)</math> ist von exponentieller Komplexität. Das bedeutet, dass eine Verdopplung des Aufwands nur bewirkt, dass die maximale Problemgröße um eine Konstante wächst. Algorithmen mit exponentieller (oder noch höherer) Komplexität werden deshalb als '''ineffizient''' bezeichnet. Algorithmen mit höchstens polynomieller Komplexität gelten hingegen als effizient.

In der Praxis sind allerdings auch polynomielle Algorithmen mit hohem Exponenten meist zu langsam. Als Faustregel kann man eine praktische Grenze von <math>\mathcal{O}(N^3)</math> ansehen. Bei einer Komplexität von <math>\mathcal{O}(N^3)</math> bewirkt ein verdoppelter Aufwand immer noch eine Steigerung der maximalen Problemgröße um den Faktor <math>\sqrt[3]{2}</math> (also eine ''multiplikative'' Vergrößerung um ca. 25%, statt nur einer additiven Vergrößerung wie bei exponentieller Komplexität).



(Vorlesung 8.5.)

==Beispiel: Gleitender Mittelwert (Running Average)==

Wir berechnen für ein gegebenes Array <tt>a</tt> einen gleitenden Mittelwert über <tt>k</tt> Elemente: 
::<math>r_i = \frac{1}{k} \sum_{j=i-k+1}^i a_j</math> 
Das heisst, für jedes <tt>i</tt> mitteln wir die letzten <tt>k</tt> Elemente von <tt>a</tt> und schreiben das Ergebnis in <tt>r[i]</tt>. Diese Operation ist z.B. bei Börsenkursen wichtig: Neben dem aktuellen Kurs für jeden Tag wird dort meist auch der gleitende Mittelwert der letzten 30 Tage sowie der letzten 200 Tage angegeben. In diesen Mittelwerten erkennt man besser die langfristige Tendenz, weil die täglichen Schwankungen herausgemittelt werden. Wir nehmen außerdem an, dass
* Array-Zugriff hat eine Komplexität von O(1)
* <math>k \ll N</math>, d.h. <math>N-k\approx N</math>.

Die beiden folgenden Algorithmen berechnen die Mittelwerte auf unterschiedliche Art. Der linke folgt der obigen Definition durch eine Summe, während der rechte inkrementell arbeitet: Man kann den Bereich der <tt>k</tt> letzten Werte als Fenster betrachten, das über das Array <tt>a</tt> geschoben wird. Schiebt man das Fenster ein Element weiter, fällt links ein Element heraus, und rechts kommt eins hinzu. Man muss also nicht jedes Mal die Summe neu berechnen, sondern kann den vorigen Wert aktualisieren. Wir werden sehen, dass dies Folgen für die Komplexität des Algorithmus hat.

{| border="1" cellspacing="0" cellpadding="2"
|-
! Schritte
! Version 1: O(N * k)
! Komplexität
! Version 2: O(N)
! Komplexität
|-
|
1.
|
<tt>r = [0] * len(a)</tt>
|
'''<center>O(N)</center>'''
|
<tt>r = [0] * len(a)</tt>
|
'''<center>O(N)</center>'''
|-
|
2.
|
<tt>if k > len(a):</tt>
|
'''<center>O(1)</center>'''
|
<tt>if k > len(a):</tt>
|
'''<center>O(1)</center>'''
|-
|
3.
|
:: <tt>raise RuntimeError ("k zu groß")</tt>
|

|
:: <tt>raise RuntimeError ("k zu groß")</tt>
|

|-
|
4.
|
<tt>for j in range(k, len(a)):</tt>
|
<center>O(N-k) = '''O(N)'''</center>
|
<tt>for i in range(k):</tt>
|
'''<center>O(k)</center>'''
|-
|
5.
|
:: <tt>for i in range(j-k+1, j+1):</tt>
|
'''<center>O(k)</center>'''
|
:: <tt>r[k] += a[i]</tt>
|
'''<center>O(1)</center>'''
|-
|
6.
|
:::: <tt>r[j] += a[i]</tt>
|
'''<center>O(1)</center>'''
|
<tt>for j in range(k+1, len(a)):</tt>
|
<center>O(N-k) = '''O(N)'''</center>
|-
|
7.
|
:: <tt>r[j] /= float(k)</tt>
|
'''<center>O(1)</center>'''
|
:: <tt>r[j] = (a[j] - a[j-k] + r[j-1])</tt>
|
'''<center>O(1)</center>'''
|-
|
8.
|
<tt>return r</tt>
|
'''<center>O(1)</center>'''
|
<tt>for j in range(len(a)):</tt>
|
'''<center>O(N)</center>'''
|-
|
9.
|

|

|
:: <tt>r[j] /= float(k)</tt>
|
'''<center>O(1)</center>'''
|-
|
10.
|

|

|
<tt>return r</tt>
|
'''<center>O(1)</center>'''
|}

Obwohl Version 2 mehr Zeilen benötigt, besitzt das Programm eine geringere Komplexität.

===Berechnung der Komplexität===

====Berechnung der Komplexität von Version 1====

(Wiederholung der Rechenregeln:siehe Vorlesung 7.5.)

Zuweisungen 
äußere Schleife = f(x) 
innere Schleife = g(x)

4. Schritt: for j in range(k, len(a)) = äußere Schleife 
:: f(x) = O(N)(siehe Tabelle)
5. Schritt: for i in range(j-k+1, j+1) = innere Schleife 
:: g(x) = O(k) 

Multiplikationsregel (für geschachtelte Schleifen): 
O(f(x)) * O(g(x)) ∈ O(f(x) * g(x)) 

Multiplikationsregel angewendet auf Version 1 
O(N) * O(k) ∈ O(N * k) 
Komplexität von Version 1 = O(N * k)

====Berechnung der Komplexität von Version2====

siehe Tabelle

Zuweisungen 

6.Schritt: for j in ange(k+1, len(a)): 
:: f1(x) = O(N)

8.Schritt: for j in range(len(a)): 
:: f2(x) = O(N)

4.Schritt: for i in range(k): 
:: g(x) = O(k)

Additionsregel (für nacheinander ausgeführte Programmteile): 
O(f(x) + g(x)) = O(f(x)) falls g(x) ∈ O(f(x)) 
O(f(x) + g(x)) ∈ O(g(x)) falls f(x) ∈ O(g(x)) 
oder kurz O(f(x) + g(x)) = O(max(f(x),g(x)))

Anwendung der Additionsregel auf Version 2 
O(f1(x)) + O(f2(x)) + O(g(x)) 
O(N) + O(N) +O(k) = O(N), weil O(k) ∈ O(N) [O(max(O(N),O(k)))] 
(da wir wissen O(k) < O(N): 
if k > len(a):
:: raise RuntimeError("k zu groß") 
Daraus folgt: 
→ k < len(a) → for-Schleifen die über k iterieren haben eine kleinere Komplexität als for-Schleifen die über len(a) iterieren)

Komplexität von Version 2 = O(N)

====Fazit====

Obwohl Version 2 mehr Schritte benötigt hat sie eine geringere Komplexität, da die for-Schleifen nicht wie bei Version 1 verschachtelt/untergeordnet sind. Bei verschachtelten for-Schleifen muss die Multiplikationsregel angewendet → höhere Komplexität

Die gerade berechnete Komplexität gilt nur unter der Annahme, dass Array-Zugriffe eine Komplexität von O(1) besitzen

{| border="1" cellspacing="0" cellpadding="5"
|Allgemein:
Algorithmen-Analysen beruhen auf der Annahme, dass Zugriff auf die Daten optimal schnell sind, dass heißt dass die geeigneteste Datenstruktur verwendetet wird. → Ansonsten: Komplexitätsverschlechterung!
|}

===Beispiel für eine Verschlechterung der Komplexität durch Verwendung einer nicht optimalen Datenstruktur===

Beispiel: Verwende eine verkettete Liste anstalle eines Arrays. Um auf das j-te Element der Liste zuzugreifen, muss die Liste bis dahin durchlaufen werden

{| border="1" cellspacing="0" cellpadding="5" align="left"
!Implementation von L[j] für verkettete Liste
!Komplexität
|-
|
: <tt>r = L.head</tt>
|
O(1)
|-
|
<tt>while j > 0:</tt>
|
O(j)
|-
|
:: <tt>r = r.next</tt>
|
O(1)
|-
|
:: <tt>j -= 1</tt>
|
O(1)
|-
|
<tt>return r.data</tt>
|
O(1)
|}

'''<math> \Bigg\rbrace </math> O(j)''' 
r[j] = r[j] + a[i] '''→''' O(1) → O(N), falls a[i]= O[N]

====Fazit:====
Wegen der Schleife hat der Array-artige Zugriff bei einer verketteten Liste eine Komplexität von O(N). 
Würden wir in unserem running Average-Beispiel(siehe oben) auf eine verkettete Liste zugreifen hätten wir anstatt O(1) eine Komplexität von O(N) für den Zugriff auf unser Array.

Beispiel: Running-Average mit verketteter Liste

{| border="1" cellspacing="0" cellpadding="5"
! Schritte
! Version 1 mit verketteter Liste: O(N2 * k)
! Komplexität
|-
|
1.
|
<tt></tt>
|
'''<center>O(N)</center>'''
|-
|
2.
|
<tt>if k > len(a):</tt>
|
'''<center>O(1)</center>'''
|-
|
3.
|
:: <tt>raise RuntimeError ("k zu groß")</tt>
|

|-
|
4.
|
<tt>for j in range(k, len(a)):</tt>
|
<center>O(N-k) = '''O(N)'''</center>
|-
|
5.
|
:: <tt>for i in range(j-k+1, j+1):</tt>
|
'''<center>O(k)</center>'''
|-
|
6.
|
:::: <tt>r[j] += a[i]</tt>
|
'''<center>O(i) = '''O(N)'''</center>'''
|-
|
7.
|
:: <tt>r[j] /= float(k)</tt>
|
'''<center>O(1)</center>'''
|-
|
8.
|
<tt>return r</tt>
|
'''<center>O(1)</center>'''
|-
|}

Die Änderung gegenüber der ursprünglichen Version ist in Zeile 6. Der Zugriff <tt>a[i]</tt> erfolgt jetzt auf eine Liste, nicht auf ein Array. Aufgrund der obigen Implementation dieses Zugriffs verbirgt sich dahinter ''eine weitere Schleife''. Das heisst, wir haben jetzt '''drei''' geschachtelte Schleifen.
Zuweisungen 
äußere Schleife = f2(x) 
innere Schleife = g(x)

verkettete Liste 
:: f1(x) = O(N)
4. Schritt: for j in range(k, len(a)) = äußere Schleife 
:: f2(x) = O(N)(siehe Tabelle)
5. Schritt: for i in range(j-k+1, j+1) = innere Schleife 
:: g(x) = O(k) 

Multiplikationsregel ohne Konstante: 
O(f(x) * O(g(x)) ∈ O(f(x) * g(x)) 

Multiplikationsregel angewendet auf Version 1 mit einer verketteten Liste 

O(N) * O(N) * O(k) ∈ O(N2 * k) 

Die Komplexität von Version 1 mit einer verketteten Liste wäre O(N2 * k)

'''→ Die richtige Datenstruktur ist wichtig, da es sonst zu einer Komplexitätsverschlechterung kommen kann!'''

Auf Version 2 unseres runningAverage-Beispiels hätte eine verkettete Liste allerdings keine Auswirkungen, da die Additionsregel bei der Komplexitätsberechnung angewendet würde und somit Version 2 immer noch eine Komplexität von O(N) hätte.

==Amortisierte Komplexität==

Bis jetzt wurde die Komplexität nur im schlechtesten Fall(Worst Case) betrachtet, die Komplexität im schlechtesten Fall schwankt jedoch. 
Die amortisierte Komplexität beschäftigt sich mit der Komplexität im durschnittlichen/typischen Fall(Average Case)

Zum weiter Lesen: [[http://de.wikipedia.org/wiki/Amortisierte_Laufzeitanalyse Wikipedia: Amortisierte Laufzeitanalyse]]

===Beispiel: Inkrementieren von Binärzahlen===

Frage: Was kostet eine Operation im Durchschnitt?

Annahme: Bei jeder Operation wird ein Gehalt vom Wert 1 bezahlt, dass dem Guthaben zugeschrieben wird, wenn die Kosten das Gehalt decken. 
:: Kosten <= Gehalt → es wird gespart
:: Kosten > Gehalt → Guthaben - Gehalt werden für die Kosten verbraucht

{| border="1" cellspacing="0" cellpadding="5" align="left"
!Schritte
!Zahlen
!Kosten
!Kosten + Sparen
!Guthaben
|-
|1.
|00001
|1
|'''2'''
|'''1'''
|-
|2.
|00010
|2
|'''2'''
|'''1'''
|-
|3.
|00011
|1
|'''2'''
|'''2'''
|-
|4.
|00100
|3
|'''2'''
|'''1'''
|-
|}

Die Kosten ergeben sich aus der Anzahl der Ziffern die von 1 nach 0, bzw. von 0 nach 1 verändert werden

Rechnung:

1. Schritt: Kosten: 1 <= Gehalt: 1 
:: → es wird gespart 

2. Schritt: Kosten: 2 > Gehalt: 1 
:: → es wird nicht gespart 
:: → Guthaben bleibt so wie es ist 

3. Schritt: Kosten: 1 <= Gehalt: 1 
:: → es wird gespart 

4. Schritt: Kosten: 3 > Gehalt: 1 
:: → Guthaben: 2 - Gehalt: 1 = 1 
:: → es wird eine 1 vom Guthaben genommen um die Kosten zu zahlen 

Zum weiter Lesen: [[http://de.wikipedia.org/wiki/Account-Methode Wikipedia Account-Methode]]

====Fazit====
Die amortisierte Komplexität beschäftigt sich mit dem Durchschnitt aller Operation im ungünstigsten Fall. Operationen mit hohen Kosten, die aber nur selten ausgeführt werden, fallen bei der amortisierten Komplexität nicht so ins Gewicht. Bei Algorithmen, die gelegentlich eine "teure" Operation benutzen, ansonsten jedoch "billigen" Operationen aufrufen, kann die amortisierte Komplexität niedriger sein also die Komplexität im schlechtesten (Einzel-)Fall.

In unserem Beispiel fällt der 4. Schritt bei den Kosten schlußendlich nicht so ins Gewicht, da wir die Kosten aus unserem Guthaben mitbezahlen können → tatsächliche Kosten = 3, Kosten + Sparen = 2 
:: → Der Algorithmus besitzt durch dieses Verfahren eine niedrigere Komplexität

==statisches Array==

Ein statisches Array hat eine feste Größe N und besitzt eine Komplexität von O(N). 
Wird das Array um ein Element erweitert, muss ein neues Array mit der Größe N+1 erzeugt werden. 

Anhängen eines weiteren Elements an ein statisches Array:

{| border="1" cellspacing="0" cellpadding="5" align="right"
!Schritte
|'''Array'''
(wie es aussehen könnte)
!Komplexität
|-
|<center>altes Array</center>
|<center>[0,1,2,3]</center>
|<center>-</center>
|-
|1. Array N+1
|<center>[None,None,None,None,None]</center>
|<center>O(N+1) = '''O(N)'''</center>
|-
|2. Kopieren
|<center>[0,1,2,3,None]</center>
|<center>'''O(N)'''</center>
|-
|3. append von "x"
|<center>[0,1,2,3,'x']</center>
|<center>'''O(1)'''</center>
|-
|}

altesArray = [0,1,2,3] 
altesArray.append('x')

1. Es wird ein neues Array der Größe N+1 erzeugt 
2. Die Daten aus dem alten Array werden in das neue Array mit der Länge N+1 kopiert 
(Die Operation besitzt nur eine Komplexität von O(N), wenn das Kopieren eines Elements eine Komplexität von O(1) besitzt) 
3. 'x' wird an die letzte Stelle des neuen Arrays geschrieben

Additionsregel: 
O(N) + O(N) + O(1) ∈ O(N), falls O(1) ∈ O(N) [O(max(O(N),O(1))] (Bedingung: N > 1)

==dynamisches Array==

Beim dynamischen Array werden mehr Speicherelemente reserviert als zur Zeit benötigt. Es gibt verschiedene Möglichkeiten wie ein dynamisches Array realisiert werden kann.

capacity = Anzahl der möglichen Elemente, die in das Array passen 
size = Anzahl der Elemente, die im Array gespeichert sind 
data = statisches Array der Größe "capacity" 
A

Beispiele für mögliche Vorgehensweisen eines dynamischen Arrays beim Zufügen eines neuen Elements: (size == capacity)
* Ein neues statisches Array der Größe size == capacity wird erzeugt
* capacity wird verdoppelt 
: → neue capacity = 2 * alte capacity
* capacity wird um einen Prozentsatz vergrößert 
: → neue capacity = alte capacity * c, c > 1
* ...

'''Folge:''' Das Hinzufügen eines neuen Elements in ein dynamisches Array ist amortisiert, die Operation besitzt eine Komplexität von O(1).

==Analyse des dynamischen Arrays==

Durchschnitt der Gesamtkosten für N-maliges append = <math>\frac{1}{N} \sum_{i = 1}^N Kosten(i)</math> 

Fall 1: Array ist nicht voll 
Es wird kein Umkopieren benötigt, da das Array noch nicht voll ist → size < capacity

Kosten: 1 
Potenzial vor append: Φi-1 = 2(i - 1) - capacity 
Potenzial nach append: Φi - capacity 

amortisierte Kosten = Kosteni + Φ(i) - Φ(i-1)
::::: = 1 + (2i - capacity) - [2(i - 1) - capacity]
::::: = 1 + 2i - capacity - 2i + 2 + capacity
::::: = 1 + <del>2i</del> - <del>capacity</del> - <del>2i</del> + 2 + <del>capacity</del>
::::: = 1 + 2
::::: = 3 = O(1) → konstant

Fall 2: Array ist voll 
Umkopieren wird nach i-tem append benötigt → size == capacity

Kosten: (i-1) + 1 
Potenzial vor append = Φi-1 = 2(i - 1) - capacity 
Potenzial nach append = Φi = 2i - 2 * capacity 
::::: = 2i - 2i , da capacity = i
::::: = 0
amortisierte Kosten = Kosteni + Φ(i) - Φ(i-1)
::::: = ((i - 1) + 1) + 0 - [2(i-1) - capacity]
::::: = i - 2i - 2 - capacity
::::: = <del>i</del> - <del>2</del>i - 2 - capacity
::::: = <del>i</del> - 2 - <del>capacity</del> , da capacity = i
::::: = 2 = O(1) → konstant

'''Damit wurde bewiesen, dass die Operation append beim dynamischen Array amortisiert ist → O(1)'''

{| border="1" cellspacing="0" cellpadding="5" align="left"
!Array 
(wie es aussehen könnte)
!size
!capacity
!Kosten 1.append
!Summe Kosten
!Durchschnittskosten
!Φi = 2 * size - capacity 
(i = size)
!Potenzialdifferenz 
Δ Φi = Φi - Φi-1
!amortisierte Kosteni 
= Kosteni + Δ Φi
|-
| <center>[None]</center>
| <center>0</center>
| <center>1</center>
| <center>-</center>
| <center>-</center>
| <center>-</center>
| <center>-1</center>
| <center>-</center>
| <center>-</center>
|-
| <center>[a]</center><center>Array ist voll!</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>1</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b]</center><center>Array ist voll!</center>
| <center>2</center>
| <center>2</center>
| <center>1 + 1</center>
| <center>3</center>
| <center>3/2</center>
| <center>2</center>
| <center>1</center>
| <center>3</center>
|-
| <center>[a,b,c,None]</center>
| <center>3</center>
| <center>4</center>
| <center>2 + 1</center>
| <center>6</center>
| <center>6/3</center>
| <center>2</center>
| <center>0</center>
| <center>3</center>
|-
| <center>[a,b,c,d]</center><center>Array ist voll!</center>
| <center>4</center>
| <center>4</center>
| <center>1</center>
| <center>7</center>
| <center>7/4</center>
| <center>4</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,None,None,None]</center>
| <center>5</center>
| <center>8</center>
| <center>4 + 1</center>
| <center>12</center>
| <center>12/5</center>
| <center>2</center>
| <center>-2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,None,None]</center>
| <center>6</center>
| <center>8</center>
| <center>1</center>
| <center>13</center>
| <center>13/6</center>
| <center>4</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,g,None]</center>
| <center>7</center>
| <center>8</center>
| <center>1</center>
| <center>14</center>
| <center>14/7</center>
| <center>6</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,g,h]</center><center>Array ist voll!</center>
| <center>8</center>
| <center>8</center>
| <center>1</center>
| <center>15</center>
| <center>15/8</center>
| <center>8</center>
| <center>2</center>
| <center>3</center>
|-
| <center>[a,b,c,d,e,f,g,h,j,None,None,None, 
None,None,None,None,None,None]</center>
| <center>9</center>
| <center>16</center>
| <center>8 + 1</center>
| <center>24</center>
| <center>24/9</center>
| <center>2</center>
| <center>-6</center>
| <center>3</center>
|-

== Landau-Symbole ==

Um die asymptotische Komplexität verschiedener Algorithmen miteinander vergleichen zu können, verwendet man die sogenannten [http://de.wikipedia.org/wiki/Landau-Symbole Landau-Symbole]. Das wichtigste Landau-Symbol ist <math>\mathcal{O}</math>, mit dem man eine ''obere Schranke'' für die Komplexität angeben kann.

Schreibt man <math>f \in \Omega(g)</math>, so stellt dies eine asymptotische ''untere Schranke'' für die Funktion f dar.

Schließlich bedeutet <math>f \in \Theta(g)</math>, dass die Funktion f genauso schnell wie die Funktion g wächst, das heißt man hat eine asymptotisch ''scharfe Schranke'' für f. Hierzu muss sowohl <math>f\in\mathcal{O}(g)</math> als auch <math>g\in\mathcal{O}(f)</math> erfüllt sein.

Im nun folgenden soll auf die verschiedenen Landau-Symbole noch näher eingegeangen werden.

===<math>\mathcal{O}</math> - Notation===

<math>f \in \mathcal{O}(g)</math> ist eine Abschätzung der asymptotischen Komplexität der Funktion f von oben. Per Definition gilt <math>f(N) \in \mathcal{O}(g(N))</math> genau dann, falls eine Konstante

<math> c > 0 </math> existiert, so dass

<math> f(N) \le c \cdot g(N) </math> für <math> N \ge N_0 </math>

erfüllt ist.

Im Prinzip ist <math>f \in \mathcal{O}(g)</math> also ein <-Operator für Funktionen, analog zum <-Operator für Zahlen.

===<math>\Omega</math>- Notation===

<math>f \in \Omega(g) </math> schätzt die asymptotische Komplexität der Funktion f nach unten ab.

Formal kann man <math>f(N) \in \Omega(g(N)) </math> genau dann schreiben, falls es eine Konstante <math> c > 0 </math> gibt, so dass

<math> f(N) \ge c \cdot g(N) </math> für <math> N \ge N_0 </math>

gilt.
Man verwendet diese Notation also um abzuschätzen, wie groß der Aufwand (die Komplexität) für einen bestimmten Algorithmus ''mindestens'' ist und nicht ''höchstens'', was man mit der <math>\mathcal{O}</math> - Notation ausdrücken würde.

Ein praktisches Beispiel für eine Anwendung der <math>\Omega</math>- Notation wäre die Fragestellung, ob es ''prinzipiell'' einen besseren Algorithmus für ein bestimmtes Problem gibt. Wie später in der Vorlesung gezeigt werden wird, ist das Sortieren eines Arrays beispielsweise immer mindestens von der Komplexität <math> \Omega(N\cdot \ln N) </math>, was konkret bedeutet, dass kein Sortieralgorithmus jemals eine geringere Komplexität als Merge-Sort beispielsweise haben wird. Natürlich kann man den entsprechenden Sortieralgorithmus, also Merge-Sort zum Beispiel, unter Umständen noch optimieren, aber die Komplexität wird erhalten bleiben. Mit diesem Wissen kann man sich viel (vergebene) Arbeit sparen.

===<math>\Theta</math>- Notation===

<math>f(N) \in \Theta(g(N))</math> ist eine scharfe Abschätzung der asymptotischen Komplexität einer Funktion f.

Damit dies gilt, muss <math>f(N) \in \mathcal{O}(g(N))</math> und ''gleichzeitig'' <math>f(N) \in \Omega(g(N))</math> erfüllt sein.

Dies ist natürlich auch die beste Abschätzung der asymptotischen Komplexität einer Funktion f. Formal bedeutet <math>f(N) \in \Theta(g(N))</math> dass es zwei Konstanten <math> c_1 </math> und <math> c_2 </math>, beide größer als Null, gibt, so dass für alle <math> N \geq N_0 </math> gilt:

<math> c_1 \cdot g(N) \leq f(N) \leq c_2 \cdot g(N) </math>.

In der Praxis verwendet man jedoch statt der <math>\Theta</math>- Notation oft die <math>\mathcal{O}</math> - Notation.

== Komplexitätsvergleich zweier Algorithmen ==

In diesem Abschnitt wollen wir der Frage nachgehen, wie ein formaler Beweis für die Behauptung <math> f(N) \in \mathcal{O}(g(N))</math> geschehen kann. Hierbei werden zwei Beweismethoden vorgestellt werden, und zwar der '''Beweis über die Definition der Komplexität''' sowie der '''Beweis durch Dividieren'''.
===Beweis über die Definition der asymptotischen Komplexität===

Die Definition der asymptotischen Komplexität <math>f(N) \in \mathcal{O}(g(N))</math> war:

Es gibt eine Konstante <math> c > 0 </math>, so dass <math> f(N) \le c \cdot g(N) </math> für <math> N \ge N_0 </math> erfüllt ist.

Um also die die asymptotische Komplexität <math>f(N) \in \mathcal{O}(g(N))</math> zu beweisen, muss man die oben erwähnten Konstanten c und <math> N_0 </math> finden, so dass

<math> f(N) \leq g(N) </math> für alle <math> N \ge N_0 </math> erfüllt ist.

Dies geschieht zweckmäßigerweise mit dem Beweisprinzip der ''vollständigen Induktion''. Hierbei ist zu zeigen, dass
# <math> f(N_0) \leq g(N_0) </math> für die eine zu bestimmende Konstante <math> N_0 </math> gilt (''Induktionsanfang'') und
# falls <math> f(N) \leq g(N) </math>, dann auch <math> f(N+1) \leq g(N+1) </math> (''Induktionsschritt'') gilt.

===Beweis durch Dividieren===

Hierbei wählt man eine Konstante c und zeigt, dass <math> \lim_{N \rightarrow \infty} \frac{f(N)}{c \cdot g(N)} \leq 1 </math> gilt. Man kann dies als eine alternative Definition von Komplexität ansehen.

Als Beispiel betrachten wir die beiden Funktionen <math> f(N) = N \,\lg N </math> und <math> g(N) = N^2 </math> und wollen zeigen, dass <math>f(N) \in \mathcal{O}(g(N))</math> gilt.

Als Konstante c wählen wir <math> c = 1 </math>

<math> \lim_{N \rightarrow \infty} \frac{f(N)}{g(N)} = \lim_{N \rightarrow \infty} \frac{\lg N}{N} = \frac{\infty}{\infty} </math>

Unbestimmte Ausdrücke der Form
<math> \lim_{x \rightarrow x_0} \frac{f(x)}{g(x)} </math>,
in denen sowohl <math> f(x) </math> als auch <math> g(x) </math> mit <math> x \rightarrow x_0 </math> gegen Null oder gegen Unendlich streben, kann man manchmal mit den Regeln von [http://de.wikipedia.org/wiki/L%27Hospital%27sche_Regel ''l'Hospital''] berechnen. Danach darf man die Funktionen f und g zur Berechnung des unbestimmten Ausdrucks durch ihre k-ten Ableitungen ersetzen:

<math> \lim_{x \rightarrow x_0} \frac{f(x)}{g(x)} = \lim_{x \rightarrow x_0} \frac{f^{(k)}(x)}{g^{(k)}(x)} </math>

In unserem Fall verwenden wir die erste Ableitung und erhalten:
<math> \lim_{N \rightarrow \infty} \frac{f'(x)}{g'(x)} = \lim_{N \rightarrow \infty} \frac{1/N}{1} \rightarrow 0 </math>

Damit wurde <math>f(N) \in \mathcal{O}(g(N))</math>, also <math>N \lg N \in \mathcal{O}(N^2)</math> gezeigt.

Man beachte hierbei, dass <math>N \lg N \in \mathcal{O}(N^2)</math> keine enge Grenze für die Komplexität von <math>N \,\lg N)</math> darstellt, da der Grenzwert <math> \lim_{N \rightarrow \infty} \frac{f'(x)}{g'(x)}\, </math> gegen 0 und nicht gegen eine von Null verschiedene Konstante strebt. In diesem Fall haben wir also die Komplexität von <math>N \cdot \lg N </math> also nur nach oben abschätzen können.

File:Baum.png

2008-05-19T20:15:47Z

Friedrich: uploaded a new version of "Image:Baum.png"

Suchen

2008-05-19T20:13:28Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4,\, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (''Schlüssel''), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum'' hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# Das Einfügen und Suchen im Baum Baum wechselt sich ab.
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-, >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

class Node:
def __init__(self, new):
self.key = key
self.left = self.right = None

root = ... # Wurzel des Suchbaums
nodeFound = treeSearch(root, key) # None, falls nichts gefunden

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

Suchen

2008-05-19T20:12:22Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4,\, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (''Schlüssel''), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum'' hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# Das Einfügen und Suchen im Baum Baum wechselt sich ab.
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-, >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

class Node:
def __init(self, new):
self.key = key
self.left = self.right = None

root = ... # Wurzel des Suchbaums
nodeFound = treeSearch(root, key) # None, falls nichts gefunden

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

File:Baum.png

2008-05-19T20:10:38Z

Friedrich: uploaded a new version of "Image:Baum.png": Zur Begriffsillustration von Bäumen

File:Baum.gif

2008-05-19T20:04:03Z

Friedrich:

File:Baum.pdf

2008-05-19T19:58:35Z

Friedrich:

Suchen

2008-05-18T12:27:13Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|200x200px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (''Schlüssel''), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum'' hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# Das Einfügen und Suchen im Baum Baum wechselt sich ab.
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-, >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

class Node:
def __init(self, new):
self.key = key
self.left = self.right = None

root = ... # Wurzel des Suchbaums
nodeFound = treeSearch(root, key) # None, falls nichts gefunden

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

Suchen

2008-05-18T12:11:03Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|200x200px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (''Schlüssel''), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum'' hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# Das Einfügen und Suchen im Baum Baum wechselt sich ab.
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-, >-Relation).

Suchen

2008-05-18T11:58:21Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|200x200px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft, eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein ''Binärbaum'' wie oben skizziert besteht aus einer Menge von ''Knoten'', die untereinander durch ''Kanten'' verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit ''None'' implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man ''Wurzel'' nennt. Knoten ohne Kinder heißen ''Blätter''.

Ein ''Suchbaum''

Suchen

2008-05-18T11:46:31Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|200x200px|Zur Illustration von Bäumen]]

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft, eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Suchen

2008-05-18T11:36:37Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|200x200px|Zur Illustration von Bäumen]]

Suchen

2008-05-18T11:33:20Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|framed|thumb|200x200px|Baum]]

Suchen

2008-05-18T11:31:54Z

Friedrich: /* Suche in einem Binärbaum */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)


Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

Um sich der Vielseitigkeit von Suchproblemen bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren Suchverfahren] verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren.
Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

* '''Schlüsselsuche''': meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

* '''Bereichssuche''': im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden durch graphisch durch [http://de.wikipedia.org/wiki/Hyperebene Hyperebenen] repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

* '''Ähnlichkeitssuche''': finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

* '''Graphensuche''': Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt Folgenden wird nur noch die ''Schlüsselsuche'' betrachtet werden.

==Sequentielle Suche==

Die ''sequentielle'' oder ''lineare'' Suche ist die einfachst mögliche Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array
len(a) == N
foundIndex = seqSearch(a, key)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N wenn key gefunden (erster Eintrag mit diesem Wert)

def SeqSearch(a, key):
for i in range(len(a)):
if a[i] == key: # bzw. allgemeiner a[i].key == key
return i
return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

Der Name ''lineare'' Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

==Binäre Suche==

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem [http://de.wikipedia.org/wiki/Divide_and_Conquer Divide and Conquer-Prinzip], wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum]
(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = [] # array
len(a) == N
a.sort() # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a)) # (Array, Schlüssel, von wo bis wo suchen im Array)

def binSearch(a, key, start, end): # start ist 1. Index, end ist letzter Index + 1
size = end - start # <math> \mathcal{O}(1)</math>
if size <= 0: # Bereich leer? <math> \mathcal{O}(1)</math>
return -1 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math> Anweisungen sowie der Rekursion und ist

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Falls jetzt gilt <math> N = 2^n </math>

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die ''binäre Suche'' also weit effizienter als die ''lineare Suche''. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die ''sequentielle Suche'' - bei der ''binären Suche'' hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten jedoch (<math> N = 4, 5 </math>) ist die ''sequentielle Suche'' jedoch schneller als die ''binäre Suche'', da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind.

Eine relativ einfache Möglichkeit, die ''binäre Suche'' zu verbessern, ist die sogenannte ''Interpolationssuche''. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von ''Sedgewick''.

Um sich den Algorithmus der ''binären Suche'' klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anszusehen:

{| class="wikitable" style="text-align:center" border="1" cellpadding="2"

! key !! start !! end !! size !! center !! return !! Kommentare
|-
| 4 ||0 || 5 || 5 || 2 || 2 ||
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|-
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|-
| ||0 || 2 || 2 || 1 || ||
|-
| ||0 || 1 || 1 || 0 || ||
|-
| ||0 || 0 || 0 || || -1 || rechter Randfall
|-
| 6 ||0 || 5 || 5 || 2 || ||
|-
| || 3 || 5 || 2 || 4 || 4 ||
|-
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|-
| ||3 || 5 || 2 || 4 || ||
|-
| || 3 || 4 || 1 || 3 || 3 ||
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 ||
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|thumb|100x100px|Baum]]

File:Baum.png

2008-05-18T11:27:02Z

Friedrich: uploaded a new version of "Image:Baum.png"

File:Baum.png

2008-05-18T11:26:22Z

Friedrich: uploaded a new version of "Image:Baum.png"

File:Baum.png

2008-05-18T11:17:43Z

Friedrich: