Suchen & Sortieren

mit Arrays

Inhalte Die wichtigsten Algorithmen zum Suchen & Sortieren von

Listen, bzw. Arrays Komplexität eines Algorithmus‘ Algorithmen entwerfen mit Struktogrammen Iteration & Rekursion Erste Erfahrungen mit Java in NetBeans

Lernziele heute Sie kennen elementare Suchalgorithmen (lineare und

binäre Suche) und können diese erklären, implementieren und bezüglich ihrer Zeitkomplexität bewerten

Sie kennen und verstehen die Begriffe Iteration & Rekursion und können den Unterschied anhand von Implementierungen eines Suchalgorithmus erklären

Sie wissen, was man unter der Komplexität eines Algorithmus‘ versteht, und Sie können diese Komplexität für einfache Beispielalgorithmen und Probleme selbständig abschätzen und Ihr Vorgehen erklären

Array: typ[] name = {Werte}Regal mit gleichartigen Kisten: name[0] Inhalt der ersten Kiste

int[] arr = {3, 5, 0, 17};

System.out.println(arr[3]); // 17arr[1] = 11; // an 2. Stelle 11 statt 5int x = arr[0]; // x ist 3int l = arr.length; // l ist 4

int[] arr = {3, 5, 0, 17};

System.out.println(arr[3]); // 17arr[1] = 11; // an 2. Stelle 11 statt 5int x = arr[0]; // x ist 3int l = arr.length; // l ist 4

Beispiel:

Arrays

Iteration Die Iteration (von lateinisch iterare,

"wiederholen") ist ein Begriff aus der Mathematik und bezeichnet eine Methode, sich der Lösung eines Rechenproblems schrittweise, aber zielgerichtet anzunähern durch wiederholte Anwendung desselben Rechenverfahrens.

In der Informatik wird auch von Iteration gesprochen, wenn man mit allen Elementen eines Arrays arbeiten will und sie dazu nacheinander anspricht, also (mithilfe einer Schleife) durch den Array „iteriert“

Iteration als Struktogramm

Die FOR-Schleife besteht aus einem Verarbeitungsteil und einem Steuerungsteil mit einer Bedingung.

• Die Bedingung bestimmt, ob bzw. wie häufig der Verarbeitungsteil ausgeführt wird, wenn das Programmkonstrukt durchlaufen wird.

Rekursion Rekursion, auch Rekurrenz oder Rekursivität, bedeutet

Selbstbezüglichkeit (von lateinisch recurrere = „zurücklaufen“). Sie tritt immer dann auf, wenn etwas auf sich selbst verweist. Ein rekursives Element muss nicht immer direkt auf sich selbst verweisen (direkte Rekursion), eine Rekursion kann auch über mehrere Zwischenschritte entstehen.

Rekursion kann dazu führen, dass merkwürdige Schleifen entstehen. So ist z.B. der Satz „Dieser Satz ist unwahr“ rekursiv, da er von sich selber spricht. Eine etwas subtilere Form der Rekursion (indirekte Rekursion) kann auftreten, wenn zwei Dinge gegenseitig aufeinander verweisen. Ein Beispiel sind die beiden Sätze: „Der folgende Satz ist wahr“ und „Der vorhergehende Satz ist nicht wahr“.

Rekursion zur Problemlösung Als Rekursion bezeichnet man den Aufruf oder

die Definition einer Funktion durch sich selbst. Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen so genannten infiniten Regress (umgangssprachlich Endlosschleife).

In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu „eleganten“ mathematischen Lösungen.

Rekursion als Struktogramm

Unter Rekursion versteht man ein LÖSUNGSVERFAHREN, in der Mathematik und Informatik, bei dem ein Problem derart gelöst wird, dass man es auf das selbe, aber etwas vereinfachte Problem zurückführt.

9

Wesentliche Bestandteile einer Rekursion Die Abbruchbedingung gibt an, welche Bedingung erfüllt sein muss, damit das Lösungsverfahren beendet wird.Die Reduktion gibt an, wie ein Problem auf ein gleichartiges, aber einfacheres Problem zurück zu führen ist.

10

ABBRUCHBEDINGUNG

REDUKTION

SELBSTAUFRUF

Teile & Herrsche (divide & conquer) Falls ein Problem für eine direkte Lösung zu umfangreich

ist, dann: teile das Problem in mindestens zwei, ungefähr gleich grosse

Teilprobleme (divide). löse die kleineren, einfacheren Teilprobleme (elementare Probleme) auf

die gleiche Art (conquer). füge die Teillösungen zu einer Gesamtlösung zusammen (merge)

Teile und herrsche“ ist eines der wichtigsten Prinzipien für effiziente Algorithmen. Dabei wird ausgenutzt, dass bei vielen Problemen der Lösungsaufwand sinkt, wenn man das Problem in kleinere Teilprobleme zerlegt ( reduzierte Komplexität). Dies lässt sich meist durch Rekursive Programmierung umsetzen.

http://de.wikipedia.org/wiki/Teile_und_herrsche_%28Informatik%29

Komplexität (Zeitkomplexität) Unter der Zeitkomplexität eines Problems versteht man

die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen Laufzeit und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z.B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit).

Machbarkeitsüberlegungen Angenommen:

Im Test zeigt sich, dass ein Programm für 10 Datenwerte 1 sec benötigt Wenn der Algorithmus Komplexität O(f(n)) hat,

wie viele Eingabedaten kann er in 1 Tag, 1 Jahr, 10 Jahren, 1000 Jahren verarbeiten?

Laufzeitabschätzung

Wir betrachten, wie viele Schritte im Algorithmus abgearbeitet werden müssen - abhängig von der Menge der Eingabedaten.

Beispiel 1:Wir haben eine Namensliste und wollen wissen, ob ein bestimmter Name darin vorkommt. und jetzt?

Kerim Alexandra LorenzJulianSamuelNirubanAymarJoëlSlavkoManuelNathanaelAnselmNiko

Laufzeitabschätzung

1) Lösung (Algorithmus) finden

2) Für den ungünstigsten Fall (worst

case) durchspielen

3) Laufzeit abschätzen (O-Notation)

Kerim Alexandra LorenzJulianSamuelNirubanAymarJoëlSlavkoManuelNathanaelAnselmNiko

Algorithmus Lineare Suche

• Worst case?• Laufzeit

– n = 10?– n = 20?– n = 100?– allgemein?

O(n)(n verdoppeln ver-

doppelt Laufzeit)

Algorithmus Binäre Suche

• Worst case?• Laufzeit

– n = 10?– n = 20?– n = 100?– allgemein?

O()

Laufzeitabschätzung

Wir betrachten, wie viele Schritte im Algorithmus abgearbeitet werden müssen - abhängig von der Menge der Eingabedaten.

Beispiel 2:Wir haben eine Namensliste und wollen wissen, ob ein Name darin doppelt vorkommt.

Kerim Alexandra LorenzJulianSamuelNirubanAymarJoëlSlavkoManuelNathanaelAnselmNiko

Allgemeine Laufzeit?

O-Notation

Wir betrachten, wie sich die Schrittanzahl im Algorithmus für eine sehr grosse Anzahl von Eingabedaten verhält („obere Schranke“ für Worst Case).

Beispiel Namensliste:Für n Eingabedaten brauchen wir sicher nicht mehr als

(n-1)+(n-2)+…+(1) = Schritte.

Schreibweise:Laufzeit_Namensliste = O(n2)

2

)1( nn

O-Notation

Vereinfachungsregeln:

Addition f(n) = n + 3 ⇒ O(n)

f(n) = n2 + 3n O⇒ (n2)

Multiplikation f(n) = 3n ⇒ O(n)

f(n) = n2 * 3n ⇒ O(n3)

Konstante Summanden werden vernachlässigt

Es zählt der Summand mit dem stärkeren Wachstum Konstante Faktoren werden vernachlässigt

Es zählt die Summe der Exponenten

Komplexitätsabschätzung worst-case complexity

die Betriebsmittel, die maximal zur Ausführung eines Algorithmus benötigt werden.

average-case complexity durchschnittlicher Betriebsmittelbedarf für alle

Eingaben. Dieser wird als Komplexität des Algorithmus im Durchschnittsfall bezeichnet.

best-case complexity Betriebsmittelbedarf im günstigsten Fall

Komplexitätsklassen O(2n) : Klasse aller exponentiellen Algorithmen

Algorithmen, die ihre Lösung durch systematisches Ausprobieren finden Beispiel: Wie packt man möglichst viele verschieden große Quader in einen Waggon? Hoffnungslos ineffizient für große n

O(nk) : Klasse aller polynomialen Algorithmen Gelten als „noch praktikable“ Algorithmen

O(n2) : Klasse aller quadratischen Algorithmen Einfache Sortieralgorithmen sind quadratisch (bubbleSort, insertionSort, selectionSort)

O(n*log(n)) : loglineare Algorithmen Gute Sortieralgorithmen sind loglinear (quickSort )

O(n) : Klasse aller linearen Algorithman sehr gut behandelbare Algorithmen Beispiel: lineare Suche

O(log(n)) : logarithmische Algorithmen Extrem effizient Beispiel: binäre Suche

O(1) : Klasse aller konstanten Algorithmen Laufzeit unabhängig von Datengrösse

Komplexitätsklassen

Komplexitätsklassen

noch praktikabelnicht mehr praktikabel

Komplexität von Suchalgorithmen Bei der Linearen Suche ist es egal, ob der Datenbestand

schon sortiert ist, oder nicht: n Datenzugriffe für eine erfolglose Suche (worst case) 1 Datenzugriff im best case (sehr unwahrscheinlich) im Mittel (average case) n/2 Dateizugriffe

Lineare Suche: O(n) Die Binäre Suche funktioniert nur mit sortierten Daten:

kann iterativ oder rekursiv implementiert werden 1 Listenspaltung mehr für doppelte Länge

Binäre Suche: O(log(n)) Interpolationssuche: O(log(log(n))