数据砖 店面

我觉得除非知道这个元素的上界， 然后可以说定bucket大小为k， 这样插入是O(log(n/k)) + n(k) --> 因为要找到对应的bucket, 然后维护一个有序数组。  删除是O(log(n/k)) + O(k), read是O(log(n/k)).

如果不设上界， 那还是个线性算法。 预先知道上界， 可以设k = sqrt(n), 那样就是一个sqrt(n) 算法。

intelliu 发表于 2021-5-20 10:58
我觉得除非知道这个元素的上界， 然后可以说定bucket大小为k， 这样插入是O(log(n/k)) + n(k) --> 因为要找 ...

说的没错。。bucket能很好work的前提都是有限的range。。