Рекуррентное соотношение для алгоритма детерминированного выбора

Для выбора существует линейный детерминированный во времени алгоритм. Я прочитал эту ссылку и повторение подхода "разделяй и властвуй" выглядит так: T(n) ‹= 12n/5 + T(n/5) + T(7n/10)

Однако я не понимаю, почему должно быть T(7n/10). В самой ссылке упоминается, что каждая половина раздела имеет размер (3n/10), поэтому алгоритм повторяется на (6n/10). Даже если мы включим 5 элементов из группы медианы медиан, рекурсия будет на (6n/10+5). Я понимаю, что 7n/10 является допустимой верхней границей размера рекурсии, но не слишком ли слабая верхняя граница здесь?


recurrence selection algorithm divide-and-conquer quickselect
person Jiahao Zhang    schedule 02.03.2020    source источник
comment
Но они уже учитываются в двух разделах (3/10n).   -  person Jiahao Zhang    schedule 02.03.2020
comment
Если вы пройдетесь по алгоритму, это подразумевается. Поскольку 3n/10 означает каждый медианный элемент плюс 2 элемента в этой группе.   -  person Jiahao Zhang    schedule 03.03.2020

Ответы (1)


arrow_upward
0
arrow_downward

7n/10 не является результатом 3n/10 + 3n/10 + n/10; это происходит от выполнения n - 3n/10.

Из ссылки:

Об этом проще говорить в терминах выброшенных элементов (не включенных в призыв).

Аргумент состоит в том, что рекурсивный вызов выполняется для более короткого списка, образованного не включением некоторых элементов. Показывая, что из списка исключено не менее 3n/10 элементов, следует, что включено не более 7n/10 элементов, и эта граница является жесткой, поскольку 3n/10 граница является жесткой.

Таким образом, показано, что L1 и L3 имеют размер не менее 3n/10, показывая, что каждый из них содержит не менее 3 элементов из каждого из n/10 подмножеств; то один из L1 или L3 исключается из рекурсивного вызова, давая результат. Поскольку исключается только один из L1 или L3, а не оба, складывать их размеры вместе не имеет смысла.

person kaya3    schedule 02.03.2020