Почему std::list:: reverse имеет o(n) сложность?

это может быть O(1) Если список будет хранить флаг, который позволяет, меняя значения "prev" и "next" указатели есть у каждого узла. Если реверсирование списка будет частой операцией, такое добавление может быть на самом деле полезно, и я не знаю ни одной причины, по которой его реализация будет запрещен по текущему стандарту. Однако наличие такого флага сделало бы обычный обход из списка дороже (если только постоянным фактором) потому что вместо

current = current->next;

на operator++ из списка итератора, вы получите

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

который не то, что вы решили бы добавить легко. Учитывая, что списки обычно пересекаются гораздо чаще, чем они перевернуты, было бы очень неразумно для стандарта мандат эта техника. Поэтому обратная операция может иметь линейную сложность. Заметьте, однако, что t ∈ O(1) ⇒ t∈ O(n) Итак, как упоминалось ранее, реализация вашей "оптимизации" технически будет разрешена.

если вы пришли из Java или аналогичного фона, вы можете задаться вопросом, почему итератор должен проверять флаг каждый раз. Не могли бы мы вместо этого иметь два различных типа итераторов, оба производные от общего базового типа, и иметь std::list::begin и std::list::rbegin полиморфно вернуть соответствующий итератор? Пока возможно, это сделало бы все еще хуже, потому что продвижение итератора было бы косвенным (трудно встроенным) вызовом функции сейчас. В Java вы платите эту цену в любом случае, но опять же, это одна из причин, по которой многие люди достигают C++, когда производительность критична.

как указал Бенджамин Линдли в комментариях, так как reverse Не допускается аннулировать итераторы, единственный подход, разрешенный стандартом, похоже, заключается в хранении a указатель назад к списку внутри итератора, который вызывает двойной косвенный доступ к памяти.

конечно, поскольку все контейнеры, поддерживающие двунаправленные итераторы, имеют концепцию rbegin () и 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 всего) и обновить свои данные (шаг обновления действительно O(1)). Это делает всю операцию O(n*1) = O(n).

Он также меняет местами предыдущий и следующий указатель для каждого узла. Вот почему он принимает линейный. Хотя это можно сделать в O (1), если функция, использующая этот LL, также принимает информацию о LL в качестве входных данных, например, нормально ли она обращается или наоборот.

только объяснение алгоритма. Представьте, что у вас есть массив с элементами, то вам нужно инвертировать его. Основная идея состоит в том, чтобы повторять каждый элемент, изменяя элемент на первая позиция до последней позиции, элемент на второй позиции до предпоследней позиции и так далее. Когда вы достигнете середины массива, все элементы будут изменены, таким образом, в(n/2) итерациях, что считается O (n).

Это O (n) просто потому, что он должен скопировать список в обратном порядке. Каждая отдельная операция элемента-O (1), но во всем списке их n.

конечно, есть некоторые операции с постоянным временем, связанные с настройкой пространства для нового списка, а затем изменением указателей и т. д. Нотация O не учитывает отдельные константы, как только вы включаете фактор n первого порядка.