Einfacher und praktischer deterministischer Algorithmus, komplizierte Laufzeit

18

Wenn die Laufzeit eines Algorithmus ein komplizierter Ausdruck ist, ist der Algorithmus selbst sehr oft auch kompliziert und unpraktisch. Jeder der Kubikwurzel- und -Faktoren in der asymptotischen Laufzeit führt dazu, dass der Algorithmus komplexer wird und die Laufzeit konstant bleibt. $\log \log n$

Haben wir eindrucksvolle Beispiele, bei denen diese Faustregel versagt?

Es ist natürlich leicht, Beispiele für Algorithmen zu finden , die sehr schwierig zu implementieren sind, obwohl sie eine sehr einfache Worst-Case-Laufzeit haben. Aber was ist mit der Umkehrung?

Haben wir Beispiele sehr einfacher und praktischer deterministischer Algorithmen, die einfach zu implementieren sind, jedoch einen sehr komplizierten Ausdruck als asymptotische Laufzeit im ungünstigsten Fall haben?

Bitte beachten Sie die Schlüsselwörter "deterministisch" und "Worst-Case"; Die Analyse einfacher randomisierter Algorithmen führt ziemlich leicht zu komplizierten Ausdrücken.

Was "kompliziert" ist, ist natürlich Geschmackssache. Wie auch immer, ich würde es vorziehen, einen Ausdruck zu sehen, der viel zu hässlich ist, um ihn in den Titel Ihrer Arbeit zu schreiben. Und ich würde eine komplizierte Funktion eines natürlichen Parameters (Eingabegröße, Anzahl der Knoten usw.) vorziehen .

PS. Ich dachte, ich würde das nicht zu einer "Big-List-Frage" machen und nicht zu CW. Ich würde gerne ein einziges hervorragendes Beispiel finden (falls es überhaupt existiert). Schreiben Sie daher eine andere Antwort nur, wenn Sie der Meinung sind, dass sie "besser" ist als alle bisherigen Antworten.

ds.algorithms soft-question recreational Jukka Suomela
quelle

2

Ist der AKS-Primalitätstestalgorithmus als Antwort geeignet? Ich zögere, weil die "Kompliziertheit" seiner Laufzeit in gewisser Weise auf die Pseudozufälligkeit bei der Verteilung der Primzahlen zurückzuführen ist ...

Arnab

Ich habe das Gefühl, dass der schlimmste Fall in den meisten Fällen etwas ist, das "über alles läuft", und alles ist das, woran wir die Laufzeit messen. Daher haben einfache Algorithmen natürlich einfache WC-Laufzeiten. Komplizierte Laufzeiten entstehen, wenn wir versuchen, durch einen Trick ein kleines bisschen weniger zu erreichen. Aber Ihre Frage ist interessant; Ich bin schon gespannt, ob mein Gefühl stimmt.

Raphael

@arnab: Danke, AKS ist eine gute Idee. Aber ich bin nicht sicher, ob wir es "praktisch" nennen können?

Jukka Suomela

Zählen Nachrichtenweiterleitungsschemata wie Umfrageausbreitung, Einschränkungsausbreitung oder sequentielle TRW als "Algorithmen"? Einfach zu implementieren, Laufzeit ist schwer vorherzusagen

Yaroslav Bulatov

Hoppla, ich mag immer die Rho-Methode von Pollard, sie ist einfach und praktisch, und die Analyse ist wirklich schwierig, aber die Zufälligkeit des Algorithmus macht sie als Antwort auf den Beitrag unqualifiziert ...

Hsien-Chih Chang 張顯張顯

20

Das beste Beispiel, das ich mir vorstellen kann, ist ein Algorithmus (im Folgenden beschrieben) zur Berechnung des Pegels in einer Anordnung von Linien in der Ebene, dh der polygonalen Linie, die durch die Punkte gebildet wird, über denen sich genau Linien vertikal befinden. Dies ist nicht der effizienteste Algorithmus, der für das Problem bekannt ist. Es gibt effizientere Algorithmen mit einfacheren Komplexitäten, aber ich glaube, dieser Algorithmus ist praktischer als die meisten (wenn nicht alle). Die Analyse ist wahrscheinlich nicht eng, weil sie die Komplexität auf Ebene verwendet, was ein bekanntes offenes Problem ist (ich denke, alle anderen Begriffe in der Analyse sind eng). Trotzdem bezweifle ich, dass verbesserte Grenzen für Level die Laufzeit viel einfacher machen würden. Ich gehe von $k$ $n$ $k$ $k$ $k$ , um die Komplexität als Funktion von alleinezu schreiben. $k=n/2$ $n$

Der Algorithmus basiert auf dem Line-Sweep-Paradigma und verwendet zwei -äre kinetische Turniere als kinetische Prioritätswarteschlangen. Einfügungen und Löschungen werden ausgeführt, wenn eine Linie über oder unter dem Level liegt und eine Linie von einem kinetischen Turnier zum anderen verschoben wird. Daher gibt es , Einfügungen und Löschungen (die Dey Schranke für die Verwendung von -Niveau Komplexität). Jedes Ereignis wird in verarbeitet Zeit und es gibt $(\log n)$ $k$ $O(n^{4/3})$ $k$ $O(\log n)$ Ereignisse (das ergibt sich aus der Komplexität der oberen Hüllkurve von Anordnungen von Liniensegmenten, während das aus der Höhe eines -Baums stammt ). Die Gesamtlaufzeit beträgt $O(n^{4/3} \alpha(n) \log n / \log \log n)$ $\alpha(n)$ $\log n / \log \log n$ $(\log n)$

O (n^{4 / 3} α (n) \log^{2} n / \log \log n) .

$O(n^{4/3} \alpha(n) \log^2 n / \log \log n).$

Weitere Informationen und Referenzen finden Sie im Manuskript von Timothy Chan unter http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz . Der Faktor kann durch ein binäres (intead of -ary) kinetisches Turnier entfernt werden, beschleunigt jedoch die kinetische Prioritätswarteschlange in den von mir durchgeführten Tests. Die Komplexität sollte etwas hässlicher und schlimmer werden (während der Algorithmus noch praktikabel sein wird), wenn ein kinetischer Heap anstelle eines kinetischen Turniers verwendet wird (ein innerhalb einer Quadratwurzel sollte angezeigt werden). $1/\log \log n$ $(\log n)$ $\log$

Guilherme D. da Fonseca
quelle

Exzellentes Beispiel, danke! Das wird nicht leicht zu schlagen sein. :)

Jukka Suomela

1

Dieser Algorithmus ist in der Praxis langsamer als die randomisierten Algorithmen, die ziemlich einfach zu implementieren sind (wie jemand, der einen dieser Algorithmen implementiert hat (siehe meine Arbeit "Spaziergang in einer planaren Anordnung").

Sariel Har-Peled,

Ich habe diese Antwort akzeptiert, da sie meiner Vorstellung am nächsten zu kommen scheint. Aber wenn jemand neue Ideen hat, würde ich mich freuen zu hören!

Jukka Suomela

24

Die Datenstrukturoperationen von union-find scheinen Ihren Kriterien zu entsprechen:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Kevin Wortman
quelle

2

In der Tat habe ich dieselbe Antwort gepostet, sie aber gelöscht, nachdem ich bemerkt habe, dass Sie mich verprügelt haben. :) Einfacher und eleganter Algorithmus, den ein Nicht-Theoretiker vielleicht sogar entdeckt, aber Ackermann hat die Komplexität amortisiert.

Warren Schudy

Nun,

Zeit sieht nicht , dass "kompliziert" , wenn Sie es vergleichen ,

in Guilherme Antwort. :)

O (α (n))

$O(\alpha(n))$

O (n^{4 / 3} α (n) \log^{2} n / \log \log n)

$O(n^{4/3} \alpha(n) \log^2 n / \log \log n)$

Jukka Suomela

Das Verhältnis von Algorithmuslänge zu Beweiskomplexität für Union-Find ist wahrscheinlich unschlagbar - alle drei Operationen sind was, neun Codezeilen?

Neel Krishnaswami

1

Ich glaube nicht, dass es sich um einen einfachen und praktischen Algorithmus mit komplexer Analyse handelt . Ich denke, die Frage ist nach einem einfachen und praktischen Algorithmus mit komplexer Laufzeit , dh dem tatsächlichen Ausdruck, der für die obere Schranke erhalten wird.

Guilherme D. da Fonseca

6

Simplex-Algorithmus. Einfach zu implementieren und funktioniert wunderbar in der Praxis, ist aber ein Chaos theoretisch zu analysieren.

Mohit Singh
quelle

n

$n$

Tatsächlich ist bekannt, dass Simplex im schlimmsten Fall über die Klee-Minty-Konstruktion exponentielle Zeit benötigt. Ich denke, es ist kein Beispiel dafür, worum Jukka bittet

Suresh Venkat

1

Vielleicht hätte ich lieber die Simplex-Methode als den Simplex-Algorithmus sagen sollen. Der Klee-Minty-Würfel und seine Variationen funktionieren nach einigen Vanille-Drehregeln. Aber zum Beispiel hat die zufällige Facettenschwenkregel eine verrückte obere und (aktuelle) untere Schranke. Gil Kalai hatte einen schönen Blog-Eintrag über die jüngsten Ergebnisse. gilkalai.wordpress.com/2010/11/09/…

Mohit Singh

Guter Punkt, Mohit. Ich war auch verwirrt.

Suresh Venkat

2

Ich bin mir nicht sicher, ob Sie dies für "praktisch" halten, aber es ist ein bekanntes offenes Problem. Paul Erdos sagte über Collatz Vermutung: "Mathematik ist noch nicht bereit für solche Probleme"

$x=1$

Mohammad Al-Turkistany
quelle

Und was löst dieser Algorithmus für ein Problem ...?

Jukka Suomela

Es wird vorgeschlagen, nach neuartigen Laufzeitanalysetechniken zu suchen.

Mohammad Al-Turkistany

2

man könnte dann sagen, dass eine Brute-Force-Suche nach einem Beweis der Collatz-Vermutung auch "neuartige Laufzeitanalysetechniken" motiviert; In beiden Fällen untersucht der Algorithmus nur gedankenlos einen Digraphen. Die Collatz-Vermutung macht Spaß, aber ich denke nicht, dass dies ein interessantes Beispiel für "einen Algorithmus" ist.

Niel de Beaudrap

2

Dieses Beispiel kann von Interesse sein, auch wenn es dem Brief Ihrer Anfrage nicht entspricht, da es eine gewisse spirituelle Verwandtschaft aufweist. Insbesondere die Frage der Sortierung von Pfannkuchenstapeln und gebrannten Pfannkuchen nach Umkehrungen.

http://en.wikipedia.org/wiki/Pancake_sorting

Ein Anwendungsgebiet ist die Computational Biology (Genetics), in der Fragen zur Umlagerung von Genomen in Bezug auf den Abstand zwischen Permutationen durch Umkehrung von Teilen der Permutationen nach verschiedenen Regeln formuliert werden können.

Joseph Malkevitch
quelle

Einfacher und praktischer deterministischer Algorithmus, komplizierte Laufzeit

Antworten: