Listensortierung als reines mathematisches Problem formulieren

Es gibt mehrere mathematische Studien zu Sortieralgorithmen, ausgehend von Knuths Bibel [3] zu diesem Thema. Das Handbook [2] bietet auch einen rigorosen Ansatz für Algorithmen und gibt eine Reihe von Referenzen.

Ich werde nicht versuchen, die 790 Seiten von Knuths Band in wenigen Zeilen zusammenzufassen, aber hier sind einige Punkte, die für einen mathematischen Ansatz zum Sortieren zu berücksichtigen sind.

1. Sie erhalten eine völlig geordnete$n$-Elementsatz$S = \{a_1 < a_2 < \ldots < a_n\}$. Am Anfang steht das zu sortierende Array$(a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)})$, Wo$\sigma$ist eine Permutation von$\{1, \ldots, n\}$.
2. Normalerweise misst die (Zeit-)Komplexität die Anzahl der Vergleiche, die zum Sortieren des Arrays erforderlich sind. Kein anderer Parameter wird berücksichtigt. So sind Vergleiche der Form „ist$a < b$?" sind die einzigen grundlegenden Operationen, die berücksichtigt werden. Auf diese Weise ist das Problem völlig unabhängig von der Implementierung.
3. Es gibt mehrere Komplexitätsmaße, einschließlich Zeitkomplexität (einschließlich Worst-Case-Zeitkomplexität ), durchschnittliche Zeitkomplexität , Raumkomplexität (die die von Ihrem Algorithmus verwendete Speichermenge misst), ganz zu schweigen von der neueren amortisierten Rechenkomplexität . In Ihrer Frage scheinen Sie an der Zeitkomplexität im schlimmsten Fall interessiert zu sein.
4. [BEARBEITEN] Die minimale Anzahl von Vergleichen, die zum Sortieren benötigt werden$n$Elemente ist die OEIS-Sequenz A036604 . Siehe [4] für einen aktuellen Beitrag zu diesem Thema.

In einem Kommentar behaupten Sie das

wenn die Liste ein Array von Zahlen im Computerspeicher ist, Verschieben des Elements in Position$j$in Position$i$erfordert das Verschieben einer Menge Dinge im Speicher (weil viele Elemente im Array um eine Position verschoben werden müssen).

Das ist nicht wahr. Sie können zum Beispiel mit Zeigern in C (oder Referenzen in Java) herumspielen. Darüber hinaus basieren eine Reihe von Sortieralgorithmen auf dem Vertauschen zweier Positionen$i$Und$j$, die keine Verschiebung benötigt. Um sich mit Algorithmen vertraut zu machen, ist [1] eine der Standardreferenzen, aber es gibt noch viele andere.

[1] Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. und Stein, Clifford. Einführung in Algorithmen. Dritte Edition. MIT Press, Cambridge, MA, 2009. xx+1292 S. ISBN: 978-0-262-03384-8

[2] Gonnet, Gaston H. und Baeza-Yates, R., Handbuch der Algorithmen und Datenstrukturen . 2. Aufl. (Englisch) International Computer Science Series. Bonn etc.: Addison-Wesley Publishing Company. XIV, 424 S. (1989).

[3] Knuth, Donald E. Die Kunst der Computerprogrammierung . Vol. 3. Sortieren und Suchen . Zweite Ausgabe. Addison-Wesley, Reading, MA, 1998. xiv+780

[4] Peczarski, Marcin (3. August 2011). Auf dem Weg zur optimalen Sortierung von 16 Elementen . Acta Universitatis Sapientiae 4 (2): 215–224

Allgemeine Probleme mit der Angabe vergleichsbasierter Algorithmen als reines mathematisches Problem

Schauen Sie sich die Diskussionen über vergleichsbasierte Algorithmen an (eine Klasse von Algorithmen, die die meisten Sortieralgorithmen umfasst) [0]. Es ist ein guter Ausgangspunkt für eine Formalisierung, auch wenn die Definition dieser Algorithmen in der Literatur zu vage bleibt, um einen reinen Mathematiker zufrieden zu stellen.

Ihre Frage, was einen Algorithmus ausmacht und was die grundlegenden Operationen sind, wird in [0] und [4] beantwortet. Für imperative Programmiersprachen sind grundlegende Operationen typischerweise die Operationen auf niedrigerer Ebene, die von Konstrukten auf höherer Ebene ausgeführt werden (wie Schleifen, Bedingungen usw.). Diese können von vornherein bei der Angabe einer Sprache angegeben werden.

Eine gängige „Definition“ ist, dass vergleichsbasierte Algorithmen Algorithmen sind, bei denen jede grundlegende Operation (Austausch, Zuweisung usw.) auf einem vorherigen Vergleich (oder einer Folge von Vergleichen) basieren muss. Diese Definition von vergleichsbasierten Algorithmen hat eine Lücke (nicht die einzige.) Was wirklich zählt, ist, dass die grundlegenden Operationen auf der Grundlage des transitiven Abschlusses des Ergebnisses früherer Vergleiche entschieden werden.

Ein zweites zu untersuchendes Problem ist die Beziehung zwischen vergleichsbasierten Algorithmen und Teilauftragsproduktion (dies hilft bei Ihrer Frage zu den unteren Grenzen). In Lehrbüchern wird dies selten erwähnt. Partial Order Production ist (neben anderen Aspekten) ein Ansatz zur Festlegung allgemeinerer Untergrenzen für vergleichsbasierte Algorithmen, die keine Sortieralgorithmen sein müssen[1]. Die Teilauftragsproduktion beinhaltet das unten diskutierte topologische Sortiermodell.

Ein drittes Problem (für Mathematiker) ist die Spezifikation der beteiligten Operationen. Die engste Präsentation wäre Knuths Band III über das Sortieren und Suchen (The Art of Computer Programming, Band III), eine ausgezeichnete Ressource, die bereits stromaufwärts erwähnt wurde. Selbst bei dieser Genauigkeit wird ein reiner Mathematiker vom Detail weg abstrahieren wollen, was eine Herausforderung für sich ist. Siehe unten über die Spannung zwischen Code und Mathematik.

Ein viertes Problem ist die Unterscheidung zwischen impliziten Datenstrukturen [2] und expliziten. Für den Fall der Haufensortierung wird typischerweise die Datenstruktur der Liste (Array) verwendet. Die implizite Datenstruktur ist jedoch die eines Heaps, die der Programmierer beim Schreiben des Codes im Kopf hat, obwohl die Heap-Datenstrukturen nicht explizit im Code verwendet werden (es werden nur Arrays verwendet).

Schließlich gibt es noch den Status der Algorithmenanalyse im Allgemeinen, der eine Mischung aus reiner und angewandter Mathematik bleibt. Viele Techniken sind auf den betrachteten Algorithmus zugeschnitten. Es gibt kein einheitliches Vorgehen. Knuths TAOCP Vol III hätte die detailliertesten Informationen zu einem formalen Ansatz (sei es mit Methoden, die immer noch auf verschiedene Algorithmen zugeschnitten sind). Flajolets Arbeit an der Algorithmusanalyse kann als ein Weg zur Vereinheitlichung angesehen werden (obwohl die verwendeten Operationen manchmal von den üblicherweise in der Informatik verwendeten Operationen abweichen, um sicherzustellen, dass Erzeugungsfunktionen angewendet werden können. Dies führt wie immer zu einer Spannung zwischen Informatik und Mathematik Schuhhorn-Code, um die Mathematik anzupassen). Ich habe ein Buch zu diesem Thema geschrieben, das sich auf eine vereinheitlichende Theorie konzentriert und näher an der Standardberechnung bleibt [3].

Es bleibt noch viel zu tun, um die Theorie auf die richtige Abstraktionsebene zu bringen, um die Erwartungen eines reinen Mathematikers zu erfüllen (Ihre ursprüngliche Frage, glaube ich). Das Spiel soll Klarheit und Präzision ausbalancieren und eine Vereinheitlichung erreichen, während die eigentlichen Ziele der Disziplin (in diesem Fall CS) respektiert werden.

Es scheint, dass sich Ihre Fragen auch darauf beziehen, was auf Hardwareebene passiert. Ich würde A Guide to Experimental Algorithmics [4] empfehlen. Dieser Bereich ist ein Mittelweg zwischen rein experimenteller algorithmischer Analyse (zu maschinenabhängig) und theoretischer Analyse (maschinenunabhängig, aber in gewisser Weise zu weit von der Praxis entfernt). Es verwendet Techniken, die einer kontrollierten Laborumgebung in der Informatik ähneln.

Die obigen Skizzen zeigen, warum die formale Definition vergleichsbasierter Algorithmen herausfordernd ist. Es kann getan werden. Zum Beispiel tut es [3] für eine eingeschränkte Klasse (die speziell darauf abzielt, modulares Average-Case-Timing zu realisieren). [1] vertritt die Ansicht, dass alle vergleichsbasierten Algorithmen Berechnungen haben, die (für Listen fester Größe$n$) können durch Entscheidungsbäume modelliert werden. [1] vertritt daher die Ansicht, dass die Algorithmen mit den Bäumen identifiziert werden (dh die Algorithmen zur Teilauftragsproduktion in [1] werden einfach als Entscheidungsbäume mit bestimmten Eigenschaften aufgefasst). Sobald dieser Sprung gemacht ist, entsteht der reine mathematische Kontext, basierend auf Entscheidungsbäumen und topologischen Sortierungen. Es umgeht Ihre Frage nach einem formalen Rahmen, in dem allgemeine vergleichsbasierte Berechnungen so formuliert sind, dass sie einen reinen Mathematiker (oder beispielsweise einen theoretischen Informatiker) zufrieden stellen. Ich glaube, dass es durchaus machbar ist, dh eine Logik sollte machbar sein, in der vergleichsbasierte Berechnungen erfasst werden. Ich kenne keine Referenz, die dies tut (und wäre interessiert, wenn jemand eine hat).

Ein Ausgangspunkt, um die reine mathematische Formulierung anzusprechen [1,3,5]

Der folgende Ansatz kann als rein mathematische Formulierung des Problems angesehen werden. Es ist verwandt mit Yaos Ansatz in [1] sowie dem Ansatz in [3], wo beide topologische Sortierungen verwenden, um vergleichsbasierte Berechnungen zu modellieren. Anstatt sich auf den Code zu konzentrieren, liegt der Fokus auf den Eingabe-Ausgabe-Funktionen, die mit den durchgeführten Operationen verbunden sind im Code (ein semantischer Ansatz).

Die Einsatzregel des Designers: transitive Schließung

Eine übliche Definition von vergleichsbasierten Algorithmen ist, dass jede Grundoperation (Austausch, Zuweisung usw.) auf einem vorherigen Vergleich oder einer Folge von Vergleichen basieren muss. Diese Definition hat eine unglückliche Lücke. Was wirklich zählt, ist, dass die Grundoperationen auf der Grundlage des transitiven Abschlusses des Ergebnisses früherer Vergleiche entschieden werden. Lassen$k \geq 2$.

Bei einem Sortieralgorithmus wie Bubble Sort ist jeder Austausch zwischen Listenelementen das direkte Ergebnis eines Vergleichs zwischen diesen beiden Elementen. Für Quicksort zwei Elemente$a, b$kann mit einem Schwenkelement verglichen werden$p$, und kann auf dieser Grundlage ausgetauscht werden$a > p$Und$p > b$wenngleich$a$Und$b$noch nie direkt verglichen. Der Austausch wird auf der Grundlage des transitiven Abschlusses der gewonnenen Informationen über die Anordnung der Elemente bis zu diesem Zeitpunkt der Berechnung durchgeführt. In diesem Stadium der Berechnung kennt der Algorithmusdesigner alle Ordnungsbeziehungen zwischen verglichenen Labelpaaren sowie alle legitim gefolgerten Ordnungsbeziehungen, dh erhalten durch transitiven Abschluss. Es ist diese Sammlung von Beziehungen, und nur diese Sammlung, die die Entscheidungen des Designers unterstützt, die Ausführung grundlegender Codeoperationen einzubeziehen.

Der Entwurf jedes vergleichsbasierten Algorithmus erfordert, dass nach jedem in der Berechnung durchgeführten Vergleich ein Austausch oder ein anderer grundlegender Berechnungsschritt auf der Grundlage der durch die vorherigen Vergleiche festgelegten Reihenfolge durchgeführt wird. Diese Reihenfolge betrifft den transitiven Abschluss aller Paare, für die die richtige Reihenfolge bestimmt wurde. Dies legt die Einsatzregeln für den Algorithmusdesigner fest, der den Algorithmus niemals dazu bringen kann, eine grundlegende Operation außerhalb dieses Kontexts auszuführen.

Beachten Sie, dass es für den Designer nicht erforderlich ist, Austauschvorgänge in Übereinstimmung mit einer bestimmten Reihenfolge vorzunehmen. Der Designer muss sicherstellen, dass der Algorithmus die richtigen Ausgaben erzeugt. Ob ausgeführte Swaps den Algorithmus diesem Ziel näher bringen oder nicht, ist eine Entscheidung, die getroffen werden muss, aber keine Entscheidung, die erzwungen wird. Einzige Voraussetzung ist, dass am Ende eine „Soll“-Ordnung erreicht wird (vorgegeben als Teil der Spezifikation für den Algorithmus). Um eine Zielreihenfolge vorzugeben, die am Ende erreicht werden muss, wird das topologische Sortiermodell eingeführt.

Bestellinformationen filtern und Daten entsprechend permutieren

Jeder Vergleich, der während einer vergleichsbasierten Berechnung durchgeführt wird, bestimmt, ob zwei Labels in der richtigen oder falschen Reihenfolge auftreten . Jeder Vergleich filtert ein zusätzliches Informationsbit aus den Daten heraus: 0 für ein Paar außerhalb der Reihenfolge und 1 für ein Paar in der richtigen Reihenfolge.

Wenn ein Vergleich zwischen zwei Labels durchgeführt wurde$a$Und$b$das festzustellen$a \leq b$In der linearen Reihenfolge auf Etiketten beziehen wir uns auf das Paar$(a,b)$als gefiltertes Paar . Falls$a \geq b$etabliert ist, beziehen wir uns auf das Paar$(b,a)$als gefiltertes Paar .

Die festgelegte Eingabereihenfolge

Für jede Ausführung eines vergleichsbasierten Algorithmus an einer Eingabe$I$und bei jedem Vergleich, der bei dieser Ausführung durchgeführt wird, ist die festgelegte Eingabereihenfolge (bis zu diesem Punkt in der Berechnung) die Teilreihenfolge, die durch Nehmen des transitiv-reflexiven Abschlusses der gefilterten Paare erhalten wird, die während der Berechnung bis einschließlich dieses Vergleichs erhalten werden.

Die Eingabereihenfolge ist die partielle Eingabereihenfolge, die erreicht wird, wenn die Ausgabe für erzeugt wird$I$, dh die festgelegte Eingabereihenfolge für den zuletzt durchgeführten Vergleich.

Bei der Ausführung eines vergleichsbasierten Algorithmus können zwei Etiketten ausgetauscht (oder unter Verwendung anderer grundlegender Operationen verschoben) werden. Ein Swap ist eine Permutation, die eine einzelne Transposition der Eingabedaten darstellt und zwei Labels austauscht.

Vergleichsbasierte Algorithmen werden ausgeführt von:

• (implizites) Filtern der Daten über Vergleiche und
• (explizites) Permutieren von Daten nur unter Verwendung von Swaps (oder anderen grundlegenden Operationen) an Paaren, die in der festgelegten Eingabereihenfolge enthalten sind.

Der Filterprozess

Der Filterprozess sammelt implizit mehr Informationen über die lineare Reihenfolge einer Eingabe auf Labels. Diese Informationen werden durch die festgelegte Eingabereihenfolge erfasst. Der Filterprozess partitioniert auch die Eingaben in Sätze, die die festgelegte Eingabereihenfolge erfüllen.

Betrachten Sie jede vergleichsbasierte Sortierung und jede Eingabeliste$L$von Größe$n$der Einfachheit halber verschiedene Elemente zu speichern. Einmal wird ein erster Vergleich durchgeführt, um die Reihenfolge zwischen zwei Listenelementen zu bestimmen$L[i]$Und$L[j]$mit$i < j$, werden die möglichen Eingaben, für die diese Entscheidung getroffen wird, halbiert (von$n!$Zu$\frac{n!}{2}$Listen). Diese Eingaben betreffen jetzt nur noch die Listen für die$L[i]< L[j]$ob dies das Ergebnis des Vergleichs war, oder die Listen für die$L[j] > L[i]$ansonsten.

Vergleichsbasierte Sortieralgorithmen sammeln nach und nach Informationen über Paarreihenfolgen, die in der etablierten Eingabereihenfolge für die Elemente einer Liste erfasst werden. An jedem Punkt der Berechnung, dh nach jedem Vergleich, kann diese Reihenfolge interpretiert werden, um die Eingangslisten herauszufiltern, die der bis dahin festgelegten Reihenfolge nicht genügen.

Der Prozess des Herausfilterns von Eingaben, die die etablierte Reihenfolge nicht erfüllen, ist implizit. Es ist nicht Teil des Codes. Es ist jedoch Teil des beabsichtigten Entwurfs des Programmierers für den Algorithmus.

Der Permutationsprozess

Der Permutationsprozess wird von jedem vergleichsbasierten Algorithmus ausgeführt, wie durch seinen Code bestimmt . Für jede Eingabe kann ein vergleichsbasierter Algorithmus eine Reihe von Austauschvorgängen (oder allgemeiner grundlegende Operationen) an Labelpaaren ausführen. Die Zusammensetzung dieser Swaps bildet eine Permutation, die die ursprüngliche Eingabe in eine Ausgabe umwandelt. An dieser Stelle konzentrieren wir uns ausschließlich auf vergleichsbasierte Sortieralgorithmen.

Nach jedem Vergleich hat jeder vergleichsbasierte Sortieralgorithmus die Möglichkeit, Datenetiketten zu permutieren, damit sie in die beabsichtigte sortierte Reihenfolge der Ausgabelisten passen. Beispielsweise listet if Elemente auf$L[i]$Und$L[j]$durch eine vergleichsbasierte Sortierung bestimmt werden, dass sie außerhalb der Reihenfolge auftreten, d. h$L[j]> L[i]$Wo$i<j$, dann kann ein Austausch vorgenommen werden, um ihre relative Reihenfolge in Übereinstimmung mit der zu berechnenden sortierten Ausgabe zu bringen.

Für jede vergleichsbasierte Sortierung hat der kombinierte Prozess der Eingabefilterung und Eingabepermutierung den folgenden Effekt:

• Zu dem Zeitpunkt, an dem eine Ausgabe berechnet wurde, wurden die möglichen Eingaben auf eine einzige Liste heruntergefiltert.

• Der vom Algorithmus auf dieser Eingabe durchgeführte Permutationsprozess, dh die Zusammenstellung der bis dahin auf der Eingabe durchgeführten Sammlung von Swaps, erzeugt die sortierte Ausgabe.

Dies führt natürlich zu dem folgenden mathematischen Modell, das "Quell"- und "Ziel"-Ordnungen für vergleichsbasierte Berechnungen erfasst.

Das topologische Sortiermodell

Das mathematische Modell

Das mathematische Modell für vergleichsbasierte Algorithmen [1] und [3] besteht aus zwei Teilen:

(a) Modellieren von Datenstrukturen als teilweise geordnete endliche Mengen;

(b) Modellieren von Daten auf diesen nach topologischen Sortierungen;

Aus dieser Sicht hat eine abstrakte Spezifikation eines Sortieralgorithmus einen Eingangszustand, der durch jede mögliche Permutation einer endlichen Menge von Elementen (dargestellt gemäß (a) und (b) durch eine diskrete, teilweise geordnete Menge zusammen mit ihren topologischen Sortierungen, gegeben ist gegeben durch alle Permutationen) und geben eine sortierte Liste von Elementen aus (dargestellt wiederum gemäß (a) und (b) durch eine linear geordnete endliche Menge mit ihrer eindeutigen topologischen Sortierung).

Beispiel 1: Die (ungeordneten) Eingabelisten der Größe 2 eines Sortieralgorithmus werden durch die topologischen Sortierungen einer diskreten Ordnung der Größe 2 über der Menge der Elemente modelliert$\{x_1,x_2\}$:

$$\{(x_1: 1,x_2:2),(x_1:2,x_2:1)\}$$

Die Funktionswerte$s(x_1) = 2$Und$s(x_2) = 1$von, sagen wir, der topologischen Sorte$s = (x_1:2,x_2:1)$(über der diskreten Ordnung der Größe 2) werden als Etiketten bezeichnet und entsprechen im Fall einer Listendatenstruktur den Elementen der Liste. Der Standort$i$eines Etiketts$a$wofür$s(x_i) = a$wird als Index des Labels bezeichnet und entspricht der Position eines Elements in einer Liste. Die Liste$(2,1)$enthält das Element 2 an Position 1 (also den Index von$x_1$) und das Element 1 an Position 2 (also der Index von$x_2$). Wir sagen, dass für diese topologische Sortierung der Index von Label 2 1 und der Index von Label 1 2 ist. Die 2! topologische Sorten$\{(x_1: 1,x_2:2),(x_1:2,x_2:1)\}$bestehen aus 2 Permutationen, die die ungeordneten Listen darstellen$(1,2)$Und$(2,1)$. Diese topologischen Sortierungen bilden die Wurzelzustände, in denen Listen der Größe 2 (mit unterschiedlichen Elementen) vorkommen können. Tatsächlich ist eine Liste der Größe 2 entweder sortiert, dargestellt durch$(1,2)$, oder umgekehrt sortiert, dargestellt durch$(2,1)$. Zusammen bilden diese topologischen Sorten den Zustandsraum . Ein Zustandsraum dient intuitiv dazu, die gleichmäßige Verteilung über die Daten darzustellen: jede der unendlich vielen möglichen Eingabelisten$(a,b)$der Größe 2 (mit unterschiedlichen Elementen) mit gleicher Wahrscheinlichkeit in einem der beiden Wurzelzustände des Zustandsraums auftritt. Diese Interpretation dient dazu, die traditionelle Komplexitätsanalyse von Algorithmen zu untermauern, die von einer Gleichverteilung ausgeht.

Beispiel 2: Triviale Art von Listen der Größe 2

Berechnungen werden topologische Sortierungen in neue topologische Sortierungen umwandeln. Alle Berechnungen basieren auf Vergleichen. Stellen Sie sich zum Beispiel einen Sortieralgorithmus vor, sei es ein sehr primitiver, der nur über Listen der Größe 2 arbeitet und einen einzigen Vergleich mit den beiden Elementen der Liste (den Labels der entsprechenden topologischen Sortierung) durchführt. Auf diesen Vergleich folgt ein Austausch der Etiketten, falls diese Etiketten nicht in Ordnung sind. Ein solcher Algorithmus verlässt die topologische Sortierung$(x_1: 1,x_2:2)$unverändert und transformieren die topologische Sortierung$(x_1:2,x_2:1)$über einen einzigen Swap zur topologischen Sortierung$(x_1:1,x_2:2)$. Das Sortieren in diesem Modell erzeugt die eindeutige topologische Sortierung über der linearen Ordnung.

Teil (a) der Modellbeschreibung legt fest, dass wir endliche Teilordnungen verwenden, um Datenstrukturen darzustellen. Diese Reihenfolge kann abhängig von der Implementierung implizit oder explizit in der Ausgangsdatenstruktur dargestellt werden. Beispielsweise kann im Fall einer Haldenbildung aus einer ungeordneten Eingabeliste die Berechnung die Halde explizit aufbauen, indem die Eingabeliste in eine binäre Baumdatenstruktur transformiert wird, die die Haldeneigenschaft erfüllt, und de facto eine Halde bildet. Alternativ kann der Algorithmus eine Eingabeliste nehmen und die Listendatenstruktur für seine Ausgaben beibehalten. Elemente der Eingabeliste werden an Ort und Stelle neu organisiert, dh es wird eine neue Liste erzeugt, deren Elemente einer Heap-Struktur genügen. Die diesem Heap zugrunde liegende Baumstruktur bleibt ein "impliziter" Teil der Implementierung. Der Algorithmus verwendet für alle Zwecke die vom Programmierer beabsichtigte Heap-Struktur, aber die Datenstruktur bleibt während der Berechnung jederzeit eine Liste. Dies Dies ist beispielsweise beim Heapify-Prozess im traditionellen (in-place) Heapsort der Fall. Wir bezeichnen in diesem Fall die Heap-Struktur als implizite Datenstruktur und die Listendatenstruktur als explizite Datenstruktur . Diese können übereinstimmen oder nicht, je nachdem von der Implementierung ab.In unserem Kontext modellieren Teilaufträge die implizite Datenstruktur.

Ein grundlegendes Beispiel für das Rechenmodell: Sortieralgorithmen

Wir veranschaulichen (a), (b) des Modells für einen Sortieralgorithmus, der über Größenlisten arbeitet$n$.

Für Sortieralgorithmen sind Eingaben Listendatenstrukturen, die durch endliche diskrete Ordnungen dargestellt werden. Die Elemente der Ordnung werden mit positiven ganzen Zahlen beschriftet, die aus einem linear geordneten Beschriftungssatz gezogen werden$\mathcal{L}$, was in diesem Fall die übliche lineare Ordnung der positiven ganzen Zahlen ist. Die einzige Anforderung an diese Kennzeichnung ist, dass ihre Kombination mit der diskreten Ordnung eine topologische Sortierung bildet.

Es ist möglich, mit Listen umzugehen, die sich wiederholende Elemente enthalten. Diese müssten durch topologische Sortierungen modelliert werden, für die die Bedingungen gelockert werden, um wiederholte Kennzeichnungen zu ermöglichen. Siehe [3] für eine Diskussion darüber, wie wiederholte Labels durch die Zuweisung zufälliger Tie-Breaker gehandhabt werden können. Es ist Standardpraxis in der algorithmischen Analyse, die Analyse in erster Instanz für Listen ohne doppelte Elemente durchzuführen – ein Ansatz, der hier gewählt wird.

Sortieralgorithmen transformieren daher topologische Sortierungen der diskreten Ordnung (Permutationen) in die eindeutige topologische Sortierung der linearen Ordnung (die sortierte Liste).

Sortieralgorithmen sind eine restriktive Art von vergleichsbasierten Algorithmen. Die Eingaben sind ungeordnete Größenlisten$n$die vorkommen in$n!$mögliche Zustände. Die Ausgaben erfolgen in genau einem Zustand, der sortierten Ausgabeliste$[1,2, 3, \ldots, n]$.

Wir betrachten allgemeinere vergleichsbasierte Algorithmen, die mit Eingaben und Ausgaben arbeiten, die keine Listendatenstruktur sein müssen.

Quelle und Ziel eines Algorithmus

Betrachten Sie eine Sequenz$\alpha = (\alpha_n)_n$von endlichen Posets der Größe$n$und eine Folge$\beta= (\beta_n)_n$von Verfeinerungen von$(\alpha_n)_n$, dh$\alpha_n$verfeinert die Reihenfolge$\beta_n$für jeden$n$. Das Paar$(\alpha,\beta)$wird eine Verfeinerung mit einer Quelle genannt $\alpha =(\alpha_n)_n$und ein Ziel $\beta = (\beta_n)_n$.

Ein Algorithmus$A$ erkennt die Verfeinerung $(\alpha,\beta)$falls:

die Eingaben der Größe$n$, als Menge betrachtet, bilden den Zustandsraum über der Quellordnung$\alpha$. Erinnern Sie sich daran für jeden endlichen Poset$\alpha$, der Zustandsraum$\Sigma(\alpha)$ist die Menge aller topologischen Sorten mit Labels in$\{1,\ldots,n\}$Wo$n = |\alpha|$.

die entsprechenden Ausgänge, als Menge betrachtet, bilden den Zustandsraum$\Sigma(\beta_n)$.

$\Sigma(\alpha_n)$wird als Quellraum bezeichnet (für Eingaben von size$n$).

$\Sigma(\beta_n)$wird als Zielraum bezeichnet (für Eingaben von size$n$).

Mit etwas Missbrauch der Terminologie: if$\alpha = (\alpha_n)_n$ist die Quelle eines solchen vergleichsbasierten Algorithmus$A$und wir berücksichtigen Größeneingaben$n$, Dann$\alpha_n$wird auch als „die Quelle“ bezeichnet.

Man kann einen vergleichsbasierten Algorithmus als einen Algorithmus betrachten, der grundlegende Operationen ausschließlich auf der Grundlage des transitiven Abschlusses früherer Vergleiche ausführt, Filterung und Permutation in jeder Stufe, so dass für eine gegebene Quelle$\alpha$und ein Verfeinerungsziel$\beta$, realisiert der Algorithmus die Verfeinerung. Alternativ kann man vom Code abstrahieren und sich ganz auf Entscheidungsbäume konzentrieren [1].

Beispiel: Für einen vergleichsbasierten Sortieralgorithmus$A$die Quelle ist die Sequenz$\Delta = (\Delta_n)_n$von diskreten Größenordnungen$n$und das Ziel ist die Sequenz$L = (L_n)_n$von linearen Größenordnungen$n$.

Für den vergleichsbasierten Algorithmus heapify, der ungeordnete Größenlisten transformiert$n$zu Haufen ist die Quelle die Folge diskreter Ordnungen$\Delta = (\Delta_n)_n$. Das Ziel ist die Sequenz$H = (H_n)_n$Wo$H_n$ist das Poset, das durch das Hasse-Diagramm eines Haufens der Größe bestimmt wird$n$.

Das topologische Sortiermodell untermauert Komplexitätsuntergrenzen für allgemeine vergleichsbasierte Algorithmen (dh Algorithmen, die keine Sortierungen sein müssen).

Das Entropieverhältnis

Wenn$A$ist ein vergleichsbasierter Algorithmus mit Größeneingaben$n$auftreten$k$Zustände und Ausgaben, die in auftreten$l$gibt dann die Quellenentropie (also die Eingangsentropie) an$H^{s}_{A}(n) = log_2{k}$und die Zielentropie$H^{t}_{A}(n) = log_2(l)$.

Entropisches Verhältnis (ER) Es wird angenommen, dass sowohl die Quellzustände als auch die Zielzustände mit gleicher Wahrscheinlichkeit auftreten, dh gleichmäßig verteilt sind.

Betrachten Sie einen vergleichsbasierten Algorithmus$A$mit Eingängen mit Wurzelzuständen über der Quelle$\alpha_n$und Ausgaben mit Wurzelzuständen über dem Ziel$\beta_n$. Lassen$k = |\Sigma(\alpha_n)|$bezeichnen die Quellraumgröße und$l = |\Sigma(\beta_n)|$die Zielraumgröße.

Das Entropieverhältnis ist die Differenz zwischen der Quell- und der Zielentropie, die mit bezeichnet wird$\Delta H_{A}$:

$$\Delta H_{A}(n) = H^{s}_{A} (n)- H^{t}_{A}(n) = log_{2}(\frac{k}{l})$$ Die$log_2$des Verhältnisses der Quellraumgröße zur Zielraumgröße.

Theorem (siehe [1], [5]) (Die ER-Untergrenze): Betrachten Sie einen vergleichsbasierten Algorithmus$A$mit Quelle$\alpha$und Ziel$\beta$, und mit Eingaben von$A$von Größe$n$vorkommend in$k$Wurzelzustände und Ausgaben, die in auftreten$l$Wurzelzustände, dh$A$hat ein Entropieverhältnis$\Delta H_{A} = log_2{\frac{k}{l}}$.

Die folgenden unteren Grenzen der Worst-Case- und Average-Case-Vergleichszeit gelten für jeden vergleichsbasierten Algorithmus$A$dieser Art:

$$T^{W}_{A}(n) \geq \Delta H_{A} \mbox{ and }\overline{T}_{A}(n) \geq \Delta H_{A}$$

Untergrenze für vergleichsbasierte Sortieralgorithmen$A$

Die Untergrenze ist

$$\Delta H_{A}(n) = log_{2}(\frac{n!}{1}) =log_2(n!)$$ Das ER ist in diesem Fall die übliche informationstheoretische untere Grenze, dh die Entropie der Eingaben, die eine untere Grenze für die Worst-Case- und Average-Case-Zeit liefert.

Untere Grenze zum Erstellen perfekter Haufen von Größe$7$Betrachten Sie einen vergleichsbasierten Algorithmus$H^{*}$Erstellen perfekter Haufen aus ungeordneten Größenlisten$7$. Es gibt$\frac{7!}{63}$perfekte Haufen von Größe$7$. Somit

$$\Delta H_{H^{*}}(7) = log_{2}(\frac{7!}{\frac{7!}{63}}) = 63$$

Das topologische Sortiermodell von [1] ist die nächste Annäherung an eine rein mathematische Problemstellung für vergleichsbasierte Berechnungen. Es vertieft sich nicht in die Syntax (Code) der Algorithmen, sondern identifiziert vergleichsbasierte Algorithmen mit Entscheidungsbäumen, die ihre Berechnungspfade modellieren.

[0] Die Kunst der Computerprogrammierung, Band III, Sortieren und Suchen, D. Knuth, Addison-Wesley, 1998.

[1] Zur Komplexität von Teilauftragsproduktionen Andrew Chi-Chih Yao, SIAM J. COMPUT. Vol. 18, Nr. 4, S. 679-689, Gesellschaft für industrielle und angewandte Mathematik, 1989.

[2] Munro, J. Ian; Suwanda, Hendra; "Implizite Datenstrukturen für schnelles Suchen und Aktualisieren". Zeitschrift für Computer- und Systemwissenschaften . 21 (2): 236–250, 1980.

[3] Schellekens, M.; Ein modularer Kalkül für die durchschnittlichen Kosten der Datenstrukturierung, 2008.

[4] McGeogh, Catherine C.; Ein Leitfaden zur experimentellen Algorithmik, CUP. 2012.

[5] Schonhage, A. (1976), The production of posets, Asterisque 38-39:229-246.

Vergleichssortierungen werden oft ohne Bezugnahme auf Algorithmen definiert.

Definition: Ein Vergleich sortiert weiter$n$elements ist ein verwurzelter binärer Baum, in dem

• jeder Knoten$v$ist mit einer Reihe von Permutationen gekennzeichnet$P(v) ⊆ S_n$,
• jeder interne Knoten$v$ist mit einem Paar unterschiedlicher Indizes gekennzeichnet$1 ≤ i_v < j_v ≤ n$,
• für den Wurzelknoten$v$, wir haben$P(v) = S_n$,
• für jeden Blattknoten$v$, wir haben$|P(v)| ≤ 1$,
• für jeden internen Knoten$v$, seine linken und rechten Kinder$v_<$Und$v_>$erfüllen $$P(v_<) = \{σ ∈ P(v) \mid σ_{i_v} < σ_{j_v}\}, \quad P(v_>) = \{σ ∈ P(v) \mid σ_{i_v} > σ_{j_v}\}.$$

Hier ist zum Beispiel eine Vergleichssortierung für 3 Elemente:

(Sie können – müssen aber nicht – sich eine Vergleichssortierung als den Entscheidungsbaum eines Algorithmus vorstellen, bei dem bei jedem Schritt$P(v)$stellt die Menge möglicher Ordnungen dar; der Algorithmus wählt Indizes aus$i_v$Und$j_v$und vergleicht die Elemente an diesen Indizes, um die Menge der Möglichkeiten einzugrenzen.)

Theorem: Die Höhe eines beliebigen Vergleichs sortiert weiter$n$Elemente ist$Ω(n \lg n)$.

Beweis: Ein binärer Höhenbaum$h$hat höchstens$2^h$Blätter, aber eine Vergleichssortierung hat zumindest$n!$, So$h ≥ \lg n! = Ω(n \lg n)$. ∎

Ich habe auch damit zu kämpfen, jetzt, wo ich einige Kurse in theoretischer reiner Mathematik belege ... Ich habe versucht, den Algorithmus neu zu definieren oder zu versuchen, eine "statische" Definition von Algorithmus zu erhalten, und nicht versucht, ein "Verb" wie Vergleichen zu verwenden , Bewegung usw. Knuths Definition geht davon aus, dass es mindestens ein Turing-Maschinenmodell oder Von Neumann gibt. Für Mathematiker muss es kein Maschinenmodell für die theoretische Analyse geben. Hier ist etwas, von dem ich denke, dass es der Denkweise eines Mathematikers näher kommt ... Auf keinen Fall streng ... aber ich zeige einen Ansatz.

Defn: Lassen Sie einen Satz$A = \{ a_i \}_{0 \le i \le n}$. Lassen$\sigma: A \rightarrow A$eine 'aufsteigend sortierte' Karte sein, so dass$\sigma(a_i)=a_k$mit folgender Einschränkung

1. Wenn$i < j$Dann$\sigma(a_i) \le \sigma(a_j)$(aufsteigende Karte)
2. Seien 'Algorithm Maps' eine Familie von Funktionen$f_{t}: \{[0,1], \sigma\} \rightarrow \{ A, B_t \cup \{a_{k+1}\}, B_1 \}$Wo$B_t = \{a_k\}_{k \le n} \subseteq A$so dass ... (1) gilt$B_t$Und$\sigma(a_i) = a_i$iff$i > k$.$f(0, \sigma) = A$,$f(1, \sigma) = B_1$Und$k=n$. Zum Zeitpunkt$t$ $f(t, \sigma) = B_{t} \cup \{ a_{k+1} \}$und es gibt so etwas$k$Und$B_t$.

Die schnellste Algorithmuskarte ist$f_t$Wo$t$ist minimal. Dies ist unabhängig vom Modell wie Turing oder RAM usw. Dies ist ähnlich wie Definitionen von "Deformationsrückzug" aus der algebraischen Topologie für zB

Abgesehen davon würde ich sagen, dass es in der Mathematik immer noch einige 'Verben' gibt, wie 'Rotation' oder die Gruppenoperation, die zB die physikalische Welt unabsichtlich einbringt. IMHO sollten sie so gering wie möglich sein