-2
n 개의 요소가 포함 된 배열 백업 min-heap에서 루트를 삭제하고 나머지 힙을 다시 heap하는데 가장 최악의 시간 복잡도는 무엇입니까?n 개의 요소가 포함 된 배열 백업 min-heap에서 루트를 삭제할 때 최악의 시간 복잡도는 얼마입니까?
- O (1)
- O (LG 않음)
- O (N)
- O (N 엑스 N)의 제거 동작의
A
답변
-2
복잡성 O 인 (H) = O (logn), 여기서 h은 힙의 높이이고, n은 힙의 요소 수입니다.
여기에서 자세한 내용을보실 수 있습니다 : O (n)이 O (n)이
공간
평균 최악의 경우
: 여기 remove_minimum
힙 Complexites에 대한 자세한 정보입니다 검색 O (n) O (n)
,210삽입 O (1) O (로그 N)
가 O는 (로그 n) 삭제 O (로그 N)
픽 O (1) O (1)
선다형 답은 숙제와 비슷하게 보입니다. 너 스스로 무엇을 생각해 냈어? –
루트를 제거하는 것은 마지막 노드를 가져 와서 루트에 놓은 다음 다시 적절한 위치로 옮깁니다. 복잡성은 항목이 내려 앉아야하는 레벨 수에서 파생됩니다. 힙 정의 방법을 이해한다면 그 값이 무엇인지 알아낼 수 있어야합니다. –