ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 12

Пусть P — массив, содержащий n целых чисел. Пусть t — нижняя верхняя граница количества сравнений элементов массива, необходимых для нахождения минимального и максимального значений в произвольном массиве из n элементов. Какой из следующих вариантов правильный?
(А) t>2n−2
(Б) t>3⌈n/2⌉ и t≤2n−2
(C) t>n и t≤3⌈n/2⌉
(D) t>⌈log ₂ (n)⌉ и t≤n

Ответ: (В)
Объяснение: Потребуется t≤2n−2 сравнений без метода «разделяй и властвуй».

Потребуется t≤ 3⌈n/2⌉ – 2 с техникой «разделяй и властвуй».
Викторина этого вопроса