힙합의 속도와 메모리 분석

Question

나는 이러한 질문에 대해 인터넷 검색을 시도했지만 구체적인 대답을 찾을 수없는 것 같습니다. 내가 발견 한 대부분은 마스터 정리와 함께 증명을 사용하는 것이었지만, 나는 더 직관적으로 기억 될 수있는 평범한 영어로 무엇인가를 기대하고있다. 또한 나는 학교에 다니지 않고 있으며 이러한 질문은 인터뷰를위한 것입니다.

MEMORY :

정확히 메모리 사용면에서 큰 O를 결정하는 데 의미 하는가 무엇

? 예를 들어, n 개의 항목을 모두 저장해야 할 때 heapsort가 O (1) 메모리로 실행되는 것으로 간주되는 이유는 무엇입니까? 힙에 대해 하나의 구조 만 작성했기 때문입니까? 또는 크기를 알기 때문에 스택에 만들 수 있습니다. 항상 메모리 사용이 일정합니까?

SPEED :

원소를 첨가하는 것은 (1) 그러나 O (logn)에서 수행되는 침출 O에서 수행되는 경우 힙의 작성이 O (n)이 시간에 수행되는 방법

? O (1)에서 삽입을하고 O (n)를 삽입 한 후 각 삽입이 O (logn)가 된 후에 여과하는 것을 의미하지 않을까요? 따라서 O (n) * O (logn) = O (nlogn)입니다. 나는 또한 힙 정렬의 대부분의 구현이 힙을 만들기 위해 침투하는 대신에 heapify 함수를 사용한다는 것을 알아 차렸습니까? heapify는 O (logn)에서 O (nlogn)이고 n (nlogn) + O (nlogn) = O (nlogn)에 n 개의 삽입을 사용하여 비교를 수행합니까? 첫 번째 방법은 작은 n을 사용하는 두 번째 방법보다 성능이 좋지 않습니까?

이런 종류의 것을 가정 해 보았습니다.하지만 O (1) 연산을 n 번 수행하면 O (n) 시간이되는 것은 사실입니까? 또는 n * O (1) = O (1)입니까?

Answer 1

그래서 위키 피 디아에서 이진 힙을 만드는 것에 대한 유용한 정보를 찾았습니다 : http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap.

나는 삽입과 어쩌면 단지 빌드 단계 또는 뭔가를 호출해서는 안된다하더라도 혼란의 주요 원인은 힙에 "삽입"하는 것이 모두 O (1)와 O (logn) 인 방법이라고 생각합니다. . 따라서 힙을 이미 생성 한 후에는 heapify를 사용하지 않을 것입니다. 대신 O (logn) 삽입 메소드를 사용하십시오.

힙 속성을 유지하면서 항목을 반복적으로 추가하는 방법은 O (nlogn)에서 실행되고 힙 속성을 존중하지 않고 힙을 생성 한 다음 실제로 heapifying하는 것은 O (n)에서 실제로 실행됩니다. 직관적이고 증거가 필요하기 때문에 나는 그것에 대해 틀 렸습니다.

주문한 항목을 가져 오는 제거 단계는 각 방법마다 힙 속성을 고려한 동일한 비용 (O (nlogn))을 쓴 후에 동일 비용입니다.

결국 힙 빌드 방법에는 O (1) + O (n) + O (nlogn) = O (nlogn)이고 O (nlogn) = 삽입 방법에 대한 O (nlogn). 첫 번째가 특히 작은 n의 경우에 바람직합니다.