Как изменяется сложность поиска при использовании отображения «слово → список документов»?

Использование отображения принципиально меняет сложность поиска.

Определение

Отображение «слово → список документов» — это форма инвертированного индекса, реализованная через хеш-таблицу.

Сложность операций

1. поиск слова в отображении — O(1) в среднем,

2. обход списка документов — O(k), где k — число документов с этим словом.

Сравнение с линейным поиском

• линейный поиск: O(n · m),

• поиск по индексу: O(1 + k).

Практический эффект

• быстрый отклик на запросы,

• предсказуемая производительность,

• хорошая масштабируемость.

Вывод

Использование отображения «слово → список документов» радикально снижает сложность поиска и делает систему пригодной для частых запросов.