#1158792

#1158792: Алгоритм Хаффмана строит Σ-дерево снизу вверх, и на каждой итерации он объединяет два дерева, имеющие наименьшие суммы частот соответствующих символов. Сколько слияний выполнит жадный алгоритм Хаффмана до остановки? Число символов обозначается n = |Σ|

Алгоритм Хаффмана строит Σ-дерево снизу вверх, и на каждой итерации он объединяет два дерева, имеющие наименьшие суммы частот соответствующих символов. Сколько слияний выполнит жадный алгоритм Хаффмана до остановки? Число символов обозначается n = |Σ|
Варианты ответа:
  • n – 1.
  • n.
  • (n + 1)n / 2.

🔒 Ответ будет доступен после оплаты

Тематика: Вычислительная математика Основы алгоритмизации и программирования Теория программирования (алгоритмизация)
📚 Похожие вопросы по этой дисциплине
Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути от исходной вершины до всех остальных. Каким будет время работы алгоритма как функции от m (числа ребер) и n (числа вершин)? Имеется куча с n объектами. Какую из следующих задач можно решить с помощью операций Вставить и Извлечь минимум с временем O(1) и дополнительной работы с временем O(1)? Предположим, что набор данных S вставляется в фильтр Блума, который использует m хеш-функций и битовый массив длины n. Первое допущение говорит, что для каждого ключа k, каждой хеш-функции hi и каждой позиции q∈ {0, 1, 2,..., n − 1} в массиве вероятность того, что hi (k) = q равна в точности 1/n. Второе допущение предполагает, что вероятность того, что hi (k1) = q, а также hj(k2) = r, равна произведению индивидуальных вероятностей, также рассчитываемая как 1/n2. Какова вероятность того, что первый бит массива равен 1 (с учетом эвристических допущений)? Какое из перечисленных ниже свойств не входит в определение хорошо спроектированной хеш-функции? Что выведет интерпретатор для следующей программы (версия Python 3.6+)? def get_name_and_decades(name, age):     print(f"My name is {name} and I'm {age / 10:.5f} decades old.") get_name_and_decades("Leo", 31)