Изображение, объясняющее первый алгоритм
Обобщенная медиана медиан для подсписка размера a
Из этого алгоритма мы можем Посмотрите, чем для того, чтобы получить линейное время выполнения алгоритма, константа должна быть больше 4. Однако мне было интересно, что произойдет, если я разделю n / 8 подсписков и выберу 4-е наибольшее число каждого подсписка в качестве медианы.
Я ожидал, что время работы будет линейным, так как 8> 4, однако, когда я вычислил время работы, я нашел O (nlogn). Расчет для подсписка размером 8
Может кто-нибудь сказать мне, если я ошибался, и объяснить, почему размер подсписка всегда должен быть нечетным?