Big-O-Grundlagen

Big-O ist ein Werkzeug, mit dem du abschätzt, ob Code bei größeren Datenmengen noch sinnvoll skaliert. In Android-Apps geht es dabei nicht um abstrakte Theorie, sondern um konkrete Wirkung: Bleibt eine Liste flüssig, reagiert der Screen schnell, und verbraucht dein Code nur so viel Speicher, wie für die Aufgabe nötig ist?

Was ist das?

Big-O beschreibt die Wachstumsrate eines Algorithmus. Du fragst nicht: „Wie viele Millisekunden dauert dieser Code auf meinem Gerät?“ Du fragst: „Wie verändert sich der Aufwand, wenn aus 10 Elementen 1.000 oder 100.000 werden?“ Genau diese Denkweise ist für Android wichtig, weil Nutzer sichtbare Datenmengen direkt spüren: Kontakte, Chat-Nachrichten, Suchergebnisse, Offline-Listen, lokale Datenbankeinträge oder UI-State in Compose.

Die wichtigsten Begriffe sind Zeitkomplexität und Speicherkomplexität. Zeitkomplexität beschreibt, wie viele Arbeitsschritte mit der Eingabegröße wachsen. Speicherkomplexität beschreibt, wie viel zusätzlicher Speicher benötigt wird. Die Eingabegröße wird oft als n bezeichnet. n kann eine Liste von Nachrichten sein, eine Anzahl von Dateien, eine Menge von Datenbankzeilen oder die Zahl der sichtbaren UI-Elemente.

Typische Big-O-Klassen sind leicht zu merken. O(1) bedeutet: Der Aufwand bleibt gleich, unabhängig von der Datenmenge. Ein Zugriff auf ein Element per Schlüssel in einer Map ist meistens so ein Fall. O(n) bedeutet: Der Aufwand wächst ungefähr linear. Wenn du eine Liste einmal durchläufst, ist das typisch. O(n²) bedeutet: Für jedes Element gehst du wieder über viele oder alle Elemente. Das wird schnell teuer. Bei 100 Elementen sind es grob 10.000 Vergleiche, bei 10.000 Elementen bereits sehr viele Millionen.

Du brauchst dafür am Anfang keine formale Mathematik. Baue dir zuerst ein mentales Modell: Zähle Schleifen, erkenne verschachtelte Schleifen, achte auf wiederholte Suche in Listen und unterscheide einmalige Kosten von Kosten, die bei jedem Frame, jeder Eingabe oder jedem Recompose auftreten.

Wie funktioniert es?

Big-O ignoriert konstante Faktoren und kleine Details. Wenn ein Code eine Liste zweimal durchläuft, ist das trotzdem O(n), nicht O(2n). Wenn eine Methode vor der Schleife noch drei feste Prüfungen macht, bleibt es O(n). Diese Vereinfachung ist nützlich, weil sie dich auf die Skalierung konzentriert.

Im Android-Alltag musst du Big-O besonders dort beachten, wo Code häufig oder mit sichtbaren Daten läuft. Beispiele sind LazyColumn-Daten, Suchfilter, Sortierungen, Diffing von Listen, Mapping zwischen Datenbankmodellen und UI-Modellen, Validierung in Formularen oder Berechnungen in einem ViewModel. Ein ViewModel ist oft ein guter Ort, um solche Arbeit auszulagern, weil der Screen dadurch klarer bleibt und du die Logik besser testen kannst. Trotzdem wird langsamer Code nicht automatisch gut, nur weil er im ViewModel liegt.

Compose macht das Thema zusätzlich sichtbar. Wenn du in einer Composable-Funktion bei jeder Recomposition eine große Liste filterst oder sortierst, kann ein eigentlich akzeptabler O(n log n)- oder O(n)-Schritt plötzlich störend werden, weil er zu oft ausgeführt wird. Die Frage lautet dann nicht nur „Wie teuer ist diese Operation?“, sondern auch „Wie oft läuft sie?“ Ein linearer Durchlauf über 5.000 Elemente kann in Ordnung sein, wenn er nach dem Laden einmal passiert. Derselbe Durchlauf kann schlecht sein, wenn er bei jeder Texteingabe, jedem State-Update oder jedem Frame erneut startet.

Speicherkomplexität ist ähnlich praktisch. Wenn du eine Liste filterst, erzeugst du oft eine neue Liste. Das ist zusätzlicher Speicher, meist O(n). Das ist nicht automatisch falsch. Häufig ist eine klare, unveränderliche Liste für UI-State genau richtig. Aber wenn du mehrere große Zwischenlisten erzeugst, etwa erst map, dann filter, dann sortedBy, solltest du wissen, dass du nicht nur CPU-Zeit, sondern auch Speicher und Garbage Collection belastest. Auf schwächeren Geräten oder bei großen Datenmengen kann das sichtbar werden.

Big-O ersetzt keine Messung. Es sagt dir, wo du genauer hinschauen solltest. Wenn du O(n²) in Code erkennst, der mit Nutzerdaten wächst, ist das ein Warnsignal. Wenn du O(n) in Code erkennst, der selten läuft und nur kleine Listen verarbeitet, ist das meist unproblematisch. Gute Android-Architektur hilft dir hier, weil Datenfluss, Zuständigkeiten und Testbarkeit klarer werden. Wenn du weißt, wo Daten transformiert werden, kannst du Komplexität gezielt prüfen.

In der Praxis

Stell dir vor, du baust eine Chat-Übersicht. Du hast eine Liste von Nachrichten und eine Liste blockierter Nutzer. Du möchtest nur Nachrichten anzeigen, deren Absender nicht blockiert ist. Eine naive Lösung sieht harmlos aus, kann aber teuer werden.

Kotlin-Beispiel:

data class Message(
    val id: String,
    val senderId: String,
    val text: String
)

fun visibleMessagesSlow(
    messages: List<Message>,
    blockedUserIds: List<String>
): List<Message> {
    return messages.filter { message ->
        message.senderId !in blockedUserIds
    }
}

Der Code ist gut lesbar, aber die Komplexität hängt von beiden Listen ab. Für jede Nachricht sucht !in blockedUserIds in einer List. Diese Suche ist linear. Wenn du m Nachrichten und b blockierte Nutzer hast, liegt der Aufwand ungefähr bei O(m * b). Wenn beide Größen wachsen, fühlt sich das wie ein verschachtelter Durchlauf an.

Eine bessere Variante nutzt ein Set, weil die Mitgliedschaftsprüfung dort im Durchschnitt sehr schnell ist.

fun visibleMessagesFast(
    messages: List<Message>,
    blockedUserIds: List<String>
): List<Message> {
    val blocked = blockedUserIds.toSet()

    return messages.filter { message ->
        message.senderId !in blocked
    }
}

Jetzt baust du einmal ein Set auf. Das kostet O(b) Zeit und zusätzlichen Speicher. Danach filterst du die Nachrichten mit ungefähr O(m). Zusammen ist das O(b + m) statt O(m * b). Für kleine Datenmengen merkst du vielleicht keinen Unterschied. Für echte Nutzerlisten kann es entscheidend sein, besonders wenn der Code bei jeder Suche oder bei jedem neuen UI-State läuft.

Die Entscheidungsregel ist: Wenn du in einer Schleife immer wieder in einer Liste suchst, prüfe, ob eine Set- oder Map-Struktur besser passt. Set eignet sich für schnelle Enthalten-Prüfungen. Map eignet sich, wenn du Objekte schnell über eine ID finden willst. Diese Regel ist im Android-Code sehr häufig nützlich, etwa beim Zuordnen von UI-Modellen, beim Markieren ausgewählter Elemente oder beim Abgleich lokaler Daten mit Serverdaten.

Eine typische Stolperfalle ist, Big-O nur am Codeausschnitt zu betrachten und den Aufrufkontext zu vergessen. Diese Funktion ist deutlich besser, wenn sie einmal im ViewModel ausgeführt wird, nachdem neue Daten geladen wurden. Sie ist weniger gut, wenn du sie direkt in einer Composable-Funktion bei jeder Recomposition aufrufst. In Compose solltest du teure Ableitungen möglichst kontrolliert ausführen, etwa im ViewModel, in einem Flow-Operator oder mit geeigneter Memoization über remember, wenn die Daten wirklich UI-lokal sind.

Auch Tests können helfen. Du musst keinen Performance-Benchmark für jede Hilfsfunktion schreiben. Aber du kannst mit realistischen Testdaten prüfen, ob deine Funktion bei 10, 1.000 und 50.000 Elementen noch brauchbar bleibt. In einem Code-Review kannst du gezielt fragen: „Wächst dieser Code linear oder quadratisch?“ und „Läuft das einmal oder sehr oft?“ Diese Fragen sind oft wertvoller als eine perfekte Big-O-Notation.

Achte außerdem auf Datenbankgrenzen. Wenn du mit Room oder einer anderen lokalen Datenquelle arbeitest, ist es oft besser, Filterung und Sortierung dort auszuführen, wo die Daten effizient abgefragt werden können. Es ist meist keine gute Idee, eine riesige Tabelle vollständig in den Speicher zu laden, nur um danach in Kotlin einfache Filter anzuwenden. Big-O betrachtet zwar den Algorithmus, aber Android-Qualität entsteht auch durch die richtige Stelle im Datenfluss.

Fazit

Big-O hilft dir, Android-Code nicht nur für den aktuellen Beispieldatensatz zu bewerten, sondern für wachsende Nutzerdaten. Prüfe beim nächsten Listen-, Such- oder Mapping-Code bewusst, ob du O(1), O(n) oder O(n²) erkennst, und frage dich, wie oft der Code läuft. Erstelle kleine Tests mit größeren Listen, beobachte den Debugger oder Profiler, und sprich Komplexität im Code-Review offen an. So lernst du, Performance-Probleme früh zu sehen, bevor sie als ruckelnde UI oder unnötiger Speicherverbrauch bei deinen Nutzern ankommen.