Расчет частоты символов в строке

Question

Я ищу наиболее эффективный (время и пространство) алгоритм для вычисления частоты символов для данной строки.

Самый простой алгоритм, который приходит на ум, - это иметь массив флагов (размер = количество различных символов), который вы хотите найти, и увеличить счетчик для соответствующего индекса. Это работает за линейное время. Единственная проблема в этом заключается в требовании к пространству массива флагов, который может возрасти до 256, если нужны все символы ASCII.

Есть ли лучший алгоритм, который может сэкономить пространство / время?

Answer 1

Если вы используете хеш-таблицу для хранения счетчиков, вам нужно пространство, пропорциональное количеству различных символов в вашей строке, и вы все равно можете выполнять вычисления за линейное время. Легко видеть, что вы не можете получить лучшее, чем линейное время, так как вам нужно посмотреть на каждого персонажа хотя бы один раз.

Однако на практике, если ваша строка действительно использует только один байт для хранения символа (то есть это не Unicode), ваш "массив флагов" будет иметь размер около 1 КБ и, таким образом, вероятно, будет лучшим выстрелом, поскольку он не имеет (постоянный фактор) время и пространство для хэш-таблицы.