Redis时间复杂度为O(log(N)+M)

Redis time complexity of O(log(N)+M)

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


这来自 Redis 文档。我理解 Big O 的概念,但我怀疑 log() 在这种情况下扮演什么角色。我在 SO 中阅读了 log 和答案, 例如 它可以有不同的基础。

谁能用几个例子解释这个时间复杂度?

例如:N = 1000, M = 10N = 1,000,000, M = 1000

请记住,大 O 表示法谈论的是长期增长率,而不是某些算法所需的实际数字步数。如果一个函数的运行时间是 100log N + 200M 或 3log N + 150M,在这两种情况下,运行时间都是 O(log N + M),所以只知道大 O 符号不会让你预测给定 N 和M 先验.

您可以做的是利用您对运行时间为 O(log N + M) 这一事实的了解,在给定一些数据点的情况下推断运行时间。例如,如果您知道 N = 10,000,000 和 M = 1,000 时的运行时间为 1s,则可以预测 N = 10,000,000 和 M = 2,000 时的运行时间可能类似于 2s,因为运行时间作为 M 的函数线性扩展。您必须处理的数据点越多,您的预测就越好。您还可以看到,运行时对 N 的变化远不如 M 的敏感,因为要使 log N 增加两倍,您需要有效地平方 N 的值。

让我逐个剖析这个东西...

O(log n):对数复杂度

要理解这种复杂性 class,您首先需要围绕 log 函数建立直觉。

你有:

  • ln:自然对数,或以对数为底e
  • log:二进制对数,或以 2 为底的对数。除非指定另一个底数
  • log*:也叫迭代对数

复杂度class我们经常使用二进制对数,或以 2 为底的对数,而不是其他的。 但区分它们仍然很重要

log 函数由 "the power to which the number 2 must be raised to obtain the value n" 定义。然而,对于像你我这样的人来说,这个定义可能有点难以推理。

你可以用一种更非正式/不太正确的方式来理解它:"the number of times you can divide by number by 2".

  • 8可以减半3次
    • 8 / 2 = 4 -> 4 / 2 = 2 -> 2 / 2 = 1.
    • 因此log(8) = 3

总结:O(log n) 意味着如果输入的大小为 n,函数使用的时间将与 log n.

成正比

O(log n)O(n).

快得多

O(n):线性复杂度

这意味着如果输入的大小为 n,函数使用的时间将与 n 成正比。意思是,它具有 1:1 比例性。


不同的变量

现在,当您有不同的变量名时该怎么办...

在这种情况下,N和M说的是不同的变量。 一些例子

  • 遍历 M x N(例如:M 行和 N 列)矩阵可能需要 O(M * N) 时间。
  • 对具有 V 个顶点和 E 个边的图执行操作的算法可以将其复杂度定义为 V 和 [=30= 的函数],例如:O(V + E)O(V * E) 或其他。

最后,回到你的问题:

在此特定上下文中,O(log(N) + M) 是什么意思?

意味着它将是以下的总和:

  • O(log N) 就集合的元素而言
  • O(N) 返回的元素(查询结果)