Рассмотрим вариацию алгоритма Quick-Sort, детерминированно выбирающего в качестве разделителя первый элемент текущего отрезка. Пусть на вход алгоритму поступает случайная последовательность, в которой все ключи различны, а все их перестановки равновероятны. Тогда каким будет матожидание глубины рекурсии?

Правильный ответ:

• # При каком значении [l0, r0] в корне дерева Prirority Search Tree не имеет смысла дальше искать в дереве, если область "колодца" задаётся так: [l1, r1] x [r1, +∞]?
• # Считается ли компьютерная память важным ресурсом, учитывающимся при разработке эффективного алгоритма?
• # Какая сложность у алгоритма сортировки выбором?
• # Выберите утверждения, характерные для алгоритма быстрой сортировки (quick-sort).
• # В каких случаях можно использовать прямую адресацию при реализации отображения?