Таблица частот
Таблица частот — это таблица, в которой для каждого различного значения указано, сколько раз оно встречается в последовательности. Она помогает быстро подсчитать повторения элементов и использовать эти данные в алгоритмах.
Например, для массива \([3, 1, 3, 2, 1, 3]\) различными значениями являются \(1\), \(2\) и \(3\). Таблица частот показывает, что значение \(1\) встретилось два раза, значение \(2\) — один раз, а значение \(3\) — три раза. Порядок строк обычно выбирают по возрастанию значений, но это не обязательно.
Как строят таблицу
- Просматривают все элементы последовательности.
- Для каждого нового значения создают строку таблицы.
- При повторной встрече увеличивают его частоту на единицу.
Здесь \(n\) — длина последовательности, \(k\) — количество различных значений, а \(f_i\) — частота \(i\)-го значения. Поэтому сумма всех частот всегда равна количеству элементов исходной последовательности.
Для последовательности \([2, 4, 2, 2, 4]\) таблица частот будет такой: значение \(2\) — частота \(3\); значение \(4\) — частота \(2\). Сумма частот равна \(3+2=5\), то есть длине последовательности.
Таблица частот не хранит каждый элемент отдельно: одинаковые значения объединяются в одну строку. Таблица вариантов также перечисляет различные значения, но таблица частот дополнительно указывает число появлений. Для текста строят таблицу частот символов, где значениями являются символы.
Какова сумма частот в таблице для последовательности из 12 элементов?
Главное
- Таблица частот сопоставляет каждому различному значению число его появлений.
- Сумма всех частот равна длине исходной последовательности.
- Таблица частот объединяет одинаковые элементы в одну строку.