Выбор "P" в Чернослив и Алгоритм поиска

Question

Выбор "P" в Чернослив и Алгоритм поиска

Примечание: на рисунке выше показано разбиение на группы по 5 (столбцы). Горизонтальное поле обозначает медианные значения каждого раздела. Пункт "P" указывает медиану медиан.

У большинства исследований, которые я видел, есть эта картина при выборе "P", и она всегда имеет нечетное количество элементов. Но что, если элементы чисел у вас четные?

ех.

 1  2  3  4  5  6  7  8  9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60

как вы получаете свой "P" в четном наборе элементов?

0

algorithm pruning

Источник

user2572792 15 июл '13 в 22:39

1 ответ

Решение

Другие вопросы по тегам algorithm pruning

user834261 15 июл '13 в 22:57 2013-07-15 22:57 · Accepted Answer · 2013-07-15 22:57

Это объяснение дает детали, которые, я думаю, вы ищете:

https://www.cs.duke.edu/courses/summer10/cps130/files/Edelsbrunner_Median.pdf

Медиана множества играет особую роль в этом алгоритме, и она определяется как i-наименьший элемент, где i = (n+1)/2, если n нечетно, и i = n/2 или (n+2)/2, если n четно.