Advanced Java Day 7: Algorithmen und Performance-Optimierung

Ziel dieses Tages

Heute wirst du lernen:

• Such- und Sortieralgorithmen: binäre Suche, Quicksort, Mergesort
• Big-O-Notation und Zeit-/Speicherkomplexitätsanalyse
• Optimierung von Schleifen und Speicherverbrauch
• Verwendung von HashMap zur Performance-Verbesserung

Am Ende wirst du in der Lage sein, effiziente Algorithmen zu schreiben und ihre Performance in Java zu analysieren.

Schritt 1: Arrays sortieren

Verwende die eingebaute Arrays.sort() Methode für optimiertes Sortieren.

import java.util.Arrays;

int[] arr = {5, 2, 8, 1, 3};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]

Schritt 2: Suchen – Binäre Suche

Die binäre Suche findet effizient ein Element in einem sortierten Array.

int index = Arrays.binarySearch(arr, 3);
System.out.println("Index von 3: " + index);

Erklärung:

• Das Array muss sortiert sein
• Teilt den Suchbereich bei jedem Schritt in zwei Hälften → O(log n) Zeitkomplexität

Schritt 3: Algorithmus-Komplexität

Die Big-O-Notation beschreibt Zeit- und Speicherkomplexität.

• O(n) – lineare Zeit
• O(log n) – logarithmische Zeit (binäre Suche)
• O(n log n) – effiziente Sortieralgorithmen wie Mergesort/Quicksort
• O(n²) – verschachtelte Schleifen / naive Algorithmen

Schritt 4: Schleifen und Speicher optimieren

• Vermeide unnötige Berechnungen in Schleifen
• Wiederverwende Objekte, um Speicherverbrauch zu reduzieren
• Bevorzuge HashMap-Zugriffe statt linearer Suchen bei Schlüssel-Wert-Daten

Schritt 5: HashMap für Performance

import java.util.*;

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);

System.out.println(map.get("Bob")); // 30

Übung

int[] arr = {5, 2, 8, 1, 3};
Arrays.sort(arr); // Eingebaute optimierte Sortierung
System.out.println(Arrays.toString(arr));

Aufgabe

Implementiere eine binäre Suche in einem sortierten Array und analysiere die Zeitkomplexität.

Schritte:

• Sortiere das Array, falls es nicht sortiert ist
• Implementiere eine binäre Suchmethode
• Gib den Index des gesuchten Elements zurück oder -1, falls es nicht gefunden wird
• Analyse des Algorithmus → O(log n)

Beispiel:

import java.util.Arrays;

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;

            if(arr[mid] == target) return mid;
            else if(arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 3};
        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr));

        int index = binarySearch(arr, 3);
        System.out.println("Index von 3: " + index); // 2
    }
}