Мы бегло прошлись по пяти структурам данных, используемым для представления наборов. Средняя производительность этих структур, когда m мало по сравнению с п, описывается табл. 13.3, где b обозначает количество битов в слове.
Таблица 13.3. Средняя производительность структур для представления наборов
Представление
набора Инициализация Вставка
элемента Вывод
элементов Полное
время
работы Объем памяти в словах
Упорядоченный
массив 1 m m 0(т2) т
Упорядоченный
список 1 m m 0{т2) 2т
продолжение &
Представление
набора Инициализация Вставка
элемента Вывод
элементов Полное
время
работы Объем памяти в словах
Двоичное дерево 1 log т m 0{т log т) Зт
Корзины m 1 m 0{т) Ът
Битовый вектор п 1 n О(т) nib
Эта таблица отражает лишь поверхностные сведения о представлении наборов в подобных задачах. В решении задачи 10 предлагаются другие возможности. В разделе 15.1 главы 15 описаны структуры данных для поиска в наборах слов.
Несмотря на то что мы занимались только структурами данных, пригодными для представления наборов, мы узнали несколько принципов, применимых ко многим задачам программирования.
Опубликовал vovan666
April 17 2013 00:03:42 ·
0 Комментариев ·
3279 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
