将数据结构副本分配给新实例的时间复杂度是多少？

Question

我只有一个小问题:我有一个AVL树,并希望将它1:1复制到一个新实例.我所做的是创建一个AVLTreeClass的新实例,并为其分配我想用等号复制的树(在C++ 11中).

我不得不担心时间的复杂性吗？或者这是否在O(1)中运行？

非常感谢您的帮助!

FunkyPeanut

Answer 1

这完全取决于实现,如果没有看到代码,我认为任何人都无法给出明确的答案.然而,存在各种合理的实现,即O(1),O(n)和O(n log n).

通过迭代旧树中的所有节点并调用公共插入方法将每个节点添加到新树,可以实现复制构造函数的简单实现.这需要旧树的每个元素的O(log n)时间,因此复杂度将为O(n log n).但是,这不是特别有效.另一种方法是盲目地制作树的深层副本.这将需要每个树节点O(1)工作,并且由于树中有n个节点,运行时将是O(n).没有任何其他迹象,我怀疑你的运行时是O(n),并且大多数程序员(我相信)也会假设这个,除非你给出了指示.

如果您怀疑副本很常见但更新很少,您可以考虑使用copy-on-write并让副本共享树的内部表示,只有在原始树或复制树发生更改时才能生成完整的深层副本.这将导致复制时间为O(1),但如果您随后进行了更改,则会花费O(n)或O(n log n).

或者,您可能有一个持久的 AVL树.在这种情况下,树上的任何变异操作都会在时间O(log n)中运行,并生成一个表示操作效果的新树,而不会实际破坏旧版本的树.在这种情况下,可以通过共享表示在O(1)中进行复制,而不会在以后对插入和删除操作进行处罚.

希望这可以帮助!