Как хранение больших чисел увеличивает сложность пространства?

Question

Для назначения я должен был написать алгоритм, который позволял бы мне использовать не более n + O (log (n)) дополнительных битов памяти (подробности о том, что алгоритм фактически должен был делать, не важныздесь), где n - размер входного массива.

Я представил алгоритм, который проходит все тестовые случаи;однако мой грейдер говорит, что я использую более n + O (log (n)) битов памяти. Их причина в том, что, как часть моего алгоритма, я добавляю количество (n * i) к каждому элементу в массиве (где i = 1, 2, 3, ... n. I - переменная индекса впетля). Они говорят, что при очень больших значениях n я буду использовать больше памяти для хранения больших чисел.

Это приводит меня к следующему вопросу: правда ли, что моя сложность пространства превышает n + O (log(n)) биты, добавляя n * i к каждому числу? Мой опыт анализа алгоритмов довольно ограничен, но я лично никогда не видел, чтобы хранение больших чисел оправдывало увеличение сложности пространства. Но давайте скажем для аргумента, что это увеличивает сложность - я буду использовать больше, чем n + O (log (n)) бит?

Я хотел бы сформулировать аргумент для вызова, но я просто хочу убедиться, что я прав, прежде чем сделать это.

Answer 1

Пусть b1 будет количеством битов для каждого числа перед добавлением (i*n) к, а b2 будет числом после этого.

Неравенство (1):

b2-b1 <= log(n*n) = 2log(n)

Доказательство (1):

Lemma 1: binary number is the best coding scheme for integers in memory.

Lemma 2: The sum of 2 integers always has the result shorter than the sum of each number's sizes.

Из неравенства (1)

В крайнем случае, если b1 -> 0, то b2 = 2log(n), поэтому увеличение пространства равно 2nlog(n),Общее пространство будет C + O(nlog(n))

Отказ от ответственности: это не доказательство вашей проблемы, потому что я не знаю точно, сколько битов вы использовали для каждого числа в начале.