Время O(n + m log m), память O(m), если сортируются все m символов алфавита. Устранение квадратичного поиска не убирает стоимость последующей сортировки.
Какова сложность после замены повторного поиска счётчиками
Время O(n + m log m), память O(m), если сортируются все m символов алфавита. Устранение квадратичного поиска не убирает стоимость последующей сортировки.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Алгоритм раньше искал символы повторным сканированием текста. Теперь за проход строит частоты алфавита размера m и сортирует m разных символов для вывода. Какова итоговая оценка?
Ответ
Время O(n + m log m), память O(m), если сортируются все m символов алфавита. Устранение квадратичного поиска не убирает стоимость последующей сортировки.
Если сортируются только k встреченных символов, используйте O(n + k log k) и O(k) при подходящем словаре. Для заранее упорядоченного конечного алфавита сортировка может быть не нужна, тогда остаётся O(n+m). Указывайте, включает ли память буфер выходного текста.