По размеру файла нельзя надёжно назвать время: оно зависит от оборудования, чтения, токенизации, числа разных слов и N. Оцените сложность и измерьте конкретную реализацию на целевой машине.
Оценка длительности обработки 1‑МБ файла для поиска топ‑N слов
По размеру файла нельзя надёжно назвать время: оно зависит от оборудования, чтения, токенизации, числа разных слов и N. Оцените сложность и измерьте конкретную реализацию на целевой машине.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Имеется текстовый файл размером 1 МБ. Требуется определить примерное время, которое потребуется для выполнения операции поиска N самых часто встречающихся слов в этом файле.
Ответ
По размеру файла нельзя надёжно назвать время: оно зависит от оборудования, чтения, токенизации, числа разных слов и N. Оцените сложность и измерьте конкретную реализацию на целевой машине.
Разбейте работу на чтение, выделение слов, подсчёт частот и выбор top-N. При M словах и K уникальных словах подсчёт занимает ожидаемое O(M), полная сортировка — O(K log K), ограниченная куча — O(K log N).
Для 1 МБ обычно важны постоянные расходы, но обещать конкретное число миллисекунд без измерения нельзя. Зафиксируйте кодировку, правила нормализации, тёплый/холодный файловый кеш и повторите замер несколько раз. Измеряйте полный путь, если пользователь ждёт и чтения, и результата.