짧은 간격 대 평균 간격

Question

주어진 임의의 실수의 정렬 된 배열 A [1 ... n] 각 i∈ [1 ... n-1]에 대해; A [I + 1] - A [I] 일 A.의 i 번째 갭

a) --Try A. 1의 N-1의 평균 간격 갭 계산 : O하여 (n) 시간 동안 A를 반복하고 각 간격을 'GapSum'에 추가합니다. GapSum/n-1 = 평균 갭

b) A의 i 번째 갭이 평균을 초과하지 않도록 평균의 법칙에 따라 i∈ [1 ... n-1] 그러한 i 번째 간격은 짧은 간격이라고합니다. A. 의 짧은 간격을 찾으십시오 - 시도하십시오 1 : 명백한 O (n) - 각 간격을 검사하고, 가장 작은 반환하십시오. A의 짧은 갭을 찾기 위해 점근 적으로 더 빠른 분할 및 정복 알고리즘이 있습니까?

내가 더 빨리이 작업을 수행 할 수있는 방법이 궁금합니까? 아마 내가 간과할만한 평균적인 자산이 있습니까? 방향이 도움이 될 것입니다.

--edit-- Nico는 평균 간격이 일정 시간에 계산 될 수 있다고 설명했습니다. 이것은 상수 시간으로 계산됩니까? 상수 시간의 평균 간격을 계산할 수있는 유일한 아이디어는 계산 전에 보조 배열을 준비하여 B [i]까지 간격의 합을 저장하는 것입니다. 그리고 평균 차이를 계산하는 것 B [N-1]/N-1

Answer 1

1. 정렬됩니다 A, 일정 시간 조회가 있고 n을 알고, 당신은 일정 시간의 평균 간격 크기를 계산할 수 있습니다 감안할 때 첫 번째 요소와 마지막 요소의 차이를 받아 n으로 나눔으로써

2. a. A을 반복하고 첫 번째 간격을 평균보다 작거나 같게 반환하십시오. 가장 작은 간격을 찾을 필요가 없습니다. 그래도 실행 시간은 여전히 ​​O(n)입니다.

   B. 더 잘 할 수 있니? binary search과 비슷한 것을 시도해보십시오 : 배열의 두 반쪽의 평균 간격 크기를 계산하십시오. 더 낮은 평균을 가진 것은 짧은 간격 하나 이상을 포함해야하므로, 그 절반 이내에서 검색 할 수 있습니다. 그 반쪽에서 재귀 적으로 같은 일을하면 O(log n) 알고리즘으로 끝날 수 있습니다!