Понимание «алгоритм выбора» Алгоритм

Question

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

Мы 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 

1. Первый шаг сортировки каждой группы (в этом случае они уже отсортированный)

2. Второй шаг рекурсивно, фи-й «истинный» медиана медиан (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.

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

Answer 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 в качестве медианы как шаг разбиения на исходный алгоритм, вы действительно получаете очень хороший раскол по мере необходимости.

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

Answer 2

Вот pseudocode для медианы алгоритма медианов (слегка измененный в соответствии с вашим примером). Псевдокод в 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) 

1. В первый раз 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)

2. Второй раз 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 будет применяться, чтобы наконец получить медианы медиан.

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