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

问题描述

为什么C++标准库中std::list类的reverse函数有线性运行时间?我认为对于双向链表，反向函数应该是 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.

推荐答案

假设，reverse 可能是 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屋！