>

이 파이 콘 이야기, 34:30 그리고 화자는 t 를 얻는다고 말합니다   n 목록의 가장 큰 요소  요소는 O(t + n) 에서 수행 할 수 있습니다 .

어떻게 가능합니까? 내 이해는 힙을 만드는 것이 O(n) 라는 것입니다. 그러나 nlargest 의 복잡성은 무엇입니까  그 자체가 O(n + t) 입니까  또는 O(t)  (그리고 실제 알고리즘은 무엇입니까?)

  • 답변 # 1

    이 경우 스피커가 잘못되었습니다. 실제 비용은 O(n * log(t)) 입니다 . 힙은 첫 번째 t 에서만 호출됩니다.  iterable의 요소. 그건 O(t) 입니다 t 이면 중요하지 않습니다.   n 보다 훨씬 작습니다 . 그런 다음 나머지 모든 요소는 heappushpop 를 통해이 "작은 힙"에 추가됩니다. , 한번에 한. 그것은 O(log(t)) 걸립니다   heappushpop 의 호출 당 시간 . 힙 길이는 t 로 유지됩니다.  전역. 결국 힙이 정렬되어 O(t * log(t)) 가 발생합니다. 그러나 t 인 경우에도 중요하지 않습니다.   n 보다 훨씬 작습니다 .

    이론과 재미있다;-)

    예상 O(n) 에서 t 번째로 큰 요소를 찾는 쉬운 방법이 있습니다  시각;예를 들어 여기를 참조하십시오. 최악의 경우 O(n) 에서 더 어려운 방법이 있습니다.  시각. 그런 다음 입력을 다시 통과하면 t 를 출력 할 수 있습니다  elements>= t 번째로 큰 값 (중복의 경우 지루한 합병증 포함). 전체 작업O(n) 에서 수행 할 수 있습니다.  시간.

    그러나 이러한 방법에는 O(n) 가 필요합니다  메모리도. 파이썬은 그것들을 사용하지 않습니다. 실제로 구현 된 것의 장점은 최악의 "추가"메모리 부담이 O(t) 라는 것입니다 예를 들어, 입력 값이 많은 값을 생성하는 생성기 인 경우에는 매우 중요합니다.

  • 이전 language agnostic - 문자열에서 SEO 친화적 대시 구분 URL을 만들려면 어떻게해야합니까?
  • 다음 c++ - getopt가 옵션에 대해 누락 된 인수를 발견하지 못했습니다