배열의 모든 숫자에 가장 가까운 번호 찾기

이 문제는 기본적으로 알고리즘 최적화 문제입니다.배열의 모든 숫자에 가장 가까운 번호 찾기

우리는 n 개의 원소를 가진 목록을 가지고 있습니다. 예를 들어 {n1,n2,n3...nk} 이 목록은 분류되고 우리는

는 (nk-n1+1) 가능한 숫자 합계가있을 수 있지만, 우리의 목표는 다른 모든 숫자에 가장 가까운 입니다 수 ni을 찾는 것입니다.

브 루트 포스 방식은 n1에서 nk까지 반복 할 수 있으며 모든 목록 번호에서 거리 합계 을 계산할 수 있습니다. 이렇게하면 쉽게 목록의 다른 모든 숫자에 가장 가까운 숫자를 파악할 수 있습니다.

하지만이 방법의 문제점은 시간 복잡성 측면에서 좋지 않다는 점입니다. 이 접근법의 시간 복잡도는 O(n^2)입니다.

더 적은 시간에이 문제를 해결할 수있는 더 나은 방법이 있다고 생각합니다. 복잡합니다.

모든 접근법을 이해할 수 있습니다.

2013-02-26 vicky

"거리"의 정의는 무엇을 사용하십니까? –

목록이 정렬되었다고 언급 했으므로 이진 검색으로 검색하는 방법은 어떻습니까? – kamaci

예 거리 (a, b) = abs (ab) – vicky

"거리"가 distance(a,b) = abs(a-b) 인 경우 중간 값을 찾아야합니다.

정렬 된 목록에서 중앙값을 찾는 것은 O (1)입니다.

2013-02-26 13:27:46

홀수의 요소가있는 경우 주어진 거리 정의 ('abs (ab)')에 대해 해당 값이 1d 경우의 중앙값과 일치하는 "). – jfs

@Sebastian : 네, 있습니다. 요소가 짝수이면 두 가지 중 하나가 수행됩니다. –

짝수 개의 요소가 있으면 Yes입니다. 가장 가까운 숫자는 평균 2 개의 중간 숫자 여야합니다. b1과 b2가 두 중간 숫자 인 경우 가장 가까운 숫자는 (b1 + b2)/2 여야합니다. – vicky

평균을 구하십시오 ... 이것은 O (n)를 필요로합니다. 그런 다음 목록을 살펴 평균에 대한 ni를 찾습니다. 또한 O (1/2n)과 비슷합니다.

2013-02-26 13:33:02

답은 ROUND (SUM (n1, ..., nk)/k)이다.

2013-02-28 07:53:39 Richard

답변