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

Question

给定大小为 N 的数据集的以下算法:

1. 将数据分成 M=(N/lg N)在 O(N) 时间内阻塞。
2. 在 O(M lg M) 时间内划分块。 *

什么是大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)？

不是家庭作业，只是一个正在研究 comp-sci 东西的工作工程师。

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) 的，而我对此毫无疑问。