redis中zadd的时间复杂度

Question

我已经读过跳过列表的插入时间复杂度是（log n）的次数很高的概率，但在最坏的情况下是O（n）。但是，在阅读redis zadd的文档时，它在https://redis.io/commands/zadd它告诉：添加每个项目的O（log（N）），其中N是排序集合中元素的数量。

如果redis使用跳过列表，那么在最坏的情况下zadd应该是O（n），不是吗？

ps：对不起，但我早些时候发布了相同的问题，但没有得到任何答复。 删除并重新创建。

Answer 1

Redis'skiplist的实施是对William Pugh的修改。所以，在最坏的情况下，时间复杂度是O(n)。时间复杂度为ZADD的是O(log(n))。