文章/答案/技术大牛

发布

社区首页 >问答首页 >这两部分算法的大O是什么？

问这两部分算法的大O是什么？
EN

Stack Overflow用户

提问于 2011-03-22 05:47:53

回答 1查看 370关注 0票数 2

给定N大小数据集上的下列算法：

什么是大-哦？如何评价(N/lg N) * lg (N/lg N)？

如果不是O(N)，那么M是否小到整个事物都变成O(N)？

*分区算法是STL的stable_partition，在本例中，它将进行M测试，最多是M交换。但是，被交换的物品是尺寸lg N的块。如果必须互换，这是否将步骤2的实际时间推回O(N lg N)？

不是作业，只是一个工作的工程师在做些什么。

发布于 2011-03-22 06:05:34

它是O(N)：

N / lgN * lg(N / lgN)=N / lgN * (lgN-lglgN)=N*(1-lglgN / lgN)<=N

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/5387357

复制

相似问题

问这两部分算法的大O是什么？EN