홈>
이 파이 콘 이야기, 34:30 그리고 화자는
t
를 얻는다고 말합니다
n
목록의 가장 큰 요소
요소는
O(t + n)
에서 수행 할 수 있습니다
.
어떻게 가능합니까? 내 이해는 힙을 만드는 것이
O(n)
라는 것입니다.
그러나
nlargest
의 복잡성은 무엇입니까
그 자체가
O(n + t)
입니까
또는
O(t)
(그리고 실제 알고리즘은 무엇입니까?)
- 답변 # 1
관련 자료
- java - 기본 kafkaListenerContainerFactory는 어떻게 작동합니까?
- c++ - 어떻게 작동합니까? 포인터 할당에 대한 포인터
- 루프의 루프가 파이썬과 어떻게 작동합니까?
- 함수 목록은 파이썬에서 어떻게 작동합니까?
- namespace - --hostname은`buildah run`에서 어떻게 작동합니까?
- Generic이 Kotlin에서 Int 인 경우 Generic은 어떻게 작동합니까?
- bash - grep은 DOS 줄 끝을 어떻게 처리합니까?
- mouse - 키보드가 작동하지 않는 이유는 무엇입니까?
- linux - gparted에서 3TB ext4 디스크를 포맷하는 데 얼마나 걸립니까?
- asp.net core - 면도기 페이지에 그림이 어떻게 표시됩니까?
- html - aria-labelledby 속성은 어떻게 작동합니까?
- haskell - 내 함수가 무한 목록에서 작동하지 않는 이유는 무엇입니까?
- c - 추가 사용을 위해 루프의 최종 결과를 int로 어떻게 가져 옵니까?
- svelte - v312에서 작동하는 데 사용 된 기능이 v330에서 작동하지 않습니다
- postgresql - - : timestamp :: date는 java/spring에서 작동합니까?
- mac - 키보드가 작동하지 않거나 켜지지 않음
- division - colorforth/mod 알고리즘은 어떻게 작동합니까?
- algorithm - 공식 x&(x - 1) 작동합니까?
- visual studio - Func in dictionary,이 코드는 어떻게 작동합니까? 씨#
- java - 두 번째 반복에서는 루프가 작동하지 않습니다
이 경우 스피커가 잘못되었습니다. 실제 비용은
이론과 재미있다;-)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)라는 것입니다 예를 들어, 입력 값이 많은 값을 생성하는 생성기 인 경우에는 매우 중요합니다.