We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in $O(T(n,m))$ time per operation, but any partially retroactive version of that data structure requires $T(n,m) \cdot m^{1-o(1)}$ worst-case time per operation, where $n$ is the size of the data structure at any time and $m$ is the number of operations. Any data structure with operations running in $O(T(n,m))$ time per operation can be converted (via the "rollback method") into a partially retroactive data structure running in $O(T(n,m) \cdot m)$ time per operation, so our lower bound is tight up to an $m^{o(1)}$ factor common in fine-grained complexity.
翻译：我们证明数据结构与同一数据结构部分追溯性版本之间差距的微小下限基本上是最理想的。 确切地说,假设三个标准假设中的任何一个,我们描述的问题是一个数据结构问题,即每个操作运行时间为$O(n,m)美元,但该数据结构的任何部分追溯性版本要求每个操作的时间为$T(n,m)\cdot m ⁇ 1-o(1)}美元,每个操作最坏的情况时间为$n是数据结构的大小,而操作数量为$1美元。每个操作运行时间为$O(n,m)美元的任何数据结构都可以(通过“滚回方法”)转换成一个部分追溯性数据结构,每个操作时间运行时间为$O(n,m)\cdotm)美元,因此我们较低的连接紧凑合1美元(m ⁇ o(1)}系数,在精细复杂复杂情况下是常见的。
相关内容
微信扫码咨询专知VIP会员