Ich habe einem Freund den berühmten deterministischen linearen Zeitauswahlalgorithmus (Median des Medianalgorithmus) erklärt.
Die Rekursion in diesem Algorithmus ist (obwohl sehr einfach) ziemlich ausgefeilt. Es gibt zwei rekursive Aufrufe mit jeweils unterschiedlichen Parametern.
Ich habe versucht, andere Beispiele für solche interessanten rekursiven Algorithmen zu finden, konnte aber keine finden. Alle rekursiven Algorithmen, die mir einfallen könnten, sind entweder einfache Schwanzrekursionen oder einfaches Teilen und Erobern (wobei die beiden Aufrufe "gleich" sind).
Können Sie einige Beispiele für anspruchsvolle Rekursionen nennen?
algorithms
recursion
elektronaj
quelle
quelle
Antworten:
Meine Lieblingswiederholung taucht in ausgangssensitiven Algorithmen zur Berechnung konvexer Hüllen auf, zuerst von Kirkpatrick und Seidel , aber später von anderen wiederholt. Es sei die Zeit zum Berechnen der konvexen Hülle von n Punkten in der Ebene, wenn die konvexe Hülle h Eckpunkte hat. (Der Wert von h ist im Voraus nicht bekannt, abgesehen von der trivialen Grenze h ≤ n .) Der Kirkpatrick- und Seidel-Algorithmus liefert die Wiederholung T ( n , h ) = { O ( n ) ifT( n , h ) n h h h ≤ n
wobein1,n2≤3n/4undn1+n2=nundh1+h2=h.
Die Lösung ist . Dies ist ein wenig überraschend, da h nicht der Parameter ist, der gleichmäßig aufgeteilt wird. Tatsächlich tritt der schlimmste Fall der Wiederholung auf, wenn h 1 und h 2 beide ungefähr h / 2 sind ; wenn irgendwie magisch h 1 immer konstant ist, wäre die Lösung T ( n , h ) = O ( n ) .T( n , h ) = O ( n logh ) h h1 h2 h / 2 h1 T( n , h ) = O ( n )
Ich habe eine Variante dieser Wiederholung in einer meiner ersten Arbeiten zur Computertopologie verwendet : wo
quelle
Die Rekursion, die ich in meiner Arbeit "Ein linearer Zeitalgorithmus zur Berechnung des Voronoi-Diagramms eines konvexen Polygons" von Aggarwal et al. Verwendet habe, ist ebenfalls ziemlich kompliziert.
Ich werde Sie herausfinden lassen, warum der gesamte Algorithmus lineare Zeit benötigt.
quelle
Es gibt eine Variation des Medianwerts für das Wiederauffinden von Wiederholungen, die bei der Entfernungssuche mit Halbebenen auftreten. Die Wiederholung selbst ist von der Form
quelle
Es gibt eine Reihe von coolen rekursiven Algorithmen [1], [2] die bei der Vorhersage von RNA-Sekundärstrukturen verwendet werden. Ein RNA-Strang, der sich selbst überlassen bleibt, bildet mit sich selbst Basenpaare. Ein relativ einfaches Beispiel aus [3] berechnet die maximale Anzahl verschachtelter, gepaarter Basen, die ein RNA-String mit sich selbst bilden wird:
Optimale Computerfaltung großer RNA-Sequenzen mit Hilfe von Thermodynamik und Hilfsinformationen von M. Zuker, P. Stiegler (1981)
Ein dynamischer Programmieralgorithmus zur Vorhersage der RNA-Struktur mit Pseudoknoten von E. Rivas, SR Eddy (1999)
Schneller Algorithmus zur Vorhersage der Sekundärstruktur von einzelsträngiger RNA von R. Nussinov, AB Jacobson (1980)
quelle
Ich verstehe immer noch nicht wirklich, was Sie unter "raffinierter Rekursion" verstehen. Zum Beispiel ist der Rekursionsschritt im FFT-Algorithmus komplex!
Wenn Sie jedoch nach einer komplizierteren Rekursion suchen möchten , ist die gegenseitige Rekursion möglicherweise eine mögliche Antwort. Die gegenseitige Rekursion ist nützlich, wenn Sie mit funktionalen Programmiersprachen arbeiten . Die gegenseitige Rekursion ist das Hauptmerkmal von Parsern für rekursive Abstammung .
quelle
Die McCarthy 91 funktioniert auf Anhieb
und die Ackermann-Funktion
könnte als ungewöhnliche, wenn auch spielzeughafte, rekursive Funktionen gelten.
quelle