c – stable_partition如何成为自适应算法？
发布时间：2020-12-16 10:08:58 所属栏目：百科 来源：网络整理
导读：stable_partition是c STL的算法头文件中存在的函数模板. 我读到它是一种自适应算法,其时间复杂度为O(n * logn)或O(n),具体取决于某些因素.有人可以解释一下这些因素是什么以及时间复杂度如何取决于这些因素.谢谢 ！ 解决方法 这取决于可用的内存量. 如果你有
|
stable_partition是c STL的算法头文件中存在的函数模板.
我读到它是一种自适应算法,其时间复杂度为O(n * logn)或O(n),具体取决于某些因素.有人可以解释一下这些因素是什么以及时间复杂度如何取决于这些因素.谢谢 ！ 解决方法
这取决于可用的内存量.
如果你有足够的内存,一种方法是简单地创建一个足够大的缓冲区,从前面和后面插入相应的元素,并在完成后将其重新放回原始元素.这将花费O(n)时间. 如果没有足够的内存,this page会提到一个O(n log n)就地方法(也可能有另一种方法) – 如果你想重新排列 – 在前面和后面,你反复找到子阵列形式 – 并将其(稳定地)重新排列到—(可以通过3次反转来完成 – 反转整个子阵列,然后是负面部分,然后是正面部分). 通过尝试分配内存并检查故障,可以简单地完成对足够内存的物理检查.一种方法是使用new,如果无法分配内存,可以抛出std :: bad_alloc或返回空指针,具体取决于所使用的版本. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |