delete[]算子的时间复杂度是多少?
我的意思是它是如何实现的-它是否迭代数组中的所有元素并为每个元素调用析构函数?
这个运算符对原语类型(int等)也是这样吗?以及用户定义的类型?
发布于 2014-01-12 16:34:26
delete和delete[]的实现分为两个阶段:
更不用说对析构函数的调用链了,因为析构函数的复杂性本质上是由您控制的,我们留给我们的是如何释放内存来考虑的。
第二点不在C++规范的范围之内。因此,任何编译器套件/操作系统都可以自由地采用自己的策略。
一种常见的内存分配/去分配策略是在需要时从操作系统分配整个内存页,然后在每个new/new[]上返回适当大小的块,然后将其长度和属性作为页眉/页脚存储在页面中。对应的delete/delete[]可以简单地将相同的块标记为“空闲”,这显然是O(1)。
如果内存解分配的复杂性为O(1),则delete 的复杂性本质上取决于对析构函数的调用。默认实现(几乎)什么也不做,它是单个调用的O(1),因此是一个整体的O(n),其中n是调用的toal数(例如,如果被解构的对象有两个字段,其析构函数被调用,然后是n = 1 (object) + 2 (o. fields) = 3)。
将所有的部分组合在一起:您可以通过在析构函数中执行操作(可以由您编写)来任意增加复杂性,但是不能比O (n ) (上一段中定义的n)“执行得更好”。在形式上正确的说法是:“delete 的复杂性是一个Omega(n)"。
请允许我在这一点上有点非正式。
发布于 2014-01-12 16:37:59
对于类类型,理论复杂性是O(n)。为每个元素调用析构函数。当然,这取决于实现是否坚持可观察的行为,因此如果析构函数是无操作的,或者行为与只将整个块标记为已释放的行为相同,那么复杂性可能就是O(1)。
对于原始类型,编译器很可能一次只释放整个内存块,因此复杂性O(1)。
https://stackoverflow.com/questions/21077140
复制相似问题