Отношение повторения для детерминированного c алгоритма выбора

Question

Линейное время детерминировано c Алгоритм выбора. Я прочитал эту ссылку , и повторение подхода «разделяй и властвуй» выглядит следующим образом: T (n) <= 12n / 5 + T (n / 5) + T (7n / 10) </p>

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

Answer 1

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, но не оба, не имеет смысла складывать их размеры вместе.