Mehrheits-Elemente effizient finden: Naive vs. Boyer-Moore-Algorithmus

Ein häufiges Problem in der Algorithmenentwicklung besteht darin, das Mehrheits-Element in einem Array zu identifizieren – also den Wert, der mehr als die Hälfte der Elemente ausmacht. Diese Aufgabe lässt sich auf verschiedene Weisen lösen, wobei sich insbesondere zwei Methoden etabliert haben: ein naiver Ansatz mit einem Häufigkeitszähler und der optimierte Boyer-Moore-Algorithmus. Beide Lösungen erreichen eine lineare Laufzeit, unterscheiden sich jedoch deutlich in ihrem Speicherbedarf und ihrer Skalierbarkeit.

Der naive Ansatz: Häufigkeitszähler mit einer Map

Der einfachste Weg, das Mehrheits-Element zu finden, besteht darin, die Häufigkeit jedes Elements zu zählen und zu überprüfen, ob ein Element die Mehrheit der Array-Elemente ausmacht. Diese Methode nutzt eine Map, um die Zählungen zu speichern, und durchläuft das Array zweimal: einmal zum Zählen und einmal zur Überprüfung.

Der folgende Code zeigt eine typische Implementierung:

function majorityElement(nums) {
  const counts = new Map();
  for (const num of nums) {
    counts.set(num, (counts.get(num) ?? 0) + 1);
  }
  for (const [num, count] of counts) {
    if (count > nums.length / 2) return num;
  }
}

Der erste Schritt besteht darin, die Map zu initialisieren und die Häufigkeiten der Elemente zu erfassen. Dabei wird für jedes Element im Array nums überprüft, ob es bereits in der Map vorhanden ist. Falls nicht, wird es mit dem Zähler 1 angelegt. Andernfalls wird der bestehende Zähler um eins erhöht. Dieser Schritt läuft in O(n) Zeit, da jedes Element genau einmal verarbeitet wird.

Im zweiten Schritt wird die Map durchlaufen, um das Element mit der höchsten Häufigkeit zu finden. Da die Aufgabenstellung garantiert, dass ein Mehrheits-Element existiert, kann die Suche beendet werden, sobald ein Element mit einer Häufigkeit größer als n/2 gefunden wird. Auch dieser Schritt benötigt O(n) Zeit, sodass die Gesamtlaufzeit bei O(n) liegt.

Der Speicherbedarf dieses Ansatzes entspricht der Anzahl der eindeutigen Elemente im Array, da die Map proportional zur Anzahl der verschiedenen Werte wächst. In ungünstigen Fällen kann dies zu einem Speicherbedarf von O(n) führen.

Der optimierte Ansatz: Boyer-Moore-Mehrheitsvotum-Algorithmus

Der Boyer-Moore-Algorithmus, entwickelt 1981 von Robert S. Boyer und J Strother Moore, bietet eine effizientere Lösung mit konstantem Speicherbedarf und linearer Laufzeit. Der Algorithmus nutzt die Eigenschaft, dass das Mehrheits-Element durch eine Art „Vertrauensvotum“ identifiziert werden kann: Jedes Vorkommen des Mehrheits-Elements erhöht das Vertrauen, während andere Elemente es verringern.

Die Implementierung ist denkbar einfach:

function majorityElement(nums) {
  let candidate = null;
  let count = 0;

  for (const num of nums) {
    if (count === 0) candidate = num;
    count += num === candidate ? 1 : -1;
  }

  return candidate;
}

Der Algorithmus durchläuft das Array nur einmal und verwendet zwei Variablen: candidate für den aktuellen Kandidaten und count als Vertrauenszähler. Zu Beginn ist der Kandidat null und der Zähler auf 0 gesetzt. Für jedes Element im Array wird überprüft, ob der Zähler bei 0 liegt. Ist dies der Fall, wird der aktuelle Kandidat auf das aktuelle Element gesetzt. Anschließend wird der Zähler angepasst: Steht das aktuelle Element für den Kandidaten, wird der Zähler um 1 erhöht; andernfalls um 1 verringert.

Diese Logik kann mit einem einfachen Beispiel veranschaulicht werden. Betrachten wir das Array [2, 4, 2, 2, 4, 4, 4]. Der Algorithmus durchläuft die Elemente wie folgt:

• 2: Kandidat wird 2, Zähler = 1
• 4: Zähler sinkt auf 0
• 2: Kandidat wird 2, Zähler = 1
• 2: Zähler steigt auf 2
• 4: Zähler sinkt auf 1
• 4: Zähler sinkt auf 0
• 4: Kandidat wird 4, Zähler = 1

Am Ende des Durchlaufs ist der Kandidat 4, was dem Mehrheits-Element entspricht. Der Algorithmus benötigt nur O(1) Speicherplatz, da lediglich zwei Variablen verwendet werden, und erreicht eine Laufzeit von O(n).

Vergleich der Ansätze: Leistung und Skalierbarkeit

Beide Ansätze erzielen eine Laufzeit von O(n), da sie das Array jeweils einmal durchlaufen. Der entscheidende Unterschied liegt im Speicherbedarf: Während der naive Ansatz mit der Map einen linearen Speicherbedarf von O(n) hat, kommt der Boyer-Moore-Algorithmus mit konstantem Speicher aus. Dies macht ihn besonders für große Datensätze oder ressourcenbeschränkte Umgebungen attraktiv.

In der Praxis eignet sich der Boyer-Moore-Algorithmus daher besser für Anwendungen, bei denen Speichereffizienz entscheidend ist. Der naive Ansatz bleibt jedoch eine verständliche und leicht umsetzbare Lösung für kleinere Datensätze oder für Entwickler, die eine intuitive Herangehensweise bevorzugen.

Die Wahl des richtigen Algorithmus hängt somit von den spezifischen Anforderungen des Projekts ab. Während der naive Ansatz durch seine Einfachheit besticht, überzeugt der Boyer-Moore-Algorithmus durch seine Effizienz und Skalierbarkeit.

In den kommenden Tagen werden weitere algorithmische Herausforderungen und Lösungsansätze vorgestellt – bleiben Sie dran für neue Einblicke in die Welt der Algorithmen.