我正在浏览一些数据结构，我注意到这是一个时间复杂度： O(log(log(n))))-competitive。
我读到持续竞争是预期时间/最佳时间的比率。但是，有一个集合竞争意味着什么？
问问题
5234 次
2 回答
13
在线算法是一种事先不知道其输入的算法，并且必须对不可预测的输入做出“反应”（在某种意义上）。相反，离线算法是那些预先知道其所有输入的算法。
竞争分析将最佳在线算法的性能与最佳离线算法的性能进行比较。因此，k 竞争意味着存在一种离线算法，其性能最多比在线算法差 k 倍。因此，O(lglgn) 竞争意味着最优离线算法的性能最多比最优在线算法差 lglgn（乘以常数）倍。
术语“k-竞争”可以以与术语“k-近似”相同的方式来考虑。k 近似意味着近似算法的性能最多比最优算法差 k 倍。
于 2009-05-30T15:54:47.040 回答
1
这可以阐明您的问题。
从上面的链接：
令 A 为任意 BST 算法，定义 A(S) 为执行序列 S 的成本，定义 OPT(S, To) 为执行序列 S 的最小成本。如果对于所有可能的序列 S，算法 A 是 T 竞争的， A(S) <= T * OPT(S, To) + O(m, n)。
于 2009-05-30T11:08:17.253 回答