Я знаю, что линейный выбор (медиана алгоритма медиан) уравнение рецидивы следующим образом:Медиана Медиана алгоритма рекуррентного соотношения
T(n) <= an + T(n/5) + T(7n/10)
Но где эти термины пришли? Я пытался понять, но я очень смущен. Может ли кто-нибудь пролить свет?
Лучшая попытка:
Это уравнение только когда вы медиану групп 5. В противном случае она будет меняться. Часть уравнения - это время, необходимое алгоритму для прохождения всех элементов и группировки их в 5. T (n/5) - это время, которое требуется для того, чтобы медиана была найдена для каждой группы из 5. Как есть п/5 групп 5.
T (7п/10) займет больше времени ...
Когда вы медианы медиан элементы разбиты на 4 квадранта. 3/10 элементов больше медианы медиан, 3/10 элемента меньше медианы медиан. Остальные 4/10 разделены на 2 группы по 2/10. Это те элементы, в которых вы не уверены, что они больше или меньше медианы медиан. Следовательно, максимальное количество элементов, которые вы могли бы иметь, больше или меньше медианы медиан, составляет 3/10 + 2/10 + 2/10 = 7/10. Таким образом, T (7n/10) является частью продолжения уравнения с максимальным сегментом чисел, который больше/меньше медианы медианов ....
Надеюсь, что это имеет смысл.