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

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

We also assume a limit on the size of each word of data. For example, when working with inputs of size n, we typically assume that integers are represented by c lg n bits for some constant c>=1. We require c>=1 so that each word can hold the value of n, enabling us to index the individual input elements, and we restrict c to be a constant so that the word size doesn't grow arbitrarily.( If the word size could grow arbitrarily, we could store huge amounts of data in one word and operate on it all in constant time - clearly an unrealistic scenario.)

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

11
задан Rndm 21 July 2012 в 14:10
поделиться