std :: list :: reverse에 왜 O (n) 복잡성이 있습니까?

std :: list :: reverse에 왜 O (n) 복잡성이 있습니까?

---

std::listC ++ 표준 라이브러리 의 클래스에 대한 역 기능 이 선형 런타임을 갖는 이유는 무엇 입니까? 이중 연결 목록의 경우 역 기능이 O (1)이어야한다고 생각합니다.

이중으로 연결된 목록을 바꾸려면 머리와 꼬리 포인터를 전환하면됩니다.

---

가설 적 reverse으로 O (1) 일 수 있습니다 . 링크 된 목록의 방향이 현재 목록이 작성된 원래의 방향과 같은지 또는 반대인지를 나타내는 부울 목록 멤버가있을 수 있습니다 (가설 ​​적으로).

불행히도, 기본적으로 다른 작업의 성능이 저하됩니다 (점근선 런타임을 변경하지 않아도). 각 작업에서, 링크의 "다음"또는 "이전"포인터를 따를 지 여부를 고려하기 위해 부울을 참조해야합니다.

이것은 비교적 드문 작업으로 간주되었으므로 표준 (구현을 지시하지 않고 복잡성 만)은 복잡성이 선형 일 수 있다고 명시했습니다. 따라서 "다음"포인터는 항상 같은 방향을 분명하게 의미하여 일반적인 작업 속도를 높입니다.

---

목록에 각 노드 의“ ”및“ ”포인터 의 의미를 바꿀 수 있는 플래그가 저장되어 있으면 O (1) 일 수 있습니다 . 목록을 되 돌리는 것이 빈번한 작업이라면, 그러한 추가가 실제로 유용 할 수 있으며 현재 표준에 의해 구현이 금지 되는 이유를 모르겠습니다 . 그러나 이러한 플래그를 사용 하면 목록의 일반적인 순회 가 더 비쌉니다 (상수 요인에 의해서만)prevnext

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 ++에 도달하는 이유 중 하나입니다.

주석에서 Benjamin Lindley 가 지적한 것처럼 reverse반복자를 무효화 할 수 없기 때문에 표준에 의해 허용되는 유일한 접근 방식은 반복자 내부의 목록에 포인터를 저장하여 이중 간접 메모리 액세스를 유발하는 것으로 보입니다.

---

양방향 반복자를 지원하는 모든 컨테이너에는 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

Given this, it seems to me that the standards committee have not taken time to mandate O(1) reverse-ordering of the container because it's not necessary, and the standard library is largely built on the principle of mandating only what is strictly necessary while avoiding duplication.

Just my 2c.

---

Because it has to traverse every node (n total) and update their data (the update step is indeed O(1)). This makes the whole operation O(n*1) = O(n).

---

It also swaps previous and next pointer for every node. Thats why it takes Linear. Although it can be done in O(1) if the function using this LL also takes information about LL as input like whether it is accessing normally or reverse.

---

Only an algorithm explanation. Imagine you have an array with elements, then you need to inverted it. The basic idea is to iterate on each element changing the element on the first position to the last position, the element on second position to penultimate position, and so on. When you reach at the middle of the array you'll have all elements changed, thus in (n/2) iterations, which is considered O(n).

---

It is O(n) simply because it needs to copy the list in reverse order. Each individual item operation is O(1) but there are n of them in the entire list.

Of course there are some constant-time operations involved in setting up the space for the new list, and changing pointers afterwards, etc. The O notation doesn't consider individual constants once you include a first-order n factor.

참고URL : https://stackoverflow.com/questions/35612220/why-does-stdlistreverse-have-on-complexity