Рубрики

ВОРОТА | GATE MOCK 2017 | Вопрос 37

Рассмотрим проблему вычисления min-max в несортированном массиве, где min и max являются минимальными и максимальными элементами массива. Алгоритм А1 может вычислять мин-макс в сравнениях а1 без разделения и завоевания. Алгоритм А2 может вычислять мин-макс в сравнениях а2 путем линейного сканирования массива. Какая может быть связь между a1 и a2 с учетом наихудших сценариев?

(А) а1 <а2

(B) a1> a2
(С) а1 = а2

(D) Зависит от ввода

Ответ: (Б)
Объяснение: Когда Divide and Conquer используется для нахождения элемента минимального-максимального в массиве, отношение повторения для числа сравнений равно
T (n) = 2T (n / 2) + 2, где 2 — для сравнения минимумов, а также максимумов левого и правого подрешеток

При решении T (n) = 1,5n — 2.
При выполнении линейного сканирования в худшем случае потребуется 2 * (n-1) сравнения, чтобы найти как минимум, так и максимум за один проход.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE MOCK 2017 | Вопрос 37

0.00 (0%) 0 votes