정렬 된 std :: list에서 검색의 복잡성은 무엇입니까?

정렬 된 std :: list에서 검색의 복잡성은 무엇입니까? 데이터 구조에 임의 액세스 권한이있는 경우 정렬 된 데이터의 검색 복잡성은 O (log n)임을 알았습니다. 그러나 목록에 임의 액세스 권한이 없기 때문에 정렬 될 때 복잡성은 무엇입니까?정렬 된 std :: list에서 검색의 복잡성은 무엇입니까?

출처

2014-10-02 user3852441

@dyp 가치의 검색 복잡성 – user3852441

검색 복잡도와 관계없이 (링크 된) 목록은 특정 사례에서 벡터/배열보다 성능이 뛰어나다는 것을 알지 못하는 경우 (이 경우는 매우 드뭅니다)주의해야합니다. 그 주제에 대한 C + + 발명가 Bjarne Stroustrup에 대한 흥미로운 이야기 : https://www.youtube.com/watch?v=YQs6IC-vgmo – leemes

음, O (N)입니다. std::list에있는 검색은 항상 O (N)이며 정렬되어 있는지 여부입니다.

정렬 된 컬렉션은 너무 멀리 있는지 또는 충분하지 않은지 알 수 있기 때문에 도움이됩니다. 그러나 목록의 한쪽 끝에서 시작할 수 없으므로 도움이되지 않습니다.

출처

2014-10-02 22:40:10 Quentin

ur repy에 대한 감사합니다. 이것은 이진 검색이 std :: list 정렬되어 있습니까? – user3852441

예. 일단 목록의 한가운데에 있다면 왼쪽 또는 오른쪽으로 가야하는지 알지만 ... 링크를 따라 가려면 이미 O (N) 시간이 걸렸을 것입니다. – Quentin

목록은 이중 링크 된 목록이며 각 노드가 pre/next를 가리키는 두 개의 포인터가 있습니다. 노드가 중간에 있다는 것을 알더라도 다음 포인터를 계속 통과해야합니다. 그러나 벡터를 사용하면 임의의 메모리에 액세스 할 수 있으므로 중간 노드로 바로 이동할 수 있습니다. – billz

검색 방법에 따라 다릅니다. 이 x.size() 비교 및 반복 단계, 및 소요됩니다 그래서

std::find(x.begin(), x.end(), value)
는, 선형 검색입니다 std::list<T> x 및 목록에없는 값 v을 감안할 때
std::binary_search(x.begin(), x.end())는 O (로그 이진 검색을 수행 (x.size())) 비교가 가능하지만 각 비교 대상을 처리하기 위해 반복자를 선형 적으로 증가시켜야합니다 (std::lower_bound 등의 경우에도 마찬가지입니다). 목록이 정렬 된 순서가 아닌 경우이 호출에 대한 동작은 정의되지 않습니다. 이 포인터 쫓는 관련 메모리 및 비 로컬 때문에

일반적 반복자 증분은 노드 기반 컨테이너 적지 않은 비용을 갖는다. 그러나 값 유형의 비교 연산 비용을 고려해야합니다 (예 : 매우 길거나 거의 같은 문자열). 또한 전용 영역에서 노드를 할당하여 메모리 위치를 처리 할 수 있습니다.

출처

2014-10-02 22:41:24

"검색 방법에 따라 달라집니다"- 아니요. 모든 경우에 선형 시간 인 이유를 설명해줍니다 ... – leemes

@leemes : 답변에서 설명하려고하는 것처럼 "약간"입니다 복잡한. –

그는 복잡성을 물었습니다. 그리고 그것은 간단한 대답입니다 : O (n). 당신이 설명하는 것은 * 복잡성 *이 아닌 * 비용 *입니다. 물론, 설명은 여전히 매우 도움이됩니다. – leemes

정렬 된 std :: list에서 검색의 복잡성은 무엇입니까?

답변

관련 문제