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