Это классное задание, поэтому я не ищу решения, просто помогу определить, находимся ли мы на правильном пути, и указатели в правильном направлении.
Проблема
Мы должны разработать алгоритм для поиска трех самых маленьких элементов в массиве. Мы должны использовать парадигму «разделяй и властвуй». Номера должны быть возвращены в отсортированном Triple. В худшем случае алгоритм должен работать за линейное время. Можно считать, что вход имеет размер 3 * 2 ^ (k - 1)
Правильность и время работы должны быть подтверждены (по индукции).
Наше текущее решение
def FindSmallest(list):
if list.size <= 3:
Sort(list)
return list
L = FindSmallest(list / 2)
R = FindSmallest(list / 2)
Triple = Merge(L, R)
return Triple
Псевдокодовая реализация алгоритма.
Теория
Мы рекурсивно делим исходную задачу пополам, пока подзадачи не будут иметь размер 3. Затем мы отсортируем подзадачи. Продвигаясь вверх по стеку рекурсии, мы объединяем подзадачи размером 3 (включая 3 наименьших элемента из обоих), пока не останется только контейнер, который возвращается как Triple.
Сортировка
Поскольку сортировка выполняется для контейнера фиксированного размера (3), мы представляем, что время их выполнения будет постоянным; максимум 3 сравнения и 3 обмена.
1024 * Объединение *
Объединение двух отсортированных массивов размером 3 также должно занимать постоянное время. Поскольку мы объединяем не на месте, процесс должен выполнить 3 сравнения и 3 назначения. Полученный объединенный контейнер будет иметь размер 3.
Время состязания
Значения
Количество делений / слияний: (n / 3) - 1
Количество подзадач / сеансов сортировки: (n / 3)
формула повторения
Мы считаем, что это повторение будет применяться к нашему алгоритму:
T (n) = 2T (n / 2) + 2 (2n - 3)
К сожалению, мы озадачены тем, как использовать это повторение для доказательства нашего времени выполнения по индукции.
Любая помощь будет высоко ценится. Пожалуйста, спросите меня, если я что-то пропустил.