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 = 10
和 N = 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)
返回的元素(查询结果)
Time complexity:
O(log(N)+M)
withN
being the number of elements in the sorted set andM
the number of elements returned.
这来自 Redis 文档。我理解 Big O 的概念,但我怀疑 log()
在这种情况下扮演什么角色。我在 SO 中阅读了 log
和答案, 例如 它可以有不同的基础。
谁能用几个例子解释这个时间复杂度?
例如:N = 1000, M = 10
和 N = 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)
返回的元素(查询结果)