问
TreeRangeMap时空复杂
mobiledu2502890917 发布于 2023-02-13 20:05我正在寻找guava TreeRangeMap,它似乎非常适合我对项目的需求.java文档说它基于(java标准？)TreeMap,它具有get(put和next)的O(log(n))时间.
但TreeRangeMap应该是某种范围树实现,根据这个SO问题,查询的O(k + log(n))时间复杂度为O(n)空间,k为范围大小？有人可以证实这一点吗？
我对TreeRangeMap.subRangeMap()操作的时间复杂性也很感兴趣.它是否具有相同的O(k + log(n))？
谢谢.
1 个回答
-
这是一种观点,而不是真正的突变或任何东西.
subRangeMap在O(1)时间内RangeMap返回,并且它返回O(log n)的每个查询操作都有附加成本 - 也就是说,它的所有操作仍然采用O(log n),只是具有更高的常数因子.资料来源:我是"实施它的人".
2023-02-13 20:09 回答
风一样的男孩668
撰写答案
今天，你开发时遇到什么问题呢？
立即提问
京公网安备 11010802041100号