Понимание алгоритма "медианы медианов"

Я хочу понять алгоритм "медианы медианов" в следующем примере:

У нас есть 45 различных чисел, разделенных на 9 групп с 5 элементами каждый.

48 43 38 33 28 23 18 13 8

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10

51 46 41 36 31 26 21 16 53

52 47 42 37 32 27 22 17 54

Первый шаг - сортировка каждой группы (в этом случае они уже отсортированы)
На втором этапе рекурсивно найдите "истинную" медиану медианов (50 45 40 35 30 25 20 15 10), т.е. набор будет разделен на 2 группы:
```
50 25

45 20 

40 15

35 10

30
```
сортировка этих 2 групп
```
30 10

35 15 

40 20

45 25

50
```

медианы составляют 40 и 15 (в случае, если числа равны, мы взяли левую медианную) поэтому возвращаемое значение равно 15, однако "истинная" медиана медианов (50 45 40 35 30 25 20 15 10) равна 30, кроме того, существует 5 элементов, меньших 15, которые составляют намного меньше 30% из 45, которые упоминаются в wikipedia

и поэтому T(n) <= T(n/5) + T(7n/10) + O(n) не работает.

Кстати, в примере в Википедии я получаю результат рекурсии как 36. Однако истинная медиана равна 47.

Итак, я думаю, что в некоторых случаях эта рекурсия может не возвращать истинную медиану медианов. Я хочу понять, где моя ошибка.

Ответ 1

Проблема заключается в том, что вы говорите, чтобы найти истинную медиану медиан. В вашем примере у вас были эти медианы:

50 45 40 35 30 25 20 15 10

Истинная медиана этого набора данных равна 30, а не 15. Вы не найдете эту медиану, разбивая группы на блоки из пяти и принимая медиану этих медианов, но вместо этого рекурсивно вызывая алгоритм выбора на этом меньшем группа. Ошибка в вашей логике предполагает, что медиану этой группы можно найти, разделив указанную выше последовательность на два блока

50 45 40 35 30

25 20 15 10

затем найдя медиану каждого блока. Вместо этого алгоритм медианы медианов будет рекурсивно называть себя полным набором данных 50 45 40 35 30 25 20 15 10. Внутри это разбивает группу на пять из пяти и сортирует их и т.д., Но это делает так, чтобы определить точку раздела для шага секционирования, и на этом этапе секционирования, что рекурсивный вызов найдет истинную медиану медианов, который в этом случае будет 30. Если вы используете 30 в качестве медианы как шаг разбиения на исходный алгоритм, вы действительно получаете очень хороший раскол по мере необходимости.

Надеюсь, это поможет!

Ответ 2

Вот псевдокод для медианы алгоритма медианов (слегка измененный в соответствии с вашим примером). Псевдокод в wikipedia не может изобразить внутреннюю работу вызова функции selectIdx.

Я добавил комментарии к коду для объяснения.

// L is the array on which median of medians needs to be found.
// k is the expected median position. E.g. first select call might look like:
// select (array, N/2), where 'array' is an array of numbers of length N

select(L,k)
{

    if (L has 5 or fewer elements) {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    // The code to follow ensures that even if M turns out to be the
    // smallest/largest value in the array, we'll get the kth smallest
    // element in the array

    // Partition array into three groups based on their value as
    // compared to median M

    partition L into L1<M, L2=M, L3>M

    // Compare the expected median position k with length of first array L1
    // Run recursive select over the array L1 if k is less than length
    // of array L1
    if (k <= length(L1))
        return select(L1,k)

    // Check if k falls in L3 array. Recurse accordingly
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))

    // Simply return M since k falls in L2
    else return M

}

Взяв ваш пример:

Медиана функции медианов будет вызываться по всему массиву из 45 элементов, таких как (с k = 45/2 = 22):

median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2)

При первом вызове M = select({x[i]}, n/10) массив {x[i]} будет содержать следующие числа: 50 45 40 35 30 20 15 10. В этом вызове n = 45 и, следовательно, вызов функции выбора будет M = select({50 45 40 35 30 20 15 10}, 4)
Второй раз вызывается M = select({x[i]}, n/10), массив {x[i]} будет содержать следующие числа: 40 20. В этом вызове n = 9 и, следовательно, вызов будет M = select({40 20}, 0). Этот вызов выбора вернет и присвоит значение M = 20.

Теперь, дойдя до того, что у вас возникло сомнение, мы теперь разделим массив L вокруг M = 20 на k = 4.

Помните массив L здесь: 50 45 40 35 30 20 15 10.

Массив будет разбит на L1, L2 и L3 в соответствии с правилами L1 < M, L2 = M и L3 > M. Следовательно:
L1: 10 15
L2: 20
L3: 30 35 40 45 50

Так как k = 4, оно больше, чем length(L1) + length(L2) = 3. Следовательно, поиск будет продолжен с помощью следующего рекурсивного вызова:
return select(L3,k-length(L1)-length(L2))

что означает:
return select({30 35 40 45 50}, 1)

который в результате вернет 30. (так как L имеет 5 или меньше элементов, следовательно, он вернет элемент в k-й, то есть 1-ю позицию в отсортированном массиве, который равен 30).

Теперь M = 30 будет получен в первом вызове функции select по всему массиву из 45 элементов, и та же логика секционирования, которая разделяет массив L вокруг M = 30, будет применяться, чтобы, наконец, получить медиану медиан.

Уф! Надеюсь, я был достаточно подробным и достаточно ясным, чтобы объяснить медиану алгоритма медианов.