Каков наиболее эффективный алгоритм хранения и печати символьных, частотных пар?

Question

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

Answer 1

Лучше использовать массив размером 256 (всего символов ascii).
Изначально все значения в массиве равны 0. При чтении символов из текстового документа на английском языке мы можем просто увеличить значение в индексе, равноезначение ascii заданных символов.Следовательно, эти операции могут быть выполнены в O(1) временной полноте без каких-либо накладных расходов (если мы используем hashMap, у нас будут накладные расходы на коллизии в худшем случае).
Так как мы должны перебрать все символы в данном текстовом документе,общая временная сложность предложенного метода составит O(n), где n - длина текстового документа.

Answer 2

Хэш-карта, где ключ = символ и значение = частота будут работать лучше всего для любого вида символов и кодировок.

Если вам нужно только то, что может производить клавиатура, вы также можете использовать массив частот, где F [символьный код ASCII] = частота.

Оба решения имеют постоянное время O (1) для каждой операции.