O (n)은 가장 가까운 쌍 알고리즘의 시간 복잡도에서 비롯된 것인가?

Question

가장 가까운 쌍 문제의 시간 복잡도는 T (n) = 2T (n/2) + O (n)입니다. 2T (n/2)는 알고리즘이 원래 크기의 절반 인 2 세트에 적용되지만 나머지는 왜 O (n)으로 나옵니까? 감사.

Answer 1

모든 분할 및 정복 알고리즘은 재귀 적 '나누기'구성 요소와 순환 된 결과가 함께 들어있는 '병합'구성 요소로 구성됩니다. 옷장 쌍의 선형 O (n) 구성 요소는 '나누기'단계의 결과를 병합 된 응답으로 병합 한 것입니다.

Answer 2

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem은 O (n)이 어디에서 오는 것인지 명확히 언급합니다 (평면형 케이스).