- Бинарный поиск
Условие работы: список слов должен быть лексографически (в алфавитном порядке) упорядочен.
Для поиска слова в словаре, словарь делим пополам и среднее слово сравниваем с искомым. Если оно совпадает, то поиск окончен, если нет, то смотрим, в верхней или нижней части словаря находится это слово. Делим эту часть пополам. И снова проверяем…
Трудоёмкость: log2N
- Метод линейного списка
Приводим список в соответствии с частотой появления слов. Можно хранить и длину слова.
Вначале проверяем по длине слова, потом пробегаем по списку слов…
Трудоёмкость: меньше n/2
- Хеширование
Один из самых распространенных и оптимальных методов.
Выбираем функцию хеширования F(x)=k, 0<k<m. Все зависит от того, какую функцию мы выберем.
Трудоёмкость: n/m
- Метод индексов
Смотреть 3) при условии, что m=n
Трудоёмкость: ~время определения индекса
