Was ist ein effizienter Algorithmus?

10

Was wird unter dem Gesichtspunkt des asymptotischen Verhaltens als "effizienter" Algorithmus angesehen? Was ist der Standard / Grund für das Zeichnen der Linie an diesem Punkt? Persönlich würde ich denken, dass alles, was ich naiv als "Subpolynom" bezeichnen könnte, so dass wie n 1 + ϵ effizient wäre und alles, was Ω ( n 2 ) ist. wäre "ineffizient". Ich habe jedoch gehört, dass alles, was polynomisch ist, als effizient bezeichnet wird. Was ist die Begründung?f(n)=o(n2)n1+ϵΩ(n2)

Robert S. Barnes
quelle

Antworten:

11

Das hängt vom Kontext ab. In der theoretischen Informatik wird normalerweise jeder Polynomzeitalgorithmus als "effizient" angesehen. In Approximationsalgorithmen würde beispielsweise eine Laufzeit von als effizient angesehen, obwohl sie in der Praxis für keinen vernünftigen Wert von ϵ verwendet werden kann . Ein Algorithmus für SAT, der in n 2 100 ausgeführt wird, wäre ein erstaunlicher Durchbruch.n1/ϵ1/ϵϵn2100

In der klassischen Algorithmusik, dh Algorithmen aus den 80er Jahren und früher, werden Laufzeiten unter oder so (Think Matrix Multiplication, Min Cost Cost Matching, Flows, lineare Programmierung) als effizient angesehen. Sie werden von den meisten Menschen immer noch als effizient angesehen, würde ich sagen. Natürlich wird ein n 2 -Algorithmus nicht als effizient angesehen, wenn ein n log n -Algorithmus bekannt ist, wie zum Beispiel zum Sortieren.n3n2nlogn

Heutzutage gibt es einen Trend zu sublinearen Algorithmen oder Streaming-Algorithmen, die mit Terabytes an Daten umgehen können. Verwenden Sie die Matrixmultiplikation, um den Seitenrang aller Seiten im Google-Index zu berechnen. Das wird nicht funktionieren.

Die asymptotische Laufzeit eines Algorithmus ist zwar sicherlich nützlich, erzählt aber nicht die ganze Geschichte. Es gibt Algorithmen mit einer guten asymptotischen Laufzeit, aber Konstanten, die so groß sind, dass sie effektiv nicht verwendet werden können. Je. Lipton nennt sie galaktische Algorithmen . Robert Sedgewick stellt in seinem Vortrag Putting the Science Back Into Computer Science sogar fest, dass Worst-Case-Grenzen "oft für die Vorhersage nutzlos, oft für Garantien nutzlos" und "Worst-Case-Analyse für die Vorhersage der Leistung nutzlos" sind .

adrianN
quelle
9
Kurz gesagt: Effizient ist das, was Ihr Problem in einem für Sie geeigneten Zeitrahmen löst.
Raphael
Dies erfordert nicht wirklich eine eigene Antwort, aber BPP, die Klasse von Funktionen mit Polynomlaufzeit (wie in der Antwort beschrieben) mit Zufälligkeit, wird oft als effizient angesehen. Mit anderen Worten, das oben Genannte ist richtig, aber Computer dürfen im Allgemeinen auf Zufälligkeiten zugreifen, um Berechnungen durchzuführen. Eine der wichtigsten praktischen Anwendungen der Zufälligkeit ist das Hashing.
SamM
Vielleicht ist "effizient" überhaupt nicht die richtige Terminologie? Ich habe gerade eines meiner Kalkülbücher durchgesehen, und der Autor nennt polynomielle Laufzeiten "verfolgbar" und exponentielle Laufzeiten "nicht handhabbar".
Robert S. Barnes
1
@ RobertS.Barnes: Unterschiedliche Wörter, gleiches Problem.
Raphael
4

Meine 2 Cent aus dem Blickwinkel verteilter Algorithmen: Bei der Betrachtung großer Netzwerke (P2P, soziale Netzwerke usw.) wird ein verteilter Algorithmus als effizient angesehen, wenn seine Laufzeit für eine Konstante c > 0 und der Algorithmus verwendet Nachrichten mit O ( log n ) Bits. Beachten Sie, dass die Anforderung an Nachrichtengrößen normalerweise noch wichtiger ist als die Laufzeit, insbesondere für "globale" Probleme, die eine größere Untergrenze für die Laufzeit haben, z. B. verteiltes MST.O(logcn)c>0 O(logn)

Peter
quelle
3

Der Grund dafür ist, dass aus Sicht des asymptotischen Verhaltens eine Polynomwachstumsrate trivial geringer ist als eine Superpolynomwachstumsrate. In der Praxis läuft ein Polynomzeitalgorithmus viel schneller als ein Superpolynomzeitalgorithmus, wenn die Eingabegröße zunimmt.

Natürlich würde niemand sagen, dass ein Algorithmus mit einer Polynomkomplexität von beispielsweise "effizient" ist, aber die Mehrheit der Algorithmen überschreitet selten eine Komplexität von O ( n 5 ) .O(n2000)O(n5)

O(n2)

Massimo Cafaro
quelle
3

Theoretisch gilt ein Algorithmus als effizient, wenn seine Laufzeit im ungünstigsten Fall durch ein Polynom in seiner Eingangslänge begrenzt ist. Der Grund dafür ist, dass Polynome gute Verschlusseigenschaften haben. Das Hinzufügen, Multiplizieren und Zusammensetzen von Polynomen sind Operationen, die Polynome ergeben, und diese sind gut, wenn Sie Probleme aufeinander reduzieren.

Natürlich wird die Lücke zwischen Polynom und Exponential mit zunehmender Eingangslänge sehr, sehr groß, so dass Polynom-Zeit-Algorithmen viel besser sind. In der Praxis kann ein Polynom-Zeit-Algorithmus lange dauern, bis er beendet wird, aber es kann sein, dass es sich um einen optimalen Algorithmus handelt (den bestmöglichen). In diesem Fall würde ich sagen, dass er effizient ist.

saadtaame
quelle
Obwohl ich verstehen kann, dass etwas, wenn es der schnellste bekannte Algorithmus für ein bestimmtes Problem ist, unter diesem Gesichtspunkt als "effizient" angesehen werden kann, fällt es mir schwer, mir alles, was in der Polytime läuft, als effizient vorzustellen. :-)
Robert S. Barnes
Für polynomielle Laufzeiten ist "effizient" nur ein Wort und ein irreführendes.
Raphael
@ Raphael Vielleicht ist Tractable ein besseres Wort ...?
Robert S. Barnes
1
@ RobertS.Barnes: Nicht viel besser, imho. "Tractable" ist genauso relativ wie "effizient".
Raphael
0

n3n2

gnasher729
quelle
Θ