이 이상한 방법

Question

방법은의 시간 복잡도를 계산하는 방법 :

List<Book> books = new List<Book>(); 

public List<Book> Shoot() 
{ 
    foreach(var b in books) 
    { 
     bool find = true; 
     foreach(var otherb in books) 
     { 
      if(otherb != b && otherb.Author == b.Author) 
      { 
       find = false; 
      } 
     } 

     if(find) 
     { 
      yield return b; 
     } 
    } 
} 

일반적으로, 시간 복잡도가 O 것 (books.Count^2)하지만, 경우 (찾기) 문이있다 바깥 쪽 루프에 있고 루프 시간이 변경 될 수 있습니다.

그래서 제 질문은 다음과 같습니다

1. 이 방법의 시간 복잡도는 무엇입니까?
2. 어떻게 계산 했습니까?

답변을 기다리고 있습니다.

미리 감사드립니다.

Answer 1

외부 루프 (n)의 각 책을 살펴보고 각 외부 책에 대해 내부 루프 (n 번)에서 각 otherb를 거쳐 시간 복잡성이 O (n^2)가 될 것입니다.

yield return은 알고리즘의 복잡성을 변경하지 않고 iterator 패턴을 생성하지만 호출하는 함수에서 전체 목록을 탐색하는 경우 algo의 모든 반복을 거치게됩니다.

What is the yield keyword used for in C#?

은 btilly 첫 번째 패스는 해시 테이블에 당신이 확인 두 번째 패스 저자 당 책의 번호를 저장, 수집을 통해 두 개의 패스를 할 수있는 언급, 알고리즘을 최적화하려면 저자는 해시 테이블을 사용하여 둘 이상의 책이있는 경우 (조회에 대한 일정 시간을 가정)하고 않는 경우 책을 얻을 :

public List<Book> Shoot() 
{ 
    var authors = new Dictionary<string, int>(); 
    foreach(var b in books) 
    { 
     if(authors.ContainsKey(b.Author)) 
      authors[b.Author] ++; 
     else 
      authors.Add(b.Author, 1); 
    } 

    foreach(var b in books) 
    { 
     if(authors[b.Author] == 1) 
      yield return b; 
    } 
} 

당신은 O (N)의 선형 시간 복잡도가이 방법, 메모를 이 경우 O (n) 여분의 공간이 필요할 것입니다.

Answer 2

최악의 경우 성능은 O(n * n)입니다. 가장 좋은 경우는 O(n)입니다. 저자가 무작위로 정렬되고 고정 부분이 하나의 책으로 만 작성된다고 가정하면 의 평균 케이스는 m 외부 루프의 반복 확률이 m으로 급격히 감소하기 때문입니다.

일반적으로 (항상 그런 것은 아니지만) 사람들은 평균적인 경우에 가장 관심이 있습니다.

덧붙여서이 문제를 처리하는 표준 방법은 모든 저자와 함께 사전을 작성하고 작성한 책의 수를 계산하는 것입니다. 시간은 O(n)입니다. 그리고 나서 그 수확량은 단지 그 사전의 키를 통해서만 하나의 엔트리로 다음 것을 찾게됩니다. 연속적인 수익률의 평균 시간은 O(1)이고 최악의 경우는 O(n)이며 모든 수익률에 대한 상각 된 평균 시간 (고정 비율은 한 권의 책만 썼다고 가정)은 수익률 당 O(1)입니다. 현재 구현에 반하여 yield 당 O(n)입니다.