Gibt es einen Algorithmus zur Optimierung der Zeit- / Raumkomplexität von Algorithmen?

9

In den 1950er Jahren wurde eine Reihe von Verfahren zur Schaltungsminimierung für Boolesche Funktionen erfunden. Gibt es eine Erweiterung dieser Methoden oder ähnliches zur Optimierung der zeitlichen oder räumlichen Komplexität von Algorithmen?

Beispielsweise würde eine Implementierung der Blasensortierung als Eingabe für einen solchen Algorithmus eine Implementierung eines Sortieralgorithmus mit einer Zeitkomplexität erzeugen, die näher an .O(nlog⁡n)

algorithms turing-machines time-complexity optimization space-complexity Optimierer
quelle
1
Geh weg!! Wir CS-Profis leben vom Unterrichten ausgefeilter Algorithmen. Ihr Vorschlag würde uns ohne Arbeit lassen!
vonbrand
Nun ... was erwartest du dann von AI?
Optimierer
Die Blasensortierung ist keine boolesche Funktion. Schlimmer noch, nicht alle Sortieralgorithmen sind gleichwertig! Zum Beispiel sind einige nicht stabil.
Yuval Filmus
Sie haben völlig Recht, aber Blasensortierung und "gute Sortierung" sind nur ein Beispiel für das, was ich als Eingabe und Ausgabe sehe. Konzentrieren wir uns nicht auf Details.
Optimierer
@ YuvalFilmus sicherlich ein sortiertes Array zurückzugeben ist nicht einfacher als wahr oder falsch zurückzugeben
vonbrand

Antworten:

11

Schlagen Sie den Beschleunigungssatz von Blum nach (ja, dieser Artikel ist weniger als informativ; schauen Sie sich ein Buch über Komplexitätstheorie an). Es heißt im Wesentlichen, dass es Programme gibt, für die es ein Programm gibt, das denselben Job ausführt, der für fast alle Eingabedaten um einen bestimmten Abstand schneller ist.

Nach dem Satz von Rice ist es unmöglich zu wissen, ob zwei gegebene Programme den gleichen Job machen.

Ja, für einige sehr eingeschränkte Begriffe von "Programm" kann man anhand eines Beispiels das "bestmögliche" Programm für den Job erstellen. Auch wichtige Klassen. Aber weit entfernt von allem, was Bubblesort ausdrücken kann.

vonbrand
quelle