TuH2 java

Wiki-Quelltext dieser Seite.

<language>Java</language>
Zurück zur Hauptseite [[Teile und Herrsche 2]]

<language>Java</language>
<language>Java</language>
==Java - Variante zu Teile und Herrsche 2==

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

<code>


</code>


<code>
// Eine Hilfe um mal schnell ein Array beliebiger Länge, zu füllen
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, 
100, 150, 165, 180, 200, 1000, 1500, 1600, 1700, 20000};
</code>

Betrachten wir nun die ''iterative Variante'' der ''binären Suche'':
<code>
// 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;
		
	}
</code>
<eval>
binSuch(myArray, 4);
</eval>

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. 

<math>
\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}
</math>

Das Intervall ändert sich wie folgt:

<math>
\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}
</math>

Kurz gefasst ändert sich das Intervall in jedem Durchlauf der Schleife von der Länge ''n'' auf <math>\dfrac{n - 1}{2}</math>. 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 <math>2^k</math> Operationen um ''n'' Elemente zu durchsuchen.

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

 <math>\log_{2} n = k \curvearrowright \mathcal{O}(\log_2 n)</math> 
 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.
<code>	
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;
		
	}
</code>

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!
<code>
//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);
	}

</code>

==Karatsuba in Java==

Dies ist eine Mögliche Implementierung in Java:

<code>
BigInteger karatsuba (BigInteger x, BigInteger y)
	{
		int n = Math.max(x.bitLength(),y.bitLength());
		if (n <= 1) return x.multiply(y);
		
		n=n /2;
		BigInteger xH = x.shiftRight(n);
		BigInteger xL = x.subtract (xH.shiftLeft(n));
		BigInteger yH = y.shiftRight (n);
		BigInteger yL = y.subtract (yH.shiftLeft(n));
		
		BigInteger p1 = karatsuba(xH, yH);
		BigInteger p2 = karatsuba(xL, yL);
		BigInteger p3 = karatsuba (xL.add(xH), yL.add(yH));
		
		return p1.shiftLeft(2*n).add(p3.subtract (p1).subtract (p2).shiftLeft(n)).add(p2);
	}
}
</code>

<eval>	

</eval>