为什么std :: list :: reverse具有O（n）复杂度？ [英] Why does std::list::reverse have O(n) complexity?

问题描述

为什么C ++标准库中 std :: list 类的反向函数具有线性运行时？我认为对于双向链表，反向函数应该是O（1）。

Why does the reverse function for the std::list class in the C++ standard library have linear runtime? I would think that for doubly-linked lists the reverse function should have been O(1).

反转双向链表应该只涉及切换头和尾指针。

Reversing a doubly-linked list should just involve switching the head and the tail pointers.

推荐答案

假设，反向可能是 O（1）。 （再次假设）布尔列表成员可能指示链接列表的方向当前与创建列表的原始方向相同还是相反。

Hypothetically, reverse could have been O(1). There (again hypothetically) could have been a boolean list member indicating whether the direction of the linked list is currently the same or opposite as the original one where the list was created.

不幸的是，这将降低其他所有操作的性能（尽管不更改渐近运行时间）。在每个操作中，都需要咨询布尔值，以考虑是跟随链接的下一个指针还是上一个指针。

Unfortunately, that would reduce the performance of basically any other operation (albeit without changing the asymptotic runtime). In each operation, a boolean would need to be consulted to consider whether to follow a "next" or "prev" pointer of a link.

由于这被认为是相对不频繁的操作，该标准（不要求实现，仅要求复杂度）规定了复杂度可以是线性的。这样，下一个指针始终可以明确地指示相同的方向，从而加快了常见情况的操作。

Since this was presumably considered a relatively infrequent operation, the standard (which does not dictate implementations, only complexity), specified that the complexity could be linear. This allows "next" pointers to always mean the same direction unambiguously, speeding up common-case operations.

这篇关于为什么std :: list :: reverse具有O（n）复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！