All geek questions in one place

Calculate value at maximum distance from set of values

What I'm trying to achieve is constantly adding more values ​​to the set and keeping them as far apart as possible. I'm sure there should be several algorithms to solve this problem, but I'm probably just not looking for suitable terms. If someone can point me to a solution (it doesn't have to be particularly effective), that would be great.

Effectively, given the set of S values ​​within the Min-Max range, I need to calculate a new V value within the same range so that the sum of the distances between V and all values ​​in S is maximized.

+4
source share
3 answers

, , . -, sumDistance(), V V .

d sumDistance(), Min <= d <= Max V . , . V, , - , .

, . , , , .

+1

, V S, /. . S_1, S_2,..., S_n - S, min max. S_i < V < S_ {i + 1}, V = S_i, V = S_ {i + 1}, .

O (n ^ 2), S. O (n) , O (1) .

, , O (log n) . , . . , , , .

+2

d(a,b) = |a-b|, min max .

:

Suppose you have a V that is not at the endpoint. Then you have values n1that are lower and n2values ​​that are higher. The total distance at the minimum will be no less (n1 - n2) * (max - V)than the maximum, and the maximum distance at the maximum will be no less (n2 - n1) * (V - min).

Since at least one of n1 - n2and n2 - n1must be non-negative, the maximum can always be found at one of the end points.

0
source

Source: https://habr.com/ru/post/1599059/

More articles:


All Articles