c – inplace_merge：N * log(N)与N-1复杂性的原因是什么？

发布时间：2020-12-16 07:31:23 所属栏目：百科来源：网络整理

导读：根据inplace_merge上的C文档,算法的复杂性是“如果使用内部缓冲区则比较线性(N-1),否则为NlogN(其中N是范围[first,last)中的数字元素”).内部缓冲区是什么意思,导致O(N-1)与O(NlogN)复杂化的原因是什么？解决方法内部缓冲区只是由足够大小的库分配的缓冲区

根据inplace_merge上的C文档,算法的复杂性是“如果使用内部缓冲区则比较线性(N-1),否则为NlogN(其中N是范围[first,last)中的数字元素”).内部缓冲区是什么意思,导致O(N-1)与O(NlogN)复杂化的原因是什么？

解决方法

内部缓冲区只是由足够大小的库分配的缓冲区,用于在合并发生时保存合并的输出(在合并完成后将其复制回原始范围).如果使用此额外空间,则可以在线性时间内完成合并.如果它不能或不使用单独的缓冲区来存储输出,则操作会因运行时O(n log n)而降级为通用排序.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!