A [i]와 상수의 차이의 최소 합 찾기

Question

과제에 대해 수학적 문제를 해결해야합니다. 다음과 같이 좁혀졌습니다 :

A[1, ... ,n]을 n의 정수로 지정하십시오.

y을 정수 상수로 둡니다.

M(y) = Sum |A[i] - y|, i = 1 to n :

는 지금, 나는 O(n) 시간에 M(y)의 최소를 발견하는 알고리즘을 작성해야합니다. 나는 단지 A[i] - y을 취하지 만, 절대 값은 |A[i] - y|입니다.

명확성을 위해이 방정식을 Wolfram Alpha에 넣습니다.

나는 최소 제곱 법을 고려했으나, M(y)의 최소값을 산출하지는 않지만, 평균값은 A입니다. A[i] - y의 절대 값을 사용하고 있으므로이 함수를 y과 구별 할 수있는 방법이 없습니다. 또한 나는 단지 O(n) 시간에 그것을해야하기 때문에 어떤 알고리즘을 생각해 낼 수 없다. 또한, 어떤 경우에는 y에 대해 더 정확한 답이있을 수 있다고 생각합니다.이 경우 y의 값은 A의 정수 요소 중 하나와 같아야합니다.

이것은 지금 정말로 일주일 내내 나를 먹었으며 아직 이해하지 못했습니다. 누구든지 저에게 올바른 방향으로 나를 가르키거나 가르쳐 줄 방법을 가르쳐 주실 수 있습니까? 나는 붙어있다. 도와 주셔서 정말 감사합니다.

Answer 1

M(y) = sum(abs(A[i] - y))이 최소 인 y를 선택하려고합니다. A[i]이 모두 양수라고 가정 해 봅시다 (문제가 번역에 의해 변하지 않기 때문에 결과가 변경되지 않습니다).

두 가지 간단한 관찰부터 시작하겠습니다. 먼저, y < min(A) 또는 y > max(A)과 같은 y를 선택하면 min(A) <= y <= max(A)과 같은 y를 선택한 경우보다 M (y)에 더 큰 값이됩니다. 또한 A (M (y)가 볼록)의 고유 한 지역 최소값 또는 범위가 있습니다.

따라서 [min(A) .. max(A)] 간격으로 y를 선택하고이 값을 이동하여 작은 M (y)을 얻을 수 있습니다. 일을 더 쉽게 이해하려면 A를 정렬하고 [1 .. n]에있는 i를 선택합시다 (그래서 y = A[i]).

세 가지 경우를 고려해야합니다.

A[i+1] > A[i] 경우 및 어느 {n이 홀수이고 i < (n+1)/2} 또는 {N M(A[i+1]) < M(A[i]) 후 짝수 및 i < n/2이다}.
M(A[i])에서 M(A[i+1])으로 갈수록 감소하는 용어의 수 (즉, n-i)가 증가하는 용어의 수 (즉, i)보다 많으며 증가 또는 감소는 항상 같은 금액이기 때문입니다. n이 홀수 인 경우 i < (n+1)/2 <=> 2*i < n+1 <=> 2*i < n입니다. 왜냐하면 2 * i가 짝수이기 (따라서 더 큰 짝수보다 작기 때문에 1을 빼기 때문입니다).
보다 공식적인 용어로는 M(A[i]) = sum(A[i]-A[s]) + sum(A[g]-A[i])이고, 여기서 s 및 g는 A[s] < A[i] 및 A[g] > A[i]과 같은 색인을 나타냅니다. 따라서 A[i+1] > A[i] 인 경우 M(A[i+1]) = sum(A[i]-A[s]) + i*(A[i+1]-A[i]) + sum(A[g]-A[i]) - (n-i)*(A[i+1]-A[i]) = M(A[i]) + (2*i-n)*(A[i+1]-A[i])입니다.2*i < n 및 A[i+1] > A[i] 이후, (2*i-n)*(A[i+1]-A[i]) < 0이므로 M(A[i+1]) < M(A[i])입니다.

마찬가지로, A[i-1] < A[i] 경우 및 어느 {N 홀수 및 i > (n+1)/2} 또는 다음, M(A[i-1]) > M(A[i]) {N 짝수 및 i > (n/2)+1이다}.

마지막으로, {n이 홀수이고 i = (n+1)/2} 또는 {n이 짝수이고 i = (n/2) or (n/2)+1}이면 감소 또는 증가로 인해 결국 첫 번째 또는 두 번째 사례로 연결되기 때문에 최소값을 갖게됩니다. 남은 가능한 값은 i이지만 모두 A [i]가 최소가됩니다.

A의 중앙값은 정확히 i가 마지막 경우를 만족시키는 값 A [i]입니다. A의 요소 수가 홀수 인 경우 y = A[(n+1)/2] (단 여러 개의 인덱스가있을 수 있음)과 같은 값이 하나 있습니다. 심지어 짝수이면 A[n/2] <= y <= A[n/2+1]과 같은 값의 범위 (단 하나의 정수 만 포함 할 수 있음)가 있습니다.

O (n) 시간의 중간 값을 찾는 데 도움이되는 표준 C++ 알고리즘이 있습니다 : nth_element. 다른 언어를 사용하는 경우에는 the median of medians algorithm (Nico Schertler pointed out) 또는 introselect (일반적으로 nth_element에서 사용하는 언어)을 찾아보십시오.