TuH2 java

Aus ProgrammingWiki

Archivierte Version vom 2009-04-16T14:30:50+00:00. Aktuelle Version

Java - Variante zu Teile und Herrsche 2

Um mit den Java Beispielen experimentieren zu können findet ihr folgende vordefinierte Datenstrukturen.

// 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};

Betrachten wir nun die iterative Variante der binären Suche. Dazu betrachten wir das Intervall in welchem gesucht wird und das Verhalten dessen Größe während der 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;
		
	}

Unsere Variablen für die Positionen im zu durchsuchenden Feld verantwortlich sind haben beim Start folgende Belegungen:

\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.

// die Sequenzielle Suche für den Vergleich
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;
		
	}


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


//karatsubas Multiplikation

import java.math.*;


public class Karatsuba_class {

	
	public 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);
	}
}

<eval> System.out.println("An welcher Stelle ist das Element zu finden? Position:" + binSuch(erzeugeFeld(10), 3)); </eval>