Divide-and-Conquer-Algorithmus
Ein sehr beliebtes algorithmisches Paradigma, ein typischer Divide-and-Conquer-Algorithmus löst ein Problem mit den folgenden drei Schritten:
- Teilen: Zerlege das gegebene Problem in Unterprobleme gleichen Typs.
- Erobern: Diese Teilprobleme rekursiv lösen
- Kombinieren: Die Antworten angemessen kombinieren
Nachfolgend einige Standardalgorithmen, die Divide-and-Conquer-Algorithmen sind:
1 – Binäre Suche ist ein Suchalgorithmus. In jedem Schritt vergleicht der Algorithmus das Eingabeelement x mit dem Wert des mittleren Elements im Array. Wenn die Werte übereinstimmen, wird der Index der Mitte zurückgegeben. Andernfalls, wenn x kleiner als das mittlere Element ist, sucht der Algorithmus nach der linken Seite des mittleren Elements, sonst nach der rechten Seite des mittleren Elements.
2 – Quicksort ist ein Sortieralgorithmus. Der Algorithmus wählt ein Pivotelement, ordnet die Arrayelemente so an, dass alle Elemente, die kleiner als das gewählte Pivotelement sind, auf die linke Seite des Pivots wandern und alle größeren Elemente auf die rechte Seite. Abschließend sortiert der Algorithmus rekursiv die Subarrays links und rechts vom Pivotelement.
3 – Merge Sort ist ebenfalls ein Sortieralgorithmus. Der Algorithmus teilt das Array in zwei Hälften, sortiert diese rekursiv und führt schließlich die beiden sortierten Hälften zusammen.
4 – Closest Pair of Points: Das Problem besteht darin, das nächstgelegene Paar von Punkten in einer Punktmenge in der x-y-Ebene zu finden. Das Problem kann in O(n²)-Zeit gelöst werden, indem die Abstände jedes Punktpaares berechnet und die Abstände verglichen werden, um das Minimum zu finden. Der Divide-and-Conquer-Algorithmus löst das Problem in O(nLogn)-Zeit.
5 – Der Algorithmus von Strassen ist ein effizienter Algorithmus zur Multiplikation zweier Matrizen. Eine einfache Methode zur Multiplikation zweier Matrizen benötigt 3 verschachtelte Schleifen und ist O(n³). Strassen’s Algorithmus multipliziert zwei Matrizen in O(n².8974) Zeit.
6 – Cooley-Tukey Fast Fourier Transform (FFT) Algorithmus ist der gebräuchlichste Algorithmus für FFT. Es ist ein Divide-and-Conquer-Algorithmus, der in O(nlogn)-Zeit arbeitet.
7 – Karatsuba-Algorithmus für schnelle Multiplikation: Er erledigt die Multiplikation von zwei n-stelligen Zahlen in höchstens 3n^(log 3) einstelligen Multiplikationen im Allgemeinen (und genau n^(log3), wenn n eine Potenz von 2 ist). Er ist daher schneller als der klassische Algorithmus, der n² einstellige Produkte benötigt.
Zählendes Inversionsproblem
Wir werden ein Problem betrachten, das bei der Analyse von Ranglisten auftritt, die für eine Reihe von aktuellen Anwendungen wichtig werden. Zum Beispiel nutzen einige Websites im Web eine Technik, die als kollaboratives Filtern bekannt ist, bei der sie versuchen, Ihre Vorlieben (für Bücher, Filme, Restaurants) mit denen anderer Personen im Internet abzugleichen. Sobald die Website Personen identifiziert hat, die einen „ähnlichen“ Geschmack wie Sie haben – basierend auf einem Vergleich, wie Sie und diese Personen verschiedene Dinge bewerten – kann sie neue Dinge empfehlen, die diesen anderen Personen gefallen haben. Eine weitere Anwendung findet sich in Recta-Search-Tools im Web, die dieselbe Anfrage bei vielen verschiedenen Suchmaschinen ausführen und dann versuchen, die Ergebnisse zu synthetisieren, indem sie nach Ähnlichkeiten und Unterschieden zwischen den verschiedenen Rankings suchen, die die Suchmaschinen zurückgeben.
Ein Kernproblem bei Anwendungen wie dieser ist das Problem des Vergleichs zweier Rankings. Sie bewerten einen Satz von rt-Filmen, und dann konsultiert ein kollaboratives Filtersystem seine Datenbank, um nach anderen Personen zu suchen, die „ähnliche“ Bewertungen hatten. Aber was ist ein guter Weg, um numerisch zu messen, wie ähnlich die Bewertungen von zwei Personen sind? Es ist klar, dass eine identische Bewertung sehr ähnlich ist und eine komplett umgekehrte Bewertung sehr unterschiedlich ist; wir wollen etwas, das durch den mittleren Bereich interpoliert.
Betrachten wir den Vergleich Ihrer Bewertung und der Bewertung eines Fremden für dieselbe Menge von n Filmen. Eine natürliche Methode wäre, die Filme von 1 bis n gemäß Ihrer Rangfolge zu beschriften, dann diese Beschriftungen gemäß der Rangfolge des Fremden zu ordnen und zu sehen, wie viele Paare „außer der Reihe“ sind. Konkreter betrachten wir das folgende Problem. Uns ist eine Folge von n Zahlen a1, …, an gegeben; wir nehmen an, dass alle Zahlen eindeutig sind. Wir wollen ein Maß definieren, das uns sagt, wie weit diese Liste davon entfernt ist, in aufsteigender Reihenfolge zu sein; der Wert des Maßes sollte 0 sein, wenn a1 < a2 << an, und sollte zunehmen, wenn die Zahlen ungeordneter werden.
Ein natürlicher Weg, diesen Begriff zu quantifizieren, ist, die Anzahl der Invertierungen zu zählen. Wir sagen, dass zwei Indizes i < j eine Inversion bilden, wenn ai > aj, das heißt, wenn die beiden Elemente ai und aj „außer der Reihe“ sind. Wir werden versuchen, die Anzahl der Invertierungen in der Folge a1, …, an zu bestimmen.