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

Dlaczego funkcja odwrotna dla std::listklasy w standardowej bibliotece C ++ ma liniowe środowisko wykonawcze? Sądzę, że dla podwójnie powiązanych list funkcją odwrotną powinna być O (1).

Odwrócenie podwójnie połączonej listy powinno po prostu obejmować zmianę wskaźników głowy i ogona.

Hipotetycznie reversemógł to być O (1) . Tam (ponownie hipotetycznie) mógł istnieć element listy boolowskiej wskazujący, czy kierunek połączonej listy jest obecnie taki sam, czy przeciwny, niż pierwotny kierunek, w którym lista została utworzona.

Niestety zmniejszyłoby to wydajność praktycznie każdej innej operacji (choć bez zmiany asymptotycznego środowiska wykonawczego). W każdej operacji należy skonsultować się z wartością logiczną, aby zastanowić się, czy zastosować wskaźnik „następny”, czy „poprzedni” linku.

Ponieważ przypuszczalnie uznano to za stosunkowo rzadką operację, standard (który nie dyktuje implementacji, tylko złożoność) określa, że ​​złożoność może być liniowa. Pozwala to „następnym” wskaźnikom zawsze jednoznacznie oznaczać ten sam kierunek, przyspieszając operacje w typowych przypadkach.

Może to być O (1), jeśli lista przechowuje flagę, która umożliwia zamianę znaczenia wskaźników „ prev” i „ next” każdego węzła. Jeśli odwrócenie listy byłoby częstą operacją, takie dodanie może być w rzeczywistości przydatne i nie znam żadnego powodu, dla którego wdrożenie byłoby zabronione przez obecny standard. Posiadanie takiej flagi spowodowałoby jednak, że zwykłe przejście na listę byłoby droższe (choćby o stały czynnik), ponieważ zamiast

current = current->next;

w operator++iteratorze listy, dostaniesz

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

co nie jest łatwe do dodania. Biorąc pod uwagę, że listy są zwykle przeszukiwane znacznie częściej niż są odwrócone, normalne byłoby wymuszanie tej techniki. Dlatego operacja odwrotna może mieć złożoność liniową. Należy jednak pamiętać, że t ∈ O (1) ⇒ t ∈ O ( n ), więc, jak wspomniano wcześniej, technicznie możliwe byłoby wdrożenie „optymalizacji”.

Jeśli pochodzisz z języka Java lub podobnego, możesz zastanawiać się, dlaczego iterator musi za każdym razem sprawdzać flagę. Czy nie moglibyśmy zamiast tego mieć dwa różne typy iteratorów, oba wywodzące się ze wspólnego typu podstawowego, i mieć std::list::begini std::list::rbeginzwracać polimorficznie odpowiedni iterator? Chociaż jest to możliwe, pogorszyłoby to wszystko, ponieważ przyspieszenie iteratora byłoby teraz wywołaniem funkcji pośredniej (trudnej do wstawienia). 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 korzysta z C ++, gdy wydajność jest krytyczna.

Jak zauważył Benjamin Lindley w komentarzach, ponieważ reversenie wolno 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ójnie pośredni dostęp do pamięci.

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

Budowanie serwera proxy odwracającego iteratory i uzyskiwanie do niego dostępu do kontenera jest banalne.

Ten brak działania jest rzeczywiście O (1).

Jak na przykład:

#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 na zlecenie O (1) odwrotnego zamawiania kontenera, ponieważ nie jest to konieczne, a biblioteka standardowa jest w dużej mierze zbudowana na zasadzie mandowania tylko tego, co jest ściśle konieczne, podczas gdy unikanie powielania.

Tylko mój 2c.

Ponieważ musi przejść przez każdy węzeł ( nłącznie) i zaktualizować ich dane (krok 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. Właśnie dlatego bierze Linear. Chociaż można to zrobić w O (1), jeśli funkcja korzystająca z tego LL pobiera również 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 każdego elementu zmieniającego element z pierwszej pozycji do ostatniej pozycji, element z drugiej pozycji do pozycji przedostatniej i tak dalej. Kiedy osiągniesz środek tablicy, zmienisz wszystkie elementy, a więc w (n / 2) iteracjach, co jest uważane za O (n).

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

Oczywiście istnieją pewne operacje wykonywane w czasie stałym związane z ustawieniem miejsca dla nowej listy, późniejszą zmianą wskaźników itp. Notacja O nie uwzględnia indywidualnych stałych, jeśli uwzględni się czynnik n rzędu pierwszego.