redis - 为什么 zpopmin 的时间复杂度是 log n？

Question

来自 redis 文档:

ZPOPMIN 键 [计数]从 5.0.0 开始可用。

时间复杂度:O(log(N)*M)，其中 N 是已排序集合中的元素数，M 是弹出的元素数。

删除并返回 count 个存储在键中的排序集中得分最低的成员。

所以，我的问题是，如果列表已排序，为什么它采用 log n，为什么不是 O(1)？

Answer 1

If the list is sorted, why it's take log n, why not O(1)?

如果排序集是用列表实现的，您实际上可以在每个元素的 O(1) 时间内完成此操作。但是，排序集是 implemented (部分)与 skip list数据结构，在 O(log(N)) 时间内进行插入和删除。