Что проверяет задание
Нужно оценить объём памяти для хранения паролей, идентификаторов, базы пользователей или сообщения фиксированной структуры. Обычно кодирование символов равномерное.
Определения
Идентификатор, слово из символов заданного алфавита фиксированной или ограниченной длины: логин, пароль, код.
Мощность алфавита, сколько различных символов разрешено. От неё зависит минимальное число бит на символ.
Длина кода символа, при равномерном кодировании это наименьшее целое число бит, не меньшее log₂ от мощности алфавита. Память обычно выделяют целыми байтами, поэтому длину часто округляют вверх до кратного 8.
Запись базы, один пользователь или один объект: идентификатор плюс дополнительные поля фиксированного размера.
Служебные данные, поля, которые не являются самим паролем, но занимают место: дата, номер, контрольная сумма, выравнивание.
Выравнивание, округление размера записи до целого числа байт, слов или блоков. Даже если информация занимает 9 бит, хранить могут 2 байта.
Информационный объём базы, произведение числа записей на размер одной записи после всех округлений.
Два разных округления
Сначала округляют код одного символа до целого числа бит. Затем часто округляют весь идентификатор до целого числа байт. Эти два шага нельзя сливать в один: лишние биты на символ и лишние биты в конце записи, разные добавки.
Если сказано «каждый символ кодируется … битами», длину кода уже дали, и log₂ считать не нужно.
Общий алгоритм решения
- Выписать алфавит или его мощность, длину идентификатора и число записей.
- Найти число бит на один символ: по условию или как ⌈log₂ N⌉.
- Найти число бит на идентификатор и округлить так, как предписывает условие (обычно до байта).
- Добавить служебные поля, тоже с их округлением.
- Умножить размер одной записи на количество записей.
- Перевести ответ в те единицы, которые просят: бит, байт, КиБ, МиБ.