Succinct Representations of Functions
Succinct Representations of Functions
复制标题
函数的简洁表示
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
S. Rao
中科院分区：
文献类型：
--
作者：
J. Munro;S. Rao
We investigate the problem of succinctly representing an arbitrary function, f: [n] →[n] so that f k (i) can be computed quickly for any i and any (positive or negative) integer power k. We give a representation that takes ((1+epsilon) n lg n + O(1)) bits and computes arbitrary positive powers in constant time. It can also be used to compute f k (i), for any negative integer k, in O(1+|f k (i)|) time.
