TuH2 java

Aus ProgrammingWiki

Archivierte Version vom 2009-04-17T11:57:00+00:00. Aktuelle Version

Zurück zur Hauptseite Teile und Herrsche 2

Java - Variante zu Teile und Herrsche 2

Um mit den Java Beispielen experimentieren zu können findet ihr folgende vordefinierte Datenstrukturen und Hilfsmethoden:

int[] erzeugeFeld(int length) {
	int[] field = new int[length];
	for (int i = 0; i < field.length; i++) {
		field[i] = i; 
	}
	return field;
}

//Ein Array für Testzwecke

int[] myArray = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

Betrachten wir nun die iterative Variante der binären Suche:

// Die eigentliche Such Methode, diese Liefert die Position an der das Element zu finden ist,
// das Ergebnis -1 signalisiert das das Element nicht enthalten ist!
int binSuch(int[] field, int x){
		int start = 0;
		int ende = field.length-1;
		int mitte = (start + ende)/2;
		
		while(start <= ende && field[mitte] != x){
			if(field[mitte] < x){
				start = mitte + 1;
			}else ende = mitte - 1;
			mitte = (ende + start)/2;
		} 
		
		if(start > ende){
			return -1;
		}else return mitte;
		
	}

<eval> System.out.print(5);</eval>

//binSuch(myArray, 4);

Um nun eine Aussage über die Effiziens treffen zu können, betrachten wir das Verhalten der Variablen, welche für die Positionen im zu durchsuchenden Feld verantwortlich sind.

\begin{array}{lcl} \text{Start} & = & 0 \\ \text{Ende} & = & Feldleange - 1 \\ \text{Feldleange zu Begin} & = & \text{start} + \text{Ende} \\ \text{Mitte des Feldes} & = & \dfrac{\text{Start} + \text{Ende}}{2} \\ \end{array}

Das Intervall ändert sich wie folgt:

\begin{array}{lcl} \text{Neue Feldlaenge} & = & \text{Ende} - \text{Start} + 1 \\ & = & \text{Ende} - (\text{Mitte} + 1) + 1 \\ & = & \text{Ende} - \text{Mitte des Feldes} \\ & = & \text{Ende} - \dfrac{\text{Start} + \text{Ende}}{2} \\ & = & \dfrac{2 \cdot \text{Ende}}{2} - \dfrac{\text{Start} + \text{Ende}}{2} \\ & = & \dfrac{\text{Ende} - \text{Start}}{2} \end{array}

Kurz gefasst ändert sich das Intervall in jedem Durchlauf der Schleife von der Länge n auf \dfrac{n - 1}{2}. Was heist das nun konkret? Wir haben 2 Intervalle zwischen denen es sich jeweils zu entscheiden gilt und dafür brauchen wir k durchläufe. Somit haben 2^k Operationen um n Elemente zu durchsuchen.

2^k = n Das lässt sich mit dem Logarithmus zur Basis 2 errechnen.

\log_{2} n = k \curvearrowright \mathcal{O}(\log_2 n) 
Dieses Ergebnis zaubert ein grinsen ins Gesicht, 
da ein Algorithmus mit logarithmischer Laufzeit äußerst Effizient arbeitet.

Den Unterschied zwischen linearem und logarithmischen Aufwand kann man sich mittels empirischer Analyse vor Augen halten, dazu findet ihr zwei Aufgaben auf der Übungsseite http://www.michael-hielscher.de/wiki/index.php/Aufgaben - TuH2#Aufgaben zur Bin.C3.A4ren Suche. Für den direkten Vergleich haben wir hier die notwendige Funktion für die sequenzielle Suche zu Verfügung gestellt.

int sequenzSuch(int[] field, int x){
		int element= -1;
		
		for(int i = 0; i < field.length; i++){
			if(field[i] == x) 
				element = i;
		}
		return element;
		
	}

Für die Interessierten, hier findet ihr noch die rekursive Variante in Java. Im Wikipedia Artikel zur binären Suche ist ein kleiner Fehler, hier ist die korrigierte Variante!

//Rekursive Variante
int binSuchRek(int [] field, int x, int start, int ende){
		int mitte = start + ((ende - start)/ 2);
		if(mitte >= field.length){
			return -1;
		}else if(field[mitte] == x){
			return mitte;
		}else if(field[mitte] < x ){
			return binSuchRek(field, x, mitte + 1, ende);
		}else 
			return binSuchRek(field, x, start, mitte - 1);
	}

<eval> System.out.print(binSuchRek(myArray, 20321, 0, myArray.length)); </eval>

Karatsuba in Java

Dies ist eine Mögliche Implementierung in Java: