¿Por qué std :: list :: reverse tiene complejidad O (n)?

¿Por qué la función inversa para la std::listclase en la biblioteca estándar de C ++ tiene tiempo de ejecución lineal? Creo que para las listas doblemente vinculadas, la función inversa debería haber sido O (1).

Revertir una lista doblemente vinculada solo debería implicar cambiar los punteros de cabeza y cola.

Hipotéticamente, reversepodría haber sido O (1) . Allí (de nuevo hipotéticamente) podría haber sido un miembro de la lista booleana que indica si la dirección de la lista vinculada es actualmente la misma o la opuesta a la original donde se creó la lista.

Desafortunadamente, eso reduciría el rendimiento de básicamente cualquier otra operación (aunque sin cambiar el tiempo de ejecución asintótico). En cada operación, un booleano necesitaría ser consultado para considerar si seguir un puntero "siguiente" o "anterior" de un enlace.

Dado que esto presumiblemente se consideraba una operación relativamente infrecuente, el estándar (que no dicta implementaciones, solo complejidad) especificaba que la complejidad podía ser lineal. Esto permite que los "siguientes" punteros siempre signifiquen la misma dirección sin ambigüedades, acelerando las operaciones de casos comunes.

Se podría ser O (1) si la lista almacenaría una bandera que permite intercambiar el significado de los “ prev” y “ next” punteros de cada nodo. Si invertir la lista sería una operación frecuente, tal adición podría ser de hecho útil y no sé de ninguna razón por la cual la norma actual prohibiría su implementación . Sin embargo, tener dicha bandera haría que el recorrido ordinario de la lista sea más costoso (aunque solo sea por un factor constante) porque en lugar de

current = current->next;

en el operator++iterador de la lista, obtendría

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

que no es algo que decidas agregar fácilmente. Dado que las listas generalmente se recorren con mucha más frecuencia de lo que se invierten, sería muy imprudente que el estándar ordenara esta técnica. Por lo tanto, se permite que la operación inversa tenga una complejidad lineal. Sin embargo, tenga en cuenta que t ∈ O (1) ⇒ t ∈ O ( n ) por lo que, como se mencionó anteriormente, la implementación de su "optimización" técnicamente estaría permitida.

Si proviene de un entorno Java o similar, es posible que se pregunte por qué el iterador debe verificar la bandera cada vez. ¿No podríamos tener dos tipos de iteradores distintos, ambos derivados de un tipo base común, y tener std::list::beginy std::list::rbeginpolimórficamente devolver el iterador apropiado? Si bien es posible, esto empeoraría aún más las cosas porque avanzar el iterador sería una llamada de función indirecta (difícil de alinear) ahora. En Java, está pagando este precio de forma rutinaria de todos modos, pero, de nuevo, esta es una de las razones por las que muchas personas recurren a C ++ cuando el rendimiento es crítico.

Como señaló Benjamin Lindley en los comentarios, dado reverseque no está permitido invalidar iteradores, el único enfoque permitido por el estándar parece ser almacenar un puntero en la lista dentro del iterador que causa un acceso doble indirecto a la memoria.

Seguramente, dado que todos los contenedores que admiten iteradores bidireccionales tienen el concepto de rbegin () y rend (), esta pregunta es discutible.

Es trivial construir un proxy que invierta los iteradores y acceda al contenedor a través de eso.

Esta no operación es de hecho O (1).

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

Rendimiento esperado:

mat
the
on
sat
cat
the

Dado esto, me parece que el comité de estándares no se ha tomado el tiempo para ordenar O (1) ordenar en reversa el contenedor porque no es necesario, y la biblioteca estándar se basa en gran medida en el principio de ordenar solo lo estrictamente necesario mientras evitando la duplicación.

Solo mi 2c.

Debido a que tiene que atravesar cada nodo ( ntotal) y actualizar sus datos (el paso de actualización es realmente O(1)). Esto hace que toda la operación O(n*1) = O(n).

También intercambia puntero anterior y siguiente para cada nodo. Por eso se necesita lineal. Aunque se puede hacer en O (1) si la función que usa este LL también toma información sobre LL como entrada, como si está accediendo normalmente o en reversa.

Solo una explicación de algoritmo. Imagine que tiene una matriz con elementos, luego necesita invertirla. La idea básica es iterar en cada elemento cambiando el elemento en la primera posición a la última posición, el elemento en la segunda posición a la penúltima posición, y así sucesivamente. Cuando llegue al centro de la matriz, todos los elementos cambiarán, por lo tanto, en (n / 2) iteraciones, lo que se considera O (n).

Es O (n) simplemente porque necesita copiar la lista en orden inverso. Cada operación de elemento individual es O (1) pero hay n de ellos en toda la lista.

Por supuesto, hay algunas operaciones de tiempo constante involucradas en configurar el espacio para la nueva lista y cambiar los punteros después, etc. La notación O no considera constantes individuales una vez que se incluye un factor n de primer orden.