Изменения
Нет описания правки
# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
# Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.
# Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).
# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Преложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Преложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
# Оцените число итераций, которые вещественный двоичный поиск с условием выхода "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
# Оцените число итераций, которые вещественный двоичный поиск с условием выхода "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
</wikitex>
