为什么 std: : list: : return 具有 O (n)复杂性？

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

逆转一个双向链接的列表只需要切换头部和尾部指针即可。

10662 次浏览
小开

因为它必须遍历每个节点(n总数)并更新它们的数据(更新步骤实际上是 O(1))。这使得整个操作 O(n*1) = O(n)。

小开
最佳答案

假设 reverse可能是 O (1)。可能存在一个布尔列表成员，指示链表的方向当前是否与创建列表的原始方向相同或相反。

不幸的是，这将降低基本上任何其他操作的性能(尽管不改变渐近运行时)。在每个操作中，都需要使用一个布尔值来考虑是否跟随链接的“ next”或“ prev”指针。

由于这可能被认为是一个相对较少的操作，因此标准(它不规定实现，只规定复杂性)指定复杂性可以是线性的。这允许“下一个”指针始终明确地表示相同的方向，从而加快常见情况下的操作。

小开

如果列表中存储的标志允许交换每个节点所具有的“ prev”和“ next”指针的含义，则 可以为 哦(1)。如果反向列表将是一个频繁的操作，这样的添加可能实际上是有用的，我不知道为什么实现它将是 禁止的目前标准的任何原因。然而，有这样一个标志将使普通的 穿越列表更昂贵(如果只是由一个常量因子) ，因为不是

current = current->next;

在列表迭代器的 operator++中，您将得到

if (reversed)
current = current->prev;
else
current = current->next;

这可不是那么容易就能决定的。鉴于列表通常被遍历的次数远远多于它们被反转的次数，使用 授权这种技术对标准来说是非常不明智的。因此，允许反向操作具有线性复杂性。但是，请注意，T & isin; 哦(1) & rArr; T & isin; 哦(N) ，因此，如前所述，实现您的“优化”在技术上是允许的。

如果您来自 Java 或类似的背景，您可能想知道为什么迭代器每次都要检查标志。我们是否可以使用两种不同的迭代器类型，它们都来自于一个公共的基类型，并且使用 std::list::begin和 std::list::rbegin以多态方式返回适当的迭代器？尽管可能，但这会使整件事情变得更糟，因为现在推进迭代器将是一个间接的(难以内联的)函数调用。在 Java 中，你无论如何都要付出这样的代价，但是话说回来，这也是许多人在性能至关重要的时候使用 C + + 的原因之一。

正如 本杰明・林德利在注释中指出的，由于 reverse不允许使迭代器失效，因此标准允许的唯一方法似乎是在迭代器中存储一个指向列表的指针，这会导致双重间接内存访问。

小开

当然，因为所有支持双向迭代器的容器都有 rstart ()和 rend ()的概念，所以这个问题是没有意义的？

构建一个反向迭代器并通过它访问容器的代理非常简单。

这个非运算实际上是 O (1)。

例如:

#include <iostream>
#include <list>
#include <string>
#include <iterator>


template<class Container>
struct reverse_proxy
{
reverse_proxy(Container& c)
: _c(c)
{}


auto begin() { return std::make_reverse_iterator(std::end(_c)); }
auto end() { return std::make_reverse_iterator(std::begin(_c)); }


auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
auto end() const { return std::make_reverse_iterator(std::begin(_c)); }


Container& _c;
};


template<class Container>
auto reversed(Container& c)
{
return reverse_proxy<Container>(c);
}


int main()
{
using namespace std;
list<string> l { "the", "cat", "sat", "on", "the", "mat" };


auto r = reversed(l);
copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));


return 0;
}

预期产出:

mat
the
on
sat
cat
the

鉴于此，在我看来，标准委员会并没有花时间去强制 O (1)对容器进行反向排序，因为这是不必要的，而且标准库很大程度上是建立在这样一个原则之上: 只强制执行严格必要的操作，同时避免重复。

只有我的2C。

小开

只有算法解释。 假设您有一个包含元素的数组，然后需要将其反转。 基本思想是对每个元素进行迭代，更改 第一个位置到最后一个位置，第二个位置上的元素到倒数第二个位置，依此类推。当您到达数组的中间时，所有元素都发生了变化，因此在(n/2)迭代中，这被认为是 O (n)。

小开

它是 O (n)仅仅是因为它需要以相反的顺序复制列表。每个单独的项操作是 O (1) ，但是在整个列表中有 n 个项操作。

当然，在为新列表设置空间以及随后更改指针等操作中会涉及到一些常量时间操作。一旦包含一阶 n 因子，O 符号就不会考虑单个常数。

小开

它还为每个节点交换上一个和下一个指针。这就是为什么需要线性。虽然它可以在 O (1)中完成，如果使用这个 LL 的函数也接受关于 LL 的信息作为输入，比如它是正常访问还是反向访问。


提交答案