Как понять сложность алгоритма медиан медиан?

Question

Я следую описанному здесь объяснению https://brilliant.org/wiki/median-finding-algorithm/ Сложность части алгоритма Медиана медиан, и она описывает примерно 3n / 10 лучших случаев и 7n / 10 худших случаев. Я не понимаю, как это получается 3n/ 10 и 7н / 10 частей?в то же время упоминалось, что «для каждого из этих элементов есть два элемента, которые меньше его (поскольку эти элементы были медианами в списках из пяти элементов - два элемента были меньше, а два элемента были больше)».

Answer 1

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

Медиана 2k+1 имеет k элементов с обеих сторон.Тогда медиана медиан из (2k+1)(2l+1) элементов, безусловно, имеет (k+1)(l+1)-1 элементов с обеих сторон (каждая медиана не меньше, чем k+1 элементов, и есть l+1 медиан, все не меньше медианы медиан).

Фракция составляет ((k+1)(l+1)-1)/(2k+1)(2l+1).В случае k=2 имеем (3(l+1)-1)/5(2l+1) ~ 3l/10.

Answer 2

Разделив список на n/5 группы по 5 и найдя медиану медиан p, вам нужно определить наихудший случай, сколько элементов вам еще нужно найти для истинной медианы.

Рассмотрим, сколько элементов списка должно быть меньше, чем p (или равно, которое в простом списке отдельных элементов содержит только p)

Половина из групп n/5иметь медиану меньше p.В этих группах есть 3 элемента - медиана и два меньших значения, которые должны быть меньше p.Мы не знаем, больше ли элементы больше p, и не знаем, есть ли у элементов в группах с медианой больше p элементы меньше p.

Таким образом, в худшем случае мы определяем, что 1/2 * n/5 групп - n/10 групп - каждая имеет 3 элемента, которые определенно меньше, чем p.Это 3n/10 элементов.В худшем случае все другие элементы больше p, поэтому 7n/10 элементов больше p для рекурсивного выполнения этого алгоритма.