Dlaczego std:: list:: reverse ma złożoność O (n)?

It could be O (1) if the list would store a flag that allows swapping the meaning of "prev" and "next" pointers each node has. Jeśli odwracanie listy byłoby częstą operacją, takie dodanie może być w rzeczywistości użyteczne i nie wiem, dlaczego implementacja byłaby zabroniona przez obecny standard. Jednak posiadanie takiej flagi uczyniłoby zwykły Trawers listy droższym (choćby o stały współczynnik), ponieważ zamiast

current = current->next;

W operator++ iteratora listy, otrzymasz

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

Co nie jest czymś, co można łatwo dodać. Biorąc pod uwagę, że listy są zwykle znacznie częściej przesuwane niż odwrócone, byłoby bardzo nierozsądne, aby standard upoważnić tę technikę. W związku z tym operacja odwrotna może mieć złożoność liniową. Należy jednak pamiętać, że t ∈ O(1) ⇒ t ∈ O(n ) Tak więc, jak wspomniano wcześniej, wdrożenie" optymalizacji " technicznie byłoby dozwolone.

Jeśli pochodzisz z Javy lub podobnego tła, możesz się zastanawiać, dlaczego iterator za każdym razem musi sprawdzać flagę. Czy nie moglibyśmy zamiast tego mieć dwóch odrębnych typów iteratorów, oba wywodzące się ze wspólnego typu bazowego i std::list::begin i std::list::rbegin polimorficznie zwracać odpowiedni iterator? Chociaż jest to możliwe, to pogorszyłoby całą sprawę, ponieważ postęp iteratora byłby pośredni (trudny do wbudowania) funkcja wywołaj teraz. W Javie i tak Płacisz tę cenę rutynowo, ale z drugiej strony, jest to jeden z powodów, dla których wiele osób sięga po C++, gdy wydajność jest krytyczna.

Jak zauważył Benjamin Lindley w komentarzach, ponieważ reverse nie może unieważniać iteratorów, jedynym podejściem dozwolonym przez standard wydaje się być Przechowywanie WSKAŹNIKA z powrotem do listy wewnątrz iteratora, co powoduje podwójny pośredni dostęp do pamięci.

Z pewnością ponieważ wszystkie kontenery obsługujące dwukierunkowe Iteratory mają koncepcję rbegin () i rend (), to pytanie jest dyskusyjne?

Zbudowanie proxy, który odwraca Iteratory i uzyskuje przez to dostęp do kontenera, jest trywialne.

Ta operacja jest rzeczywiście O (1).

Takie jak:

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

Oczekiwany wynik:

mat
the
on
sat
cat
the

Biorąc to pod uwagę, wydaje mi się, że Komitet Normalizacyjny nie poświęcił czasu, aby zlecić O(1) odwrotne zamówienie kontenera, ponieważ nie jest to konieczne, a biblioteka standardowa jest w dużej mierze zbudowana na zasadzie nakazywania tylko tego, co jest ściśle konieczne, unikając powielania.

Ponieważ musi przemierzyć każdy węzeł (n RAZEM) i zaktualizować swoje dane(etap aktualizacji jest rzeczywiście O(1)). To sprawia, że cała operacja O(n*1) = O(n).

Zamienia również poprzedni i następny wskaźnik dla każdego węzła. / Align= "left" / Linear Chociaż można to zrobić w O(1), Jeśli funkcja używająca tego LL również pobiera informacje o LL jako dane wejściowe, takie jak to, czy uzyskuje dostęp normalnie czy odwrotnie.

Tylko Wyjaśnienie algorytmu. Wyobraź sobie, że masz tablicę z elementami, a następnie musisz ją odwrócić. Podstawową ideą jest iteracja na każdym elemencie zmieniającym element na pierwsza pozycja do ostatniej pozycji, element na drugiej pozycji do przedostatniej pozycji, i tak dalej. Gdy dotrzesz do środka tablicy, wszystkie elementy zostaną zmienione, a więc w iteracjach (n / 2), które są uważane za O(n).

Jest O (N) po prostu dlatego, że musi skopiować listę w odwrotnej kolejności. Każda pojedyncza operacja elementu to O(1), ale jest ich n na całej liście.

Oczywiście istnieją pewne operacje w czasie stałym związane z ustawianiem przestrzeni dla nowej listy, a następnie zmienianiem wskaźników itp. Notacja O nie uwzględnia pojedynczych stałych po uwzględnieniu współczynnika N pierwszego rzędu.