Другая формулировка вопроса
Вопрос можно представить так. У вас есть n шаров разных размеров. Вы хотите организовать их в n / k сегментов так, чтобы каждый блок содержал ровно k шаров. Кроме того, эти ведра расположены в линию, в которой самое левое ведро содержит k самых маленьких шариков. Второе ведро слева содержит следующие k шаров, которые были бы самыми маленькими, если бы мы убрали самое левое ведро. Крайнее правое ведро содержит k самых больших шаров.
Но внутри каждого ведра у вас нет порядка. Если вам нужен самый большой шар, вы знаете, в каком ведре вы должны начать поиск, но вам все равно нужно искать в нем.
Я буду использовать термин «ведро» вместо подпоследовательности, поскольку подпоследовательность заставляет меня задуматься о том, не важно, что важно, так это принадлежность, поэтому ведро легче для меня.
Проблема с предполагаемой сложностью предполагаемого решения
Вы утверждаете, что k длина (или размер) каждого ведра. Поэтому, естественно, оно может быть между 1 и n.
Затем вы спрашиваете, существует ли решение O (n log k), которое может организовать элементы таким образом. Существует проблема с предложенной вами сложностью, которую легко увидеть, когда мы рассмотрим две крайности k = 1 и k = n.
k = n. Это означает, что у нас есть только одно большое ведро. Это тривиально, так как никаких действий не требуется. Но ваша предполагаемая сложность была O (n log k) = O (n log n), когда k = n.
Давайте также рассмотрим k = 1, поскольку она имеет аналогичную, но обратную проблему.
* * к тысяча двадцать-два = 1. Каждое ведро содержит 1 шар, и нам нужно n ведер. Это то же самое, что просить нас полностью отсортировать всю последовательность, которая в лучшем случае будет O (n log n). Но предложенная вами сложность была O (n log k) = O (n log 1) = O (n * 0) = 0. Запомните log 1 = 0. Кажется, что предложенная вами сложность совсем не подходит к проблеме.
Мы можем остановиться здесь и сказать. Нет, вы не можете делать то, что вы делаете sh на O (n log k), потому что не имеет смысла, что проблема станет более сложной, когда вы уменьшите количество сегментов. Что еще более важно, это не может стать легче, если вы увеличите количество сегментов.
Если бы мне было поручено выполнить эту сортировку вручную, я бы сказал, тривиально сортировать в один сегмент. Два легко. Три будет сложнее, чем два. Если у вас есть n блоков, то это так сложно, как только можно!
Ответ за измененную сложность Однако интересно рассмотреть, что произойдет, если мы исправим предложенную сложность, что мы вместо этого спрашиваем следующее. Есть ли способ разбить на эти сегменты в O (n log b), где b - количество сегментов (b = n / k)?
Кажется, что здесь есть смысл в крайних случаях.
Ь = 1. Одно ведро Сортировка не требуется. O (n log b) = O (n log 1) = O (0). (технически это все еще может быть O (1))
b = n. п ведра. Требуется полная сортировка. O (n log b) = O (n log n).
Таким образом, решение кажется возможным. Но это выходит за рамки вопроса сейчас. Однако я подозреваю, что Алгоритмы выбора и quickselect - это путь к go.