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))。