Понимание предположений о размере машинного слова при анализе компьютерных алгоритмов

Я читаю книгу Введение в алгоритмы Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штаина. Во второй главе в разделе "Анализ алгоритмов" упоминается, что:

Мы также предполагаем ограничение на размер каждого слова данных. Например, при работе с входами размера n мы обычно предполагаем, что целые числа представлены c lg n битами для некоторой константы c >= 1. Нам нужно c >= 1, так что каждое слово может содержать значение n, что позволяет нам индексировать отдельные элементы ввода, и мы ограничиваем c константой, чтобы размер слова не увеличивался произвольно. (Если размер слова может расти произвольно, мы можем хранить огромное количество данных одним словом и работать на нем все в постоянное время - явно нереалистичный сценарий.)

Мои вопросы - почему это предположение о том, что каждое целое число должно быть представлено c lg n битами, а также, как c >= 1 является случаем, позволяет нам индексировать отдельные входные элементы?

Ответ 1

во-первых, на lg они, по-видимому, означают логарифмическую базу 2, поэтому lg n - это количество бит в n.

то, что они говорят, это то, что если у них есть алгоритм, который принимает список чисел (я более конкретный в моем примере, чтобы облегчить его понимание), например 1,2,3,...n, то они предполагают, что:

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

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

Ответ 2

Для представления целых чисел размера n требуется, по крайней мере, lg n бит, так что нижняя граница количества бит, необходимых для хранения входов размера n. Установка константы c >= 1 делает ее нижней границей. Если постоянный множитель был меньше 1, у вас не было бы достаточного количества бит для хранения n.

Это упрощающий шаг в модели ОЗУ. Он позволяет обрабатывать каждое индивидуальное входное значение, как если бы оно было доступно в одном слоте (или "слове" ) памяти, вместо того, чтобы беспокоиться о осложнениях, которые могут возникнуть в противном случае. (Загрузка, сохранение и копирование значений разных размеров слов занимала бы различное количество времени, если бы мы использовали модель, допускающую различные длины слов.) Это то, что означало "позволяя нам индексировать отдельные элементы ввода". Предполагается, что каждый входной элемент проблемы доступен по одному адресу или индексу (что означает, что он соответствует одному слову памяти), что упрощает модель.

Ответ 3

Этот вопрос был задан очень давно, и объяснения действительно помогли мне, но я чувствую, что все еще может быть немного больше разъяснений о том, как появился lg n. Для меня очень важно говорить через вещи:

Позволяет выбрать случайное число в базе 10, например 27, нам нужно 5 бит, чтобы сохранить это. Зачем? Хорошо, потому что 27 - 11011 в двоичном формате. Уведомление 11011 имеет 5 цифр, каждая "цифра" - это то, что мы называем бит, следовательно, 5 бит.

Подумайте о том, что каждый бит является слотом. Для двоичного файла каждый из этих слотов может содержать 0 или 1. Какое наибольшее число я могу хранить с 5 битами? Наилучшим образом, наибольшее число заполнило бы каждый слот: 11111

11111 = 31 = 2 ^ 5, поэтому для хранения 31 нам нужны 5 бит, а 31 - 2 ^ 5

Как правило (и я буду использовать очень явные имена для ясности):

numToStore = 2 ^ numBitsNeeded

Так как log является математическим обратным показателем экспоненты, получаем: log (numToStore) = numBitsNeeded

Поскольку это, скорее всего, не приведет к целому числу, мы используем ceil для округления нашего ответа. Поэтому, применяя наш пример, чтобы узнать, сколько бит необходимо для хранения номера 31:

log (31) = 4.954196310386876 = 5 бит