Redis：当插入的元素在开始或结束时，ZADD是否优于O（logN）？

Question

ZADD的redis documentation指出操作是O（日志N）。

然而，当插入的元素位于排序顺序的开始或结束时，是否有人知道ZADD是否优于O（日志N）？

E.g.对于某些实现，这可能是O（1）。

具体地说，redis的tutorial指出：

经由含有 两个跳跃列表，以便我们添加元素每次一个双端口的数据结构和一个哈希表来实现时

排序集 Redis的执行一个O（log（N））操作。

这似乎是合理修改跳跃列表，以支持O（ķ）在开始和结束，其中ķ是跳跃列表的最高水平插入。

Answer 1

我有交叉贴Redis的网站在这个问题上，和彼得Noordhuis也给出了一个答案，对此我跨在这里发帖：

---

这是正确的。有序集合依赖于一个RNG来确定每个节点的层数（这是一个概率数据结构）。在跳过列表开始处插入/删除一个元素可以是O（1），而理论上最坏情况下的性能是O（N）（每个节点具有相同的级别）。但是，当考虑节点之间的层次分布时，分摊的时间复杂度为O（log N）。

Answer 2

k和log（N）之间是否存在关系？如果他们有一个固定的因素相关，你实际上没有改变任何东西。 （我不知道这种关系是否存在，但看起来很有道理，因为关于该主题的wikipedia page显然具有层结构中的这种关系。OTOH，该页面没有链接到证据，我不觉得因此，这只能是猜测。）

另外，总的来说，算法总体上是O这一事实并不能阻止特定的特殊情况变得更好（例如， O（1））。