| [ QuizWit ] in KIDS 글 쓴 이(By): valken (:이쁜왕자:) 날 짜 (Date): 2000년 6월 9일 금요일 오후 03시 52분 36초 제 목(Title): Re: 점들사이의 거리 O(n^2) 보다 오더가 낮은 알고리즘은 없다에 한표.. 증명 : 모든 pair 를 확인해야 한다.. pair 의 갯수는 n(n-1)/2 .. 한가지 제안하는 방법.. 전체 정사각형이 d 에 비해서 디따리 크고,, 점들의 수(n) 이 상당히 많고,, 랜덤하게 분포되어 있다고 가정... 전체 정사각형을,, 한변이 d 인 정사각형 타일을 깔아서 분할합니다.. 그렇다면 한개의 타일을 기준으로,, 그 타일안의 점들의 pair를 확인 하고,, 또, 그 타일안의 한 점과,, 접해 있는 타일의 한점을 비교하기만 하면 됩니다.. 접해 있지 않은 두개의 타일은 아무리 가깝게 있어도 거리가 d 이상입니다.. (점이 타일의 선위에 있을때는,, 대충 좌상은 포함, 우하는 비포함으로 하면 될듯) 모든 타일을 확인해야 하니깐,, 접해 있는 8개의 타일중 실제로는 한쪽 사분면,, 예를 들어 오른쪽, 아래, 오른쪽 아래의 3개만 확인하면 되겠네요.. 계산량의 오더는 안 줄겠지만,, 평균 계산량은 많이 줄어 들듯 하네요.. - 이쁜왕자 - - Valken the SEXy THief~~ ^_* - |