Алгоритм поиска медианы в медиане медиан

Question

Я знаю, что формула для алгоритма медианы медиан: T(n)<= T(0.7n)+T(0.2n)+O(n) и O(n) получены из определения медианы каждого блока (размер 5), и мне интересно, почему для поиска медианы требуется O (n)каждого блока ... это похоже на то, что нахождение медианы одного блока занимает O(1).Как это возможно?

Answer 1

Размер каждого блока постоянен (5).Следовательно, поиск медианы каждого блока находится в O(1) (отсортируйте блок по O(1) и возьмите средний индекс в качестве медианы).Следовательно, поиск медианы всех блоков находится в O(n).И после этого найдите медиану медианы каждого блока, на которую есть ответ в вашем другом вопросе .