这个由两部分组成的算法的 Big-O 是什么？
给定大小为 N 的数据集上的以下算法：
- 将数据分离为 M=(N/lg N) 在 O(N) 时间内出块。
- 在 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 的块。如果必须将它们交换到位，这会将步骤 2 的实际时间推回到 O(N lg N) 吗？
不是家庭作业，只是一个在职工程师在研究计算机科学的东西。
Given the following algorithm on a dataset of size N:
- Separate the data into M=(N/lg N)
blocks in O(N) time. - Partition the blocks in O(M lg M) time. *
What is the big-O? How do I evaluate (N/lg N) * lg (N/lg N) ?
If it is not O(N), is there an M small enough that the whole thing does become O(N)?
* The partition algorithm is the STL's stable_partition which, in this example, will do M tests and at most M lg M swaps. But, the items being swapped are blocks of size lg N. Does this push the practical time of step 2 back up to O(N lg N) if they must be swapped in place?
Not homework, just a working engineer poking around in comp-sci stuff.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以通过做一些数学计算来进行评估。
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)。我不知道有什么快速方法可以确定它是 O(N) 的，因为我必须在
log M中进行乘法运算，因此我对此毫无疑问。You evaluate by doing a bit of math.
log(x/y) = log(x) - log(y)->
log(N / log(N)) = log(N) - log(log(N))So, plugging this back in and combining into a single fraction.
N(log(N) - log(log(N))) / log(N)=
N - N(log(log(N)) / log(N))<=, since log(log(N)) <= log(N) as N -> inf., it's like multiplying by <= 1
NSo, the whole thing is O(N).
You can pretty easily guess that it is O(N log N) by noticing that
M = N / log Nis, itself, O(N). I don't know of a quick way to figure out that it's O(N) without a bit of doubt on my part due to having to multiply in thelog M.其复杂度为 O(N)：
It is O(N):