Por que std :: list :: reverse tem O (n) complexidade?

Por que a função reversa para a std::listclasse na biblioteca padrão C ++ possui tempo de execução linear? Eu pensaria que, para listas duplamente vinculadas, a função reversa deveria ter sido O (1).

A reversão de uma lista duplamente vinculada deve envolver apenas a troca da cabeça e dos ponteiros de cauda.

Hipoteticamente, reversepoderia ter sido O (1) . Poderia haver (novamente hipoteticamente) um membro da lista booleano indicando se a direção da lista vinculada atualmente é a mesma ou oposta à original em que a lista foi criada.

Infelizmente, isso reduziria o desempenho de basicamente qualquer outra operação (embora sem alterar o tempo de execução assintótico). Em cada operação, um booleano precisaria ser consultado para considerar se um ponteiro "próximo" ou "anterior" deve ser seguido.

Como presumivelmente isso era considerado uma operação relativamente pouco frequente, o padrão (que não determina implementações, apenas complexidade), especificou que a complexidade poderia ser linear. Isso permite que os ponteiros "próximos" sempre sigam a mesma direção sem ambiguidade, acelerando as operações de casos comuns.

Ele poderia ser O (1) se a lista seria armazenar uma bandeira que permite trocar o significado dos “ prev” e “ next” ponteiros Cada nó tem. Se a reversão da lista for uma operação frequente, essa adição pode ser realmente útil e não conheço nenhum motivo para implementá-la seria proibida pelo padrão atual. No entanto, ter essa bandeira tornaria a travessia comum da lista mais cara (mesmo que apenas por um fator constante), porque em vez de

current = current->next;

no operator++iterador da lista, você obteria

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

o que não é algo que você decida adicionar facilmente. Dado que as listas geralmente são percorridas com muito mais frequência do que são revertidas, seria muito imprudente o padrão exigir essa técnica. Portanto, a operação reversa pode ter complexidade linear. Observe, no entanto, que t ∈ O (1) ⇒ t ∈ O ( n ), portanto, como mencionado anteriormente, implementar tecnicamente sua “otimização” seria permitido.

Se você tem um plano de fundo Java ou similar, pode se perguntar por que o iterador deve verificar o sinalizador a cada vez. Em vez disso, não poderíamos ter dois tipos de iteradores distintos, ambos derivados de um tipo de base comum std::list::begine std::list::rbegindevolver e polimorficamente o iterador apropriado? Embora possível, isso tornaria tudo ainda pior, porque o avanço do iterador seria uma chamada de função indireta (difícil de incorporar) agora. Em Java, você está pagando esse preço rotineiramente de qualquer maneira, mas, novamente, esse é um dos motivos pelos quais muitas pessoas acessam o C ++ quando o desempenho é crítico.

Como apontado por Benjamin Lindley nos comentários, desdereverse não é permitido invalidar iteradores, a única abordagem permitida pelo padrão parece ser armazenar um ponteiro de volta à lista dentro do iterador, o que causa um acesso à memória indireto duplo.

Certamente, como todos os contêineres que suportam iteradores bidirecionais têm o conceito de rbegin () e rend (), essa pergunta é discutível?

É trivial criar um proxy que inverta os iteradores e acesse o contêiner por meio dele.

Essa não operação é de fato O (1).

tal como:

#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;
}

resultado esperado:

mat
the
on
sat
cat
the

Diante disso, parece-me que o comitê de padrões não levou tempo para ordenar a ordem inversa O (1) do contêiner porque não é necessário, e a biblioteca padrão é amplamente construída com base no princípio de exigir apenas o estritamente necessário enquanto evitando duplicação.

Apenas meu 2c.

Porque ele precisa percorrer todos os nós ( ntotal) e atualizar seus dados (a etapa de atualização é realmente O(1)). Isso faz toda a operação O(n*1) = O(n).

Também troca o ponteiro anterior e o próximo para cada nó. É por isso que é preciso Linear. Embora isso possa ser feito em O (1), se a função que usa este LL também recebe informações sobre LL como entrada, como se estivesse acessando normalmente ou ao contrário.

Apenas uma explicação do algoritmo. Imagine que você tem uma matriz com elementos e precisa invertê-la. A idéia básica é iterar em cada elemento, alterando o elemento da primeira posição para a última posição, o elemento da segunda posição para penúltima posição e assim por diante. Quando você alcança o meio da matriz, todos os elementos são alterados, assim nas iterações (n / 2), que são consideradas O (n).

É O (n) simplesmente porque precisa copiar a lista na ordem inversa. Cada operação de item individual é O (1), mas existem n na lista inteira.

É claro que existem algumas operações de tempo constante envolvidas na configuração do espaço para a nova lista e na mudança de ponteiros posteriormente, etc. A notação O não considera constantes individuais quando você inclui um fator n de primeira ordem.