최대 힙에서 추출하는 시간은 얼마입니까?

Question

나는이 숙제 질문이 있어요

"제임스는 그가

((^ 0.5) 로그 n) 제임스

을 잘못 이유를 설명 O 걸리는 최대 힙 (ExtractMax)에서 추출 구현하는 데 성공했다고 주장

나는 최대 힙에서 추출하는 것은 O (로그 n)이 있지만, 어떻게 제임스가 잘못된 것을 증명할 수를 소요 알아?

는

Answer 1

으로 힙을 구축하는 것은 수행 할 수 있습니다, here를 볼 수 있습니다 O (n). 이제 최대 값 추출이 O ((log n)^0.5)에서 수행 될 수 있다면, 최대 요소를 반복적으로 추출하여 n * O ((log n)^0.5)에서 전체 세트를 정렬 할 수 있습니다. 그러나 정렬의 하한값이 n * logn이므로이 작업은 불가능합니다.

따라서 James는 존재하지 않습니다.

Answer 2

@ 추출 문제를 정렬 문제로 변환하는 Duh의 솔루션은 실제로 매우 창의적입니다. 정렬이 O (n * log n)이라는 증거를 찾는 것이 너무 어렵지 않아야하며 한 가지 문제를 다른 문제로 변환하는 알고리즘 연구에서 매우 일반적입니다 (예 : 모든 NP- 완전 문제는 서로 만난다면 NP 완전이라고 증명할 수 있습니다.) 즉, 훨씬 간단한 해결책이 있다고 생각합니다.

귀하의 질문에 직접 진술했습니다. 이진 힙에서 추출하는 것은 O (log n)입니다. 에 대한 이유는입니다. O (log n)입니다. 바이너리 힙의 구조는 무엇입니까? 바이너리 힙에서 추출해야하는 작업은 무엇입니까? 왜 최악의 경우 로그 작업입니까? 이러한 제한은 구현에 의해 전혀 영향을 받습니까?

1. 그는 O에서 추출 할 수 있습니다 ((로그 n)^0.5) 그는 이진 힙을 사용
2. :

   이제 제임스의 주장에 두 부분이 있다는 것을 기억하십시오.

바이너리 힙에 대해 알고 계시다면,이 두 주장이 모두 맞을 수 있습니까? 그 이유는 무엇? 모순이 있습니까? 그렇다면 왜 모순이 있습니까? 마지막으로, 이것이 야고보에게 무엇을 의미하는지 생각해보십시오.