Какова сложность линейного поиска слова по всем документам?

Question

Линейный поиск проверяет каждый документ на наличие слова. Если документов n, а средняя длина документа m, то сложность составляет O(n · m). Такой подход плохо масштабируется при росте количества документов или их размера.

YeaHub · Accepted Answer

Линейный поиск — самый простой, но наименее эффективный способ текстового поиска.ОпределениеЛинейный поиск — это последовательная проверка всех документов на наличие искомого слова.Анализ сложностиперебор документов — n,поиск слова внутри документа — m,итоговая сложность — O(n · m).Что влияет на производительностьколичество документов,длина документов,способ хранения текста.Практические ограниченияплохо подходит для частых запросов,неэффективен при больших объёмах данных,увеличивает задержку ответа.Когда допустиммаленькие наборы документов,редкие поисковые запросы,прототипы и учебные задачи.ВыводЛинейный поиск имеет сложность O(n · m) и подходит только для простых сценариев без требований к масштабируемости.