Главная /
Алгоритмы и структуры данных поиска /
Сколько требуется дополнительной памяти для стандартного алгоритма сортировки слиянием для массива длины N?
Сколько требуется дополнительной памяти для стандартного алгоритма сортировки слиянием для массива длины N?
вопросПравильный ответ:
O(log N)
O(N)
O(N2)
Сложность вопроса
62
Сложность курса: Алгоритмы и структуры данных поиска
76
Оценить вопрос
Комментарии:
Аноним
Спасибо за сайт
09 фев 2017
Аноним
Экзамен сдан на пять. лол
22 фев 2016
Другие ответы на вопросы из темы программирование интуит.
- # Сколько памяти потребуется для предварительного построения таблицы минимумов (RMQ) для отрезков [i, j], где j это степень двойки, какое время будет для запроса после такой предобработки?
- # O-символика датет приближенную оценку. Что нужно сделать, чтобы найти оценку точнее?
- # Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0?
- # Для независимых, равномерно распределенных на множестве {0, ..., m1} случайных величин для каждого ключа ki обозначим через Xi,j случайную величину, равную 1, если h(ki)=h(kj), и 0 в противном случае. Чему равно матожидание случайной величины?
- # Пусть на первом уровне схемы совершенного хэширования используется хеш-таблица размера m = n, n - количество ключей. Пусть ni обозначает количество ключей, получивших (на первом уровне) хеш-значение i (0 <= i < m). Тогда если использовать в каждой ячейке первого уровня вышеописанную схему, свободную от коллизий, сколько потребуется дополнительной памяти?