Вопросы
1. У какой классической сортировки время работы гарантированно O(n log n) даже в худшем случае, а дополнительная память нужна только O(1)?
- Пирамидальная сортировка
- Интроспективная сортировка
- Сортировка слиянием
- Быстрая сортировка
Вопросы
2. Как работает бинарный поиск в отсортированном массиве?
- Позиция оценивается с помощью линейной интерполяции между крайними элементами диапазона; затем диапазон сокращается согласно полученной оценке и шаг повторяется до нахождения нужного элемента
- Диапазон последовательно сужается за счёт поэтапного смещения одной из границ на один индекс в сторону искомого значения до совпадения.
- На каждом шаге выбирается элемент в середине текущего диапазона. Если искомое…