Изменения
Нет описания правки
# Найдите минимальное число сравнений для сортировки 5 элементов
# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
# Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов, за полиномиальное время.
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
# Докажите, что любой алгоритм, проверяющий, есть ли в массиве два одинаковых элемента с использованием только сравнений элементов, работает за $\Omega(n \log n)$
</wikitex>
