当前位置: 首页 > 面试题库 >

当值的得分大于目标排序集中存在的最高得分时,zadd的时间复杂度

贺功
2023-03-14
问题内容

如果将一个值加到一个排序的集合(redis)上的每个值都是得分最高的值,那么时间复杂度是否O(log(N))适用于每个值zadd

或者,对于这种边缘情况,redis会执行优化(例如,例外情况scorescore,该值高于集合中的最高值,只需将值添加到最高点)?

实际上,我之所以这样问,是因为我在应用中保留了一个全局排序集,其中值zadded以自时代开始的时间作为分数。我想知道这是否仍然会O(log(N))还是会更快?


问题答案:

一旦排序集超过了zset-max- ziplist-*配置指令设置的阈值,它将被编码为跳过列表。由于需要保持跳过列表的较高级别,因此无法针对这种情况优化插入。对源代码的粗略检查表明,正如预期的那样,没有以任何特殊方式对其进行处理。



 类似资料:
  • 我有n个数组。这些数组中的每一个都可以是无限长的。(长度可以可变)。所有这n个数组都被排序了。

  • 为什么选择排序的最佳案例时间复杂度为O(n^2),而插入排序和冒泡排序为O(n)?他们的平均时间是一样的。我不明白为什么最佳案例时间不同。如果你能帮忙,我将不胜感激。

  • 问题内容: 我想使用排序集来存储对象,并使用redis-server时间戳作为得分。 我知道我可以使用带ID的Redis Streams ,但是Redis Streams有局限性,包括我不能编辑对象,不能使用等级或字典排序,不能真正删除中间,并集或相交等对象。 我想自动执行此操作,并使用redis-server时间戳,以便可以使用多个客户端,而不必担心时钟同步。 这个怎么做? 问题答案: 解决方案

  • 在这种情况下,复杂度不应该像O(n)=n*[(n-1)(n-2)......(n-(n-1))]那样,对于外环的n次中的每一次,内环运行的差分步长逐渐减小由一。这样O(n)就等于(n^3-n^2)/2。我的方法有什么问题?

  • 以下代码的时间复杂度分析和空间复杂度分析是什么: 给定一个非空字符串和一个包含非空单词列表的字典,确定是否可以被分段为一个或多个字典单词的空格分隔序列。

  • 问题内容: 我有一个MySQL查询,该查询选择表中得分最高的3名球员,然后创建一个额外的列,为他们分配排名: 目前的进展 因此,如果表如下所示: 查询的结果将是这样的: 问题 如何更改此查询,使其在结果列表中也显示用户及其排名?例如,如果我如何返回: 编辑:我应该提到-我正在使用MySQL 5.0.96版 问题答案: 对于8.0之前的版本… https://www.db-fiddle.com/f/