Изменения

Перейти к: навигация, поиск

Список заданий по ДМ-сем2

2 байта добавлено, 21:26, 19 мая 2014
\log, однако!
# Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов
# Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов.
# Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны# Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$
# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент. Предложите способ или докажите, что это невозможно.
# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
Анонимный участник

Навигация