algorithm - 这个由两部分组成的算法的 Big-O 是什么？

Question

在大小为 N 的数据集上给出以下算法:

1. 将数据分成M=(N/lg N) 在 O(N) 时间内出 block 。
2. 在 O(M lg M) 时间内对 block 进行分区。 *

什么是大O？如何评估 (N/lg N) * lg (N/lg N) ？

如果不是 O(N)，是否有一个足够小的 M 使得整个事情变成 O(N)？

* 分区算法是 STL 的 stable_partition，在此示例中，它将执行 M 次测试和至多 M lg M 交换。 但是，被交换的项目是大小为 lg N 的 block 。如果必须将它们交换到位，这会将步骤 2 的实际时间推回到 O(N lg N) 吗？

不是家庭作业，只是一个在职工程师在研究计算机科学的东西。

Answer 1

您可以通过做一些数学计算来进行评估。

log(x/y) = log(x) - log(y)
->
log(N/log(N)) = log(N) - log(log(N))

因此，将其重新插入并组合成一个分数。
N(log(N) - log(log(N)))/log(N)
=
N - N(log(log(N))/log(N))
<=，因为 log(log(N)) <= log(N) as N -> inf.，就像乘以 <= 1
N

所以，整个事情的复杂度是 O(N)。

通过注意到 M = N/log N 本身就是 O(N)，您可以很容易地猜出它是 O(N log N)。由于必须在 log M 中相乘，我不知道有什么快速方法可以毫无疑问地找出它是 O(N) 的。