2019-gate-computer-science-and-it-practice.pdf/Q14-alg1

Вопрос: Q14-alg1-31d68c

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?

Ответы

• Сортировка слиянием
• Быстрая сортировка
• Бинарный поиск
• Умножение Штрассена
• Правильный ответ: Все перечисленные алгоритмы

Объяснение

В каждом алгоритме используется данный подход:

• в сортировке слиянием функция merge сортирует пары отсортированных подмассивов,
• в быстрой сортировке функция partition применяется после разбиения к каждому из двух образовавшихся массивов после разбиения опорным элементом,
• в бинарном поиске — разделение по ключу, и рекурсивный поиск в левой и правой структуре.
• с умножением Штрассена аналогично — разделение матриц на кучу блоков и рекурсивное их перемножение.

Исходники — вопрос 14 на 223 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.