#big-o #treeset #removeall
#big-o #набор деревьев #removeall
Вопрос:
Я посещаю курс Java data structures atm. В одном из моих заданий мне предлагается выбрать структуру данных по моему выбору и написать программу проверки орфографии. Я нахожусь в процессе проверки производительности различных структур данных.
Я зашел в api для набора деревьев, и вот что там написано… «Эта реализация обеспечивает гарантированную временную стоимость журнала (n) для основных операций (добавление, удаление и содержит)».
будет ли это включать removeAll()?
как еще я мог бы это выяснить
заранее благодарю вас
Комментарии:
1. Если бы я писал программу проверки орфографии, я бы использовал набор хэшей для хранения словаря. Это дает вам постоянный доступ ко времени к каждому элементу.
Ответ №1:
Это не включало бы removeAll(), но я должен не согласиться с ответом polkageist . Возможно, что removeAll() может выполняться за постоянное время в зависимости от реализации, хотя наиболее вероятным кажется, что выполнение будет происходить за линейное время.
Я думаю, что NlogN был бы таким, если бы он был реализован практически худшим способом. Если вы удаляете каждый элемент, нет необходимости искать элементы. Любой элемент, который у вас есть, должен быть удален, поэтому нет необходимости в поиске.
Ответ №2:
Нет. Для набора аргументов размером k наихудшая верхняя граница removeAll(), конечно, равна O (k * log n) — потому что каждый элемент, содержащийся в наборе аргументов, должен быть удален из набора деревьев (для этого требуется, по крайней мере, их поиск), каждый из этих поисков приводит к стоимости log n.