为什么 zpopmin 时间复杂度是 log n? [英] why zpopmin time complexity is log n?

问题描述

来自 redis 文档:

from redis doc:

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

ZPOPMIN key [count] Available since 5.0.0.

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

Time complexity: O(log(N)*M) with N being the number of elements in the sorted set, and M being the number of elements popped.

删除并返回存储在 key 的有序集合中得分最低的 count 成员.

Removes and returns up to count members with the lowest scores in the sorted set stored at key.

所以，我的问题是，如果列表已排序，为什么需要 log n，为什么不是 O(1)?

So, my question is, if the list is sorted, why it's take log n, why not O(1)?

推荐答案

如果列表是排序的，为什么需要log n，为什么不是O(1)?

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

如果排序集是用列表实现的，你实际上可以在每个元素的 O(1) 时间内做到这一点.但是，排序集是实现(部分)与skip list 数据结构，在 O(log(N)) 时间内进行插入和删除.

If sorted sets were implemented with lists, you could in fact do this in O(1) time per element. However, sorted sets are implemented (in part) with the skip list data structure, which does insertions and deletions in O(log(N)) time.

这篇关于为什么 zpopmin 时间复杂度是 log n?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！