나는 min-heap을 사용하는 방법을 연구했습니다. 각 점에 대해 우리는 크기 k의 최소 힙을 저장할 수 있지만 큰 n (I n은 1 억 명 정도를 목표로 함)에 너무 많은 공간이 필요합니다. 분명히 적은 공간을 활용하고 시간 복잡성에 그다지 영향을 미치지 않는 더 나은 방법이 있어야합니다. 다른 데이터 구조가 있습니까?2-D 평면에서 n 개의 점이 주어지면 우리는 그들 사이에서 각 점의 k 개의 가장 가까운 이웃을 찾아야합니다.
이 문제는 KD-tree의 일반적인 설정입니다. 이러한 솔루션은 선형 적 복잡성을 갖지만 구현하기가 비교적 복잡 할 수 있습니다 (준비 구현을 사용할 수없는 경우)
대체 접근법은 순진 알고리즘의 복잡성을 줄이기 위해 버킷 팅을 사용할 수 있습니다. 아이디어는 비행기를 "양동이", 즉 크기가 작은 사각형으로 분리하여 그들이 속한 양동이에 점을 배치하는 것입니다. 가장 가까운 버킷에서 가장 가까운 것이됩니다. 무작위 데이터의 경우 이것은 상당히 좋은 개선 일 수 있지만 최악의 경우는 순진한 접근 방식과 동일합니다.
KD-Tree에 대해 배우게됩니다. 또한 버킷 팅 (bucketing) 방식도 상당히 좋은 것처럼 보입니다. 구현에 적합한 데이터 구조는 무엇이라고 생각하십니까? 제 생각에 2D 평면에서 버킷 (노드) 간의 인접성을 나타내는 가장자리가있는 그래프에서의 광범위한 첫 번째 검색은 상당히 좋을 것이라고 생각합니다. – nighthowler
상상해보십시오. 대부분의 양동이가 비어있을 것으로 예상되는 경우 각 양동이에 대해 셀이있는 2 차원 행렬 또는 해시 테이블 (또는 다른 연관 배열)을 사용할 수 있습니다 –
** 많은 공간이 ** 많은 공간에 영향을 미칩니다 .- 힙 크기는 ** k **입니까? 데이터 세트 크기에 대해 https://en.wikipedia.org/wiki/K-d_tree를 고려 했습니까? – MBo
메타는 각 포인트에 대해 하나의 민첩성을 고려하고 있다고 생각합니다. 따라서 크기가''k '인 전체'n'min-heap이있을 것이므로'n * k' 공간을 차지할 것입니다. –
@SauravSahu 예, 저는 그렇게 생각했습니다. – nighthowler