Was bedeutet O(log(log(n))))-competitive?

Question

Ich bin einige Datenstrukturen durchgegangen und habe festgestellt, dass dies eine Zeitkomplexität darstellt: O(log(log(n))))-konkurrenzfähig .

Ich habe gelesen, dass konstant-kompetitiv das Verhältnis von erwarteter Zeit zu optimaler Zeit ist. Aber was bedeutet es, einen festen Wettbewerbswert zu haben?

Answer 1

Ein Online-Algorithmus ist ein Algorithmus, der seine Eingaben nicht im Voraus kennt und (in gewissem Sinne) auf unvorhersehbare Eingaben "reagieren" muss. Im Gegensatz dazu sind Offline-Algorithmen solche, die alle ihre Eingaben im Voraus kennen.

In der Wettbewerbsanalyse wird die Leistung eines optimalen Online-Algorithmus mit der eines optimalen Offline-Algorithmus verglichen. So bedeutet k-kompetitiv, dass es einen Offline-Algorithmus gibt, der höchstens k-mal schlechter abschneidet als ein Online-Algorithmus. O(lglgn) wettbewerbsfähig bedeutet also, dass der optimale Offline-Algorithmus höchstens lglgn (mal eine Konstante) mal schlechter abschneidet als der optimale Online-Algorithmus.

---

Der Begriff "k-kompetitiv" kann auf die gleiche Weise wie der Begriff "k-Approximation" verstanden werden. Eine k-Approximation bedeutet, dass der Approximationsalgorithmus höchstens k-mal schlechter abschneidet als der optimale Algorithmus.

Answer 2

Ce site kann etwas Licht in Ihre Frage bringen.

Aus dem obigen Link:

Sei A ein beliebiger BST-Algorithmus, definiere A(S) als die Kosten für die Durchführung von Sequenz S und OPT(S, To) als die minimalen Kosten für die Ausführung der Sequenz S. Ein Algorithmus A ist T-kompetitiv, wenn für alle möglichen Sequenzen S, A(S) <= T * OPT(S, To) + O(m, n).