# В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ (возможно пересекающихся) отрезков из выбранного множества
# На базе предыдущего задания решите задачу о минимуме на отрезке без изменения элементов за $O(1)$ на запрос и $O(n \log n)$ предподготовки.
</wikitex># Постройте массив, в котором сортировка пузырьком делает максимальное число обменов# Постройте массив, в котором сортировка выбором делает максимальное число обменов# Постройте массив, в котором сортировка вставками делает максимальное число обменов# Найдите минимальное число сравнений для сортировки 4 элементов# Найдите минимальное число сравнений для сортировки 5 элементов# Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием O(1) дополнительной памяти# Докажите, что алгоритм QSort с выбором среднего элемента в качестве разделяющего работает на случайном входном наборе в среднем за $O(n \log n)$# Докажите, что алгоритм QSort с выбором случайного элемента в качестве разделяющего на любом входном наборе работает в среднем за $O(n \log n)$# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$# Модифицируйте рандомизированный алгоритм QSort, чтобы искать $k$-й по величине элемент в массиве за время $O(n)$ в среднем
