Временная сложность алгоритма детерминированного выбора

Question

Недавно я просмотрел видео о том, как мы можем сделать алгоритм выбора, выполняющийся в O (n) времени, и я смущен одним шагом в процессе создания алгоритма.

В видео говорится, что мы должны разбить набор чисел или массива на n/5 групп из 5 элементов и остальных элементов в другой группе. Затем мы находим медиану каждой группы. Затем мы находим медиану медианов и используем ее как стержень и так далее.

Однако, чтобы найти медиану каждой группы, мы должны сначала отсортировать группы. В видео говорится, что использование сортировки сортировки или сортировки слияния, но не эти алгоритмы O (nlogn)? Итак, как может общее время работы быть O (n), если сортировка уже принимает O (nlogn)?

Вот видео для справки: https://www.youtube.com/watch?v=YU1HfMiJzwg

Answer 1

набор чисел или массива в n/5 групп из 5 элементов и .... Тогда мы находим медиану каждой группы ... Однако, чтобы найти медиану каждой группы, мы должны отсортировать групп. В видео говорится, что использование сортировки сортировки или сортировки слияния, но не эти алгоритмы O (nlogn)? Итак, как может общее время работы быть O (n), если сортировка уже принимает O (nlogn)?

Не совсем верно. Поскольку сортировка группы из 5 только 5log(5), и мы сделали это в n\5 раз. Это будет n*5/5 log(5) = nlog(5). Это все еще линейно.

Answer 2

Я был неправ, прежде чем редактировать.

Я читал наборы из n/5 элементов вместо n/5 наборов из 5 элементов.

Сортировка N/5 наборов из 5 или менее элементов - O(N/5 * 5*log(5)), что является линейным по сложности.