Ich habe einige Datenstrukturen durchgesehen und das ist mir als zeitlicher Aufwand aufgefallen: O (log (log (n)))) - wettbewerbsfähig .
Ich habe gelesen, dass konstant-wettbewerbsfähig das Verhältnis der erwarteten Zeit / optimalen Zeit war. Aber was bedeutet es, wettbewerbsfähig zu sein?
Der Online-Algorithmus ist einer, der seine Eingaben nicht im Voraus kennt und in gewissem Sinne auf unvorhersagbare Eingaben "reagieren" muss. Im Gegensatz dazu sind Offline-Algorithmen solche, die alle ihre Eingaben im Voraus kennen.
Die Wettbewerbsanalyse vergleicht die Leistung eines optimalen Online-Algorithmus mit einem optimalen Offline-Algorithmus. Somit bedeutet k-kompetitiv, dass es einen Offline-Algorithmus gibt, der höchstens k-mal schlechter ist als ein Online-Algorithmus. O (lglgn) competitive bedeutet also, dass der optimale Offline-Algorithmus höchstens lglgn (mal eine Konstante) mal schlechter ist als der optimale Online-Algorithmus.
Der Begriff "k-kompetitiv" kann auf die gleiche Weise wie der Begriff "k-Approximation" gedacht werden. Eine k-Approximation bedeutet, dass der Approximationsalgorithmus höchstens k-mal schlechter ist als der optimale Algorithmus.
kann etwas Licht auf Ihre Frage.
Von dem obigen Link:
Sei A irgendein BST-Algorithmus, definiere A (S) als die Kosten der Durchführung Sequenz S und OPT (S, To) als Mindestkosten für die Durchführung der Sequenz S. Ein Algorithmus A ist T-kompetitiv, wenn für alle möglichen Sequenzen S, A (S) & lt; = T * OPT (S, To) + 0 (m, n).
Tags und Links algorithm time-complexity