O(log(log(n))))-竞争是什么意思？
我正在研究一些数据结构，我注意到这是一个时间复杂度： O(log(log(n))))-竞争性。
我读到持续竞争是预期时间/最佳时间的比率。 但具有一定的竞争力意味着什么呢？
I was going through some data structures and I noticed this as a time complexity:
O(log(log(n))))-competitive.
I read that constant-competitive was the ratio of the expected time/optimal time. But what does it mean to have a set-competitive?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在线算法是一种预先不知道其输入的算法，并且必须（在某种意义上）对不可预测的输入“做出反应”。 相比之下，离线算法是那些提前知道所有输入的算法。
竞争分析将最佳在线算法与最佳离线算法的性能进行比较。 因此，k-competitive 意味着存在一种离线算法，其性能最多比在线算法差 k 倍。 因此，O(lglgn) 竞争意味着最优离线算法的性能至多比最优在线算法差 lglgn（常量的倍）倍。
术语“k-竞争”可以以与术语“k-近似”相同的方式来思考。 k 近似意味着近似算法的性能最多比最优算法差 k 倍。
Online algorithm is one which does not know its inputs in advance, and must "react" (in a sense) to unpredictable inputs. In contrast, offline algorithms are those which know all its inputs in advance.
Competitive analysis compares the performance of an optimal online algorithm to an optimal offline algorithm. Thus, k-competitive means that there is an offline algorithm which performs at most k-times worse than an online algorithm. So, O(lglgn) competitive means that the optimal offline algorithm performs at most lglgn (times a constant) times worse than the optimal online algorithm.
The term "k-competitive" can be thought of in the same manner as the term "k-approximation". A k-approximation means that the approximation algorithm performs at most k times worse than the optimal algorithm.
这可以减少一些点亮你的问题。
来自上面的链接：
This can shed some light on your question.
From the above link: