Beispiel eines Algorithmus, bei dem ein Term niedriger Ordnung die Laufzeit für praktische Eingaben dominiert?

10

Die Big-O-Notation verbirgt konstante Faktoren, so dass einige -Algorithmen existieren, die für jede vernünftige Eingabegröße nicht durchführbar sind, weil der Koeffizient für den Term so groß ist. $O(n)$ $n$

Gibt es bekannte Algorithmen, deren Laufzeit jedoch einen Term niedriger Ordnung haben , der so groß ist, dass er bei angemessenen Eingabegrößen die Laufzeit vollständig dominiert? Ich möchte einen Algorithmus wie diesen als Beispiel in einem Algorithmuskurs verwenden, da dies einen guten Grund dafür darstellt, warum die Big-O-Notation nicht alles ist. $O(f(n))$ $o(f(n))$

Vielen Dank!

algorithms asymptotics templatetypedef
quelle

Algorithmen, die zuerst eine große Tabelle einrichten und dann für jedes Eingabeelement schnell in der Tabelle nachschlagen? Wenn die Tabelle groß genug ist, muss die Anzahl der Elemente enorm sein, um die Kosten für die Erstellung der Tabelle auszugleichen. Suchmaschinen sind ein Beispiel, wenn

die Anzahl der Abfragen ist.

n

$n$

András Salamon

Ich habe gehört, dass lineare Programmierung so ist. Simplex ist exponentiell, aber in der Praxis schneller als die Polynomalgorithmen.

Jmite

1

Ich kenne keinen Algorithmus, der Ihren Anforderungen entspricht, aber ich würde nach etwas suchen, das höchstens eine lineare Laufzeit hat, da ich darüber hinaus sehr bezweifeln würde, dass die kleineren Begriffe den führenden Begriff für die vernünftigsten Eingaben dominieren könnten. Aber vielleicht passt k-way Mergesort zu Ihren Anforderungen, wenn Sie zum Sortieren von Big Data verwendet werden? Das Problem besteht darin, die sekundären Speicherzugriffe zu minimieren, da diese sehr viel Zeit kosten - obwohl ich nicht ganz sicher bin, ob dies ein geeignetes Beispiel für das ist, was Sie demonstrieren möchten, und ich denke nicht, dass es einfach genug ist, dies zu tun illustrativ sein.

G. Bach

etwas ähnlich wie leistungsstarke Algorithmen, die zu komplex sind, um sie zu implementieren , siehe auch den Blog von rjlipton über galaktische Algorithmen

vzn

2

Kryptographie ist ein Beispiel, wenn es sich um eine entartete handelt. Zum Beispiel ist das Unterbrechen der AES-Verschlüsselung - alles, was Sie tun müssen, ist, den richtigen Schlüssel unter einer endlichen Zahl zu finden, oder oder abhängig von der Schlüsselgröße (vorausgesetzt, es ist genug Klartext bekannt den Schlüssel eindeutig bestimmen). Selbst Operationen würden heute alle Computer (ungefähr eine Milliarde, jede ungefähr eine Milliarde Operationen pro Sekunde) länger als die Lebensdauer des Universums (ungefähr eine Milliarde Milliarden Sekunden) benötigen. $O(1)$ $2^{128}$ $2^{192}$ $2^{256}$ $2^{128}$

$O(n \lg n)$

Gilles 'SO - hör auf böse zu sein'
quelle

n

$n$

O (1)

$\mathcal{O}(1)$

@ G.Bach Der Punkt dieses Beispiels ist, dass es nicht realisierbar ist (was Komplexitätstheorie mit hoher Komplexität assoziiert), obwohl es zeitlich konstant ist (in Bezug auf die Größe des Chiffretextes).

Gilles 'SO - hör auf böse zu sein'

2

O (1)

$O(1)$

o (1)

$o(1)$

1

O (1)

$O(1)$

1

Zwei Beispiele kommen aus dem Bereich der parametrisierten Komplexität und der FPT-Algorithmen in den Sinn . Dies ist möglicherweise nicht genau das, wonach Sie suchen, aber hier geht es weiter.

Stellen Sie sich ein Diagrammproblem vor, z. B. 3-FARBEN oder HAM-CYCLE. Beide Probleme können in monadischer Logik zweiter Ordnung ausgedrückt werden und können daher in linearer Zeit von Graphen mit begrenzter Baumbreite entschieden werden. Dies ist ein Ergebnis von Bruno Courcelle , aber der resultierende Algorithmus ist alles andere als praktisch.

$O(p^{9p/2})L$ $O(p^{2p}L)$ $p$ $L$

Juho
quelle

2

O (n)

$O(n)$

o (n)

$o(n)$

0

In gewissem Zusammenhang mit Ihrer Frage stehen Algorithmen, von denen bekannt ist, dass sie theoretisch eine gute Leistung aufweisen, die jedoch aufgrund der Unpraktikabilität bei kleineren Instanzen nicht für echte Probleme verwendet werden. Mit anderen Worten, wie Sie es wünschen, ist die "beworbene Leistung" theoretisch nur für große Eingaben möglich, die in praktischen Anwendungen nicht zu sehen sind. Dies spiegelt sich manchmal in den Big-Oh-Schätzungen wider, manchmal nicht genau. Einige Algorithmen haben eine gute theoretische "Leistung", sind jedoch logisch sehr komplex und wurden noch nie von irgendjemandem implementiert. Daher ist die "Leistung" bei praktischen Instanzgrößen nicht einmal bekannt, z. B. beim Maximum Flow- Problem.

Primalitätstest in P über AKS-Algorithmus
Kupferschmied-Winograd-Matrixmultiplikationsalgorithmus
siehe auch sind modernste Maximum-Flow-Algorithmen praktisch? tcs.se.
Siehe auch leistungsstarke Algorithmen, die zu komplex sind, um tcs.se zu implementieren
Galaktische Algorithmen RJLipton Blog

vzn
quelle

Aber sind diese unpraktisch, weil die Terme niedriger Ordnung dominieren oder weil die Konstanten der Terme hoher Ordnung schlecht sind?

David Richerby

entweder oder eine Kombination wäre es jeweils schwierig zu isolieren. effektiv / praktisch ist es der gleiche Effekt.

vzn

-1

Das ist eine Art Witz, aber es hat eine ernsthafte Seite ...

$O(n\log n)$ $O(n^2)$

David Richerby
quelle

1

Nein, das ist anders. Quicksort ist in der Praxis nützlich, da es keinen quadratischen Begriff für typische Eingaben gibt, egal wie groß die Größe ist. Wenn die Wahl des Pivots für ein Datenlayout schlecht ist, zeigt Quicksort auch bei kleinen Eingaben ein quadratisches Verhalten.

Gilles 'SO - hör auf böse zu sein'

Beispiel eines Algorithmus, bei dem ein Term niedriger Ordnung die Laufzeit für praktische Eingaben dominiert?

Antworten: