.NET 컬렉션 클래스의 점근적 복잡성

StackOverflow https://stackoverflow.com/questions/851949

문제

.NET 컬렉션 클래스 메서드의 점근적 복잡성(big-O 및 나머지)에 대한 리소스가 있습니까(Dictionary<K,V>, List<T> 등...)?

나는 C5 라이브러리의 문서에 이에 대한 몇 가지 정보가 포함되어 있다는 것을 알고 있습니다(예), 하지만 표준 .NET 컬렉션에도 관심이 있습니다...(그리고 PowerCollections의 정보도 좋을 것입니다).

도움이 되었습니까?

해결책

MSDN은 다음을 나열합니다.

예 : 등 :

SortedList (tkey, tvalue) 일반 클래스는 O (log n) 검색이있는 이진 검색 트리이며, 여기서 n은 사전의 요소 수입니다. 이것에서, 그것은 SortedDictionary (tkey, tvalue) 일반 클래스와 유사합니다. 두 클래스에는 비슷한 객체 모델이 있으며 둘 다 O (로그 N) 검색이 있습니다. 두 클래스가 다른 경우 메모리 사용 및 삽입 및 제거 속도가 있습니다.

SortedList (tkey, tvalue)는 SortedDictionary (tkey, tvalue)보다 기억이 적습니다.

SortedDictionary (tkey, tvalue)는 SortedList (tkey, tvalue)에 대한 O (n)과 달리 음란 된 데이터에 대한 삽입 및 제거 작업이 더 빠릅니다.

목록이 정렬 된 데이터에서 한 번에 모두 채워지면 SortedList (tkey, tvalue)는 SortedDictionary (tkey, tvalue)보다 빠릅니다.

다른 팁

이 페이지 .NET의 경우에도 동일해야 하지만 Java의 다양한 컬렉션 유형에 대한 일부 시간 복잡성을 요약합니다.

해당 페이지에서 테이블을 가져와 .NET 프레임워크에 맞게 변경/확장했습니다.MSDN 페이지도 참조하세요. 정렬사전 그리고 정렬된 목록, 다양한 작업에 필요한 시간 복잡성을 자세히 설명합니다.

수색

검색 유형/수집 유형 복잡성 설명
Linear search Array/ArrayList/LinkedList  O(N)        Unsorted data.
Binary search sorted Array/ArrayList/     O(log N)    Requires sorted data.
Search Hashtable/Dictionary<T>            O(1)        Uses hash function.
Binary search SortedDictionary/SortedKey  O(log N)    Sorting is automated.

검색 및 삽입

작업 배열/ArrayList LinkedList SortedDictionary SortedList
Access back       O(1)             O(1)        O(log N)          O(log N)
Access front      O(1)             O(1)        N.A.              N.A.
Access middle     O(1)             O(N)        N.A.              N.A.
Insert at back    O(1)             O(1)        O(log N)          O(N)
Insert at front   O(N)             O(1)        N.A.              N.A.
Insert in middle  O(N)             O(1)        N.A.              N.A.

삭제는 관련 컬렉션에 대한 삽입과 동일한 복잡성을 가져야 합니다.

SortedList에는 삽입 및 검색에 대한 몇 가지 주목할만한 특징이 있습니다.

삽입(추가 방법):

이 방법은 O(n) 연산입니다. 정렬되지 않은 데이터, 여기서 n은 개수입니다.그것이 O(log n) 연산 요소가 끝에 추가됩니다. 목록.삽입으로 인해 크기가 조정되는 경우 연산은 O(n)입니다.

검색(항목 속성):

이 속성의 값 검색 는 O(log n) 연산이고, 여기서 n은 세다.속성을 설정하는 것은 O(log n) 연산 이미 SortedList<(Of <(TKey, TValue>)>)에 있습니다.키가 목록, 속성 설정은 O (n)입니다. 정렬되지 않은 데이터에 대한 작업 또는 O(log n) 새 요소가 목록의 끝입니다.삽입으로 인해 크기 조정, 연산은 O(n)입니다.

참고하세요 ArrayList 는 다음과 같습니다 List<T> 모든 작업의 ​​복잡성 측면에서.

나는 일반적으로 알지 못합니다 (방금 게시 한 다른 답변은 아마도 당신에게 정확히 당신에게 무엇을 제공 할 것입니다), 당신은 이것과 다른 방법과 다른 방법을 반영 할 수 있습니다. 이 기능은 C#:

internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
  while (true)
  {
    SetTree<a> setTree = s;
    if (setTree is SetTree<a>.SetOne)
    {
      break;
    }
    if (setTree == null)
    {
      return n;
    }
    SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
    SetTree<a> arg_23_0 = setNode.item3;
    n = setNode.item1;
    s = arg_23_0;
  }
  return ((SetTree<a>.SetOne)s).item;
  return n;
}

좋아, 이것은 C# 용어로 정확히 '적절한'코드가 아니지만 while(true) 루프는 적어도 O (1)가 될 수 없음을 의미합니다. 그것이 실제로 무엇인지 ... 글쎄, 내 머리는 너무 아파서 알아 내기에는 너무 아파 :)

이 페이지는 대부분의 .NET 컬렉션의 일부 주요 장단점에 대한 짧은 메모를 제공합니다.

http://geekswithblogs.net/blackrabbitcoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

"컬렉션 클래스의 복잡성"과 같은 것은 없습니다. 오히려이 컬렉션에서 다른 작업마다 복잡성이 다릅니다. 예를 들어 a에 요소를 추가합니다 Dictionary<K, V>...

... 접근합니다 o (1) 작업. 새로운 요소를 수용하기 위해 용량을 늘려야하는 경우이 방법은 에) 작동, 어디에 n ~이다 Count.

a에서 요소를 검색하는 반면 Dictionary<K, V>...

... O (1) 작업에 접근합니다.

이 문서에 따르면 바이너리 트리에 기반을두고 있으며 최대 요소를 추적하는 것은 언급하지 않습니다. 문서가 올바른 경우 O (log n)이어야합니다. 컬렉션 문서에는 적어도 하나의 실수가 있었지만 (배열 지원 데이터 구조를 이진 검색 트리로 언급) 수정되었습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top