Gibt es irgendwelche Probleme, deren bekanntester Algorithmus die Laufzeit hat?

Ich habe noch nie einen Algorithmus mit einem Protokoll im Nenner gesehen und frage mich, ob es tatsächlich nützliche Algorithmen für dieses Formular gibt.

Ich verstehe viele Dinge, die zur Multiplikation eines Protokollfaktors in der Laufzeit führen können, z. B. Sortier- oder baumbasierte Algorithmen, aber was kann dazu führen, dass Sie durch einen Protokollfaktor dividieren?

Die übliche Antwort auf "Was könnte Sie veranlassen, sich durch ein Protokoll zu teilen?" ist eine Kombination aus zwei Dingen:

1. Ein Berechnungsmodell, bei dem konstante Zeitarithmetikoperationen für wortgroße Ganzzahlen zulässig sind, bei dem Sie jedoch die Länge der Wörter konservativ einschätzen möchten. Sie nehmen also Bits pro Wort an (weil weniger als) das und Sie konnten nicht einmal den gesamten Speicher adressieren und auch, weil Algorithmen, die Tabellensuchen verwenden, zu viel Zeit benötigen, um die Tabellen einzurichten, wenn die Wörter länger sind) und$O(\log n)$
2. Ein Algorithmus, der die Daten komprimiert, indem Bits in Wörter gepackt werden und die Wörter dann verarbeitet werden.

Ich denke, es gibt viele Beispiele, aber das klassische Beispiel ist der Vier-Russen-Algorithmus für die längsten gemeinsamen Teilsequenzen usw. Er endet tatsächlich mit , weil er dann aber die Bit-Packing-Idee verwendet spart einen zweiten Protokollfaktor mit einer anderen Idee: Ersetzen von Blöcken von -Bitoperationen durch eine einzelne Tabellensuche.$O(n^2/\log^2 n)$$O(\log^2 n)$

Der Zauberwürfel ist ein sehr natürliches (und für mich unerwartetes) Beispiel. Ein Würfel benötigt zum Lösen Schritte. (Beachten Sie, dass dies die Theta-Notation ist, also eine enge Ober- und Untergrenze).$n\times n\times n$$\Theta(n^2/\log n)$

Dies wird in diesem Artikel [1] gezeigt.

Es mag sein , erwähnenswert , dass die Komplexität der spezifischen Instanzen der Zauberwürfel lösen , ist offen, aber gemutmaßt NP-schwer zu sein (diskutiert hier zum Beispiel) NP hart [2]. Der Algorithmus $\Theta(n^2/\log n)$ garantiert eine Lösung, und er garantiert, dass alle Lösungen asymptotisch optimal sind, aber bestimmte Fälle möglicherweise nicht optimal lösen. Ihre Definition von nützlich kann hier gelten oder auch nicht, da Rubiks Würfel im Allgemeinen nicht mit diesem Algorithmus gelöst werden ( Kociembas Algorithmus wird im Allgemeinen für kleine Würfel verwendet, da er in der Praxis schnelle und optimale Lösungen liefert).

[1] Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw und Andrew Winslow. Algorithmen zum Lösen von Rubiks Würfeln. Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), 5.-9. September 2011, S. 689-700

[2] Erik D. Demaine, Sarah Eisenstat und Mikhail Rudoy. Das optimale Lösen des Zauberwürfels ist NP-vollständig. Tagungsband des 35. Internationalen Symposiums zu theoretischen Aspekten der Informatik (STACS 2018) vom 28. Februar bis 3. März 2018, S. 24: 1-24: 13.

Ein Beispiel für , das im Nenner ohne Bit-Packing-Tricks auftaucht, ist eine kürzlich erschienene Veröffentlichung von Agarwal, Ben Avraham, Kaplan und Sharir über die Berechnung des diskreten Fréchet-Abstands zwischen zwei polygonalen Ketten in der Zeit O ( n 2 log log n / log n ). . Obwohl ich mit den Details des Algorithmus nicht vertraut bin, besteht ein allgemeiner Trick darin, die Eingabe in relativ kleine Teile zu unterteilen und die Antworten dann geschickt zu kombinieren (dies klingt natürlich wie Teilen und Erobern, aber Sie erhalten nicht das Protokoll n im Nenner mit einigen cleveren Tricks)$\log n$$O(n^2\log\log n/\log n)$

Nicht genau das, wonach Sie gefragt haben, aber eine "wilde" Situation, in der ein logarithmischer Faktor im Nenner auftaucht, ist das Papier " Pebbles and Branching Programs for Tree Evaluation " von Stephen Cook, Pierre McKenzie, Mark Braverman und Dustin Wehr Rahul Santhanam.

Das Baum Auswertungsproblem (TEP) ist: ein gegebener ary Baum mit annotierten Werten in { 1 , ... , k } auf den Blättern und Funktionen { 1 , ... , k } d → { 1 , ... , k } auf internen Knoten , bewerte den Baum. Hier erhält jeder interne Knoten den Wert seiner mit Annotationen versehenen Funktion für die Werte seiner untergeordneten Knoten. Dies ist ein einfaches Problem, und es soll gezeigt werden, dass es im logarithmischen Raum nicht gelöst werden kann (wenn die Höhe des Baums Teil der Eingabe ist). Zu diesem Zweck sind wir an der Größe der Verzweigungsprogramme zur Lösung von TEP interessiert.$d$$\{1,\ldots,k\}$$\{1,\ldots,k\}^d \to \{1,\ldots,k\}$

In Abschnitt 5 werden enge Grenzen für Bäume der Höhe 3 sowohl für TEP als auch für das zugehörige Problem BEP angegeben, bei dem die Ausgabe auf eine willkürliche Weise auf reduziert wird . Für TEP ist die Schranke Θ ( k 2 d - 1 ) , während für BEP die Schranke Θ ( k 2 d - 1 / log k ) ist , dh Sie erhalten eine Einsparung von log k .$\{0,1\}$$\Theta(k^{2d-1})$$\Theta(k^{2d-1}/\log k)$$\log k$

Auch wenn es nicht über Laufzeit ist, dachte ich , es lohnt sich, die klassische Folge von Hopcroft, Paul und Valiant zu erwähnen: [1], da es nach wie vor ist in der Geist von "was Sie veranlassen könnte , einen Protokollfaktor zu speichern ."$\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$

Das gibt viele Beispiele für Probleme, bei denen die bekannteste Obergrenze der Raumkomplexität einen logarithmischen Nenner hat. (Abhängig von Ihrer Sichtweise würde ich denken, dass dieses Beispiel entweder sehr interessant ist - was für ein erstaunlicher Satz! - oder sehr uninteressant - es ist wahrscheinlich nicht "tatsächlich nützlich".)

[1] Hopcroft, Paul und Valiant. Zeit gegen Raum . J. ACM 24 (2): 332 & ndash; 337, 1977.

Es gibt zwei Probleme mit einer engen Abfragekomplexität :$\Theta(n/\log n)$

• Münzwägeproblem mit Federwaage.
• Mastermind mit n Position und 2 Farben.

Der bekannteste Algorithmus zur Berechnung des Bearbeitungsabstands (auch Levenshtein genannt) zwischen zwei Zeichenfolgen der Länge benötigt die Zeit O ( ( n / log n ) 2 ) :$n$$O((n/\log n)^2)$

William J. Masek, Mike Paterson: Ein schnellerer Algorithmus zur Berechnung von Abständen bei der Bearbeitung von Strings. J. Comput. Syst. Sci. 20 (1): 18 & ndash; 31 (1980).

erscheint als die richtige Grenze für ein von Greg und Paul Valiant betrachtetes Problem (keine Verbindung zu Bit-Tricks):$\Theta(n/\log n)$

Gregory Valiant und Paul Valiant, The power of linear estimators, 2011. Auf dem 52. jährlichen IEEE-Symposium über die Grundlagen der Informatik, FOCS 2011.

Hier ist ein weiteres Beispiel für eine enge Grenze mit einem logarithmischen Faktor. (Dies ist Theorem 6.17 aus Boolean Function Complexity: Advances and Frontiers von Stasys Jukna.)

Die Formelgröße (über die vollständige Binärbasis oder die De-Morgan-Basis) des Elementunterscheidungsproblems ist , wobei n die Anzahl der Bits in der Eingabe ist.$\Theta(n^2/\log n)$$n$

Der Grund der log - Faktor in dem Nenner erscheint , ist , daß repräsentiere ganze Zahlen zwischen 1 und Poly ( m ) erfordert , n : = O ( m log m ) Bits insgesamt, da jede ganze Zahl erfordert O ( log m ) Bits. So eine obere , dass natürliche Aussehen in Bezug auf gebunden m , wie Θ ( m 2 log m ) , wird Θ ( n 2 / log n ) , wenn sie in Bezug auf die zum Ausdruck$m$$\text{poly}(m)$$n := O(m \log m)$$O(\log m)$$m$$\Theta(m^2 \log m)$$\Theta(n^2/\log n)$ , wobei n die Anzahl der Bits in der Eingabe ist.$n$$n$

Ermitteln der Primfaktoren von n durch Versuchsteilung, wenn die Liste der Primzahlen bereits gegeben ist. Es gibt Primzahlen kleiner als n. Wenn Ihnen diese Primzahlen gegeben werden, dann nimmt dieProbedivisionvon n durch jede von ihnenθ($\theta(\frac{n}{\log(n)})$Zeit (unter der Annahme, dass Division eine Operation mit konstanter Zeit ist)$\theta(\frac{n}{\log(n)})$

$O(f(n))$$O\left({f(n)\over{\log f(n)}}\right)$$f(n)=n$$O\left(n \over {\log n} \right)$