O(log(log(n))))-竞争是什么意思？

Question

我正在研究一些数据结构，我注意到这是一个时间复杂度： O(log(log(n))))-竞争.

我读到持续竞争是预期时间/最佳时间的比率。但具有一定的竞争力意味着什么呢？

Answer 1

在线算法是一个不知道它的预先输入，并且必须“反应”（在某种意义上）不可预测的输入。相比之下，离线算法是那些事先知道它的所有输入。

竞争分析的最佳在线算法的性能进行比较，以一个最佳的离线算法。因此，K-的竞争意味着有一个离线算法执行最多的k倍的在线算法差。所以，O（lglgn）竞争性意味着该最佳离线算法执行至多lglgn比最佳在线算法（乘以常数）倍差。

---

的术语“K-竞争性”可以以相同的方式作为“K-近似”一词被认为是。的k近似表示该近似算法执行至多k倍比最佳算法更糟。

Answer 2

这 可以解答你的问题。

从上面的链接：

令A为任何BST算法，将A（S）定义为执行序列S和OPT（S，TO）的成本，为执行序列S的最低成本。如果对于所有可能的序列s，a（s）<= t * opt（s to） + o（m，n），则算法A是T竞争力。