algorithm - O(log(log(n))))-competitive 是什么意思？

Question

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

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

Answer 1

在线算法是一种事先不知道其输入的算法，并且必须(在某种意义上)对不可预测的输入“使用react”。相反，离线算法是那些提前知道所有输入的算法。

竞争分析将最佳在线算法的性能与最佳离线算法的性能进行比较。因此，k-competitive 意味着存在一种离线算法，其性能至多比在线算法差 k 倍。因此，O(lglgn) 竞争意味着最优离线算法的性能至多比最优在线算法差 lglgn(乘以常数)倍。

---

术语“k-competitive”可以被认为与术语“k-approximation”相同。 k-近似表示近似算法的性能至多比最优算法差 k 倍。