unj*_*nj2 8 algorithm time-complexity
我正在浏览一些数据结构,我注意到这是一个时间复杂度: O(log(log(n)))) - 竞争性.
我读到,持续竞争是预期时间/最佳时间的比率.但是,拥有一套竞争力意味着什么呢？
小智 13
在线算法是预先不知道其输入的算法,并且必须(在某种意义上)对不可预测的输入做出"反应".相比之下,离线算法是预先知道其所有输入的算法.
竞争分析将最优在线算法的性能与最佳离线算法进行比较.因此,k竞争意味着存在离线算法,其执行最多比在线算法更差k倍.因此,O(lglgn)竞争意味着最优离线算法最多执行比最优在线算法更差的lglgn(乘以常数)倍.
术语"k-竞争"可以与术语"k-近似"相同的方式来考虑.k近似意味着近似算法执行最多比最优算法差k倍.