포스트 바탕 Time complexity of TreeMap operations- subMap, headMap, tailMap시차 트리 맵의 복잡성 <> 동작 : (GET)과의 subMap()
의 subMap() 자체는 O (1), 및 O (n)은 서브 맵을 반복에서 유래 .
그럼, 왜 (키)를 사용 GET 다음?
우리의 subMap O를 대신 (실제 키, 사실, 키),
을 사용할 수 있습니다 (1)이 서브 맵을 반복하는 것은 O 또한 (1).
get (key)보다 빠르며 O (log (n))입니다. 여기에 뭔가 잘못되었습니다 ...
우리는 O
이 서브 맵을 반복도 (1)
이 올바른지 O입니다 서브맵을 (키, 사실, 키, true)를 대신 사용할 수 있습니다 (1).
O (n)은 질문에서 비롯됩니다. 대답은 이것을 암시하는 것을 아무것도 말하지 않습니다. 그것은 사실이 아니기 때문에 좋습니다.
하위 트리를 반복하는 시간 복잡도는 O (log n + k)입니다. 여기서 n은 전체 맵의 요소 수이고 k은 하위 맵의 요소 수입니다. 즉, 반복을 시작할 때 첫 번째 위치로 이동하려면 O (log n)이 필요합니다. 완료 방법을 보려면 getFirstEntry() 구현을 찾으십시오.
O (log n)에 대한 전반적인 복잡성을 가져 오지만 중간 개체가 생성되어 프로세스에서 삭제되기 때문에 단순한 get보다 느립니다.
답변이 약간 혼란 스럽습니다. 기술적으로 서브맵을 생성하는 것이 일정한 작업이라는 것은 사실입니다. 그러나 그것은 단지 실제로 낮은 키와 높은 키를 설정하는 것 외에는 아무것도 수행하지 않고 원래 트리와 트리 구조를 공유하기 때문입니다.
결과적으로 트리에서의 모든 조작은 특정 메소드가 호출 될 때까지 실제로 연기됩니다. 따라서 get()은 여전히 원래의 전체지도를 통과하고 그것이 낮은 경계와 높은 경계를 교차하지 않았는지 여부 만 확인합니다. get()을 단순히 말하면 O(n)이고 n은 서브맵이 아닌 원래 맵에서 가져옵니다.
SubMap은 O (1) 시간이 걸리지 만 모든 검색 작업은 원본지도와 동일한 O (log n) 시간이 걸립니다. SubMap이이 개체를 감싸고 결국 범위 검사를 완료하고 get() 메서드를 원본 소스 맵 객체에 적용합니다.
고마워요. 완전히 나에게 의미가 있습니다. 내 질문에 시간을내어 주셔서 감사합니다. – Leonard