Дерево решений сортировки групп в список

Question

Дайте нижнюю границу времени для создания одного отсортированного списка из n чисел, которые находятся в k группах. Таким образом, наименьшее n/k является первым и так далее.

Так что я некоторое время застрял в этой проблеме, и я действительно не уверен, как это сделать. Я знаю, как создать дерево решений, но я не понимаю, как я должен это делать в контексте этой проблемы. Я не обязательно понимаю проблему, но, похоже, она достаточно ясна, чтобы ее можно было решить для людей. Любая точка в правильном направлении или разъяснение будет чрезвычайно оценена.

Answer 1

Ваш вопрос сложный, поскольку он предполагает, что номера n были разделены на группы k, причем сами группы упорядочены. Я буду здесь считать, что номера внутри каждой группы - , а не. Если числа уже были отсортированы в каждой группе, это сделало бы проблему тривиальной.

Дерево решений для решения вашего вопроса может быть построено с помощью поддерева k, по одному для каждой группы, причем каждое поддерево подключается к следующему поддереву. Причина этого в том, что сами группы уже отсортированы, и нам нужно только отсортировать каждую группу. Нижняя граница времени выполнения возникла бы, если бы нам нужно было пройти это дерево вдоль один путь, чтобы найти правильный листовой узел (и отсортированный список). Это означает, что нижняя граница высота дерева, которое:

O(k * lg n/k)

Чтобы сломать это выражение:

lg n/k является высота каждого из k поддеревьев

k * lg n/k является высота всего дерева решений (есть подкатегории k)

Прочтите это excellent PDF from the CS 401 class at the University of Illinois at Chicago w он полностью объяснит вашу первоначальную проблему, а также покажет вам доказательство того, как я пришел к выражению Big Omega, которое я дал выше.

Answer 2

Я не уверен, что такое «нижняя граница» в вопросе.

Если

(...) числа, в к группам. Таким образом, наименьшее n/k является первым и так далее.

означает группы уже отсортирован (даны в правильном порядке), а затем

время, чтобы произвести один отсортированный список

минимален, если числа внутри группы уже отсортированы. Тогда минимальное время для создания отсортированного списка - k*(n/k-1) + k*(n/k) + (k-1) = O(n+k) для тестирования каждой из групп «k» для сортировки, преобразования каждой группы в связанные списки путем добавления каждого элемента в порядок и последующего объединения групп в один список результатов или массив.

С другой стороны, если мы хотим, чтобы минимальное время, необходимое для создания результата несмотря на первоначальные (отсутствие) порядок ввода чисел в группах, то ответ O(k*(n/k)*ln(n/k)) + n = O(n*ln(n/k)) общего алгоритма сортировки k группам n/k элементов каждый, затем помещая все n элементов в результирующий список или массив.