스왑의 복잡성 C#의 사전 형식 인수

Question

나는 을 가지고 있는데, 여기에 A의 개체는 고유하며 B의 개체는 고유하지 않습니다.

데이터를 B의 개체별로 그룹화하려고합니다.

예.

Dictionary<A,B> input = GenerateInput(); 
List<IGrouping<B,A>> output = input 
           .GroupBy(pair => pair.Value, pair => pair.Key) 
           .ToList(); 

1. 접근 방식의 복잡성은 무엇입니까? O (n)? 복잡성 = GroupBy 작업의 복잡성 - 값을 찾지 못했습니다. 제발 말해서 기사에 대한 링크를 제공하십시오.
2. 이 스와핑을 더 효율적으로/우아한 방법으로 할 수 있습니까?

추신. 변수 input과 output을 명시 적으로 작성하여 output이 Dictioany<,> 일 필요가 없음을 보여줍니다. 컨테이너가 AB에 의해 이동해야합니다.

Answer 1

접근 방법의 복잡성은 무엇입니까?

맞음, O (n)입니다. GroupBy은 해시 코드를 사용하여 값을 그룹화합니다. B에 좋은 해싱 함수가 있다고 가정하면 그룹 테이블을 구성하는 것은 O (n)의 비용을 상각하고 각 그룹을 성장시키는 비용을 상각하는 것을 포함합니다.

이 스와핑을 수행하는 데 더 효율적인 방법이 있습니까?

O (n)은 가능한 한 효율적입니다. 목록 대신 그룹을 사용하여 사전을 만들 수 있습니다.

IDictionary<B,List<A>> output = input 
    .GroupBy(pair => pair.Value) 
    .ToDictionary(g => g.Key, g => g.Select(p.Key).ToList());