Понятие дополнительной памяти.

[Maxim19]

Всем здравствуйте, возник вопрос: когда пишут О(1) дополнительной памяти в задачах на алгоритмы, имеют ввиду величину числа? Ну например записать куда то сумму всех положительных значений множества. В решениях задач такую сумму считали за О(1), как и подобные штуки. Но если так считают, то тогда можно схитрить и в числа записывать много данных, например разграничивая нулями последовательность положительных целых чисел менее 10. Кто понимает в этой теме, объясните мне, может это я не прав?

[worm2]

Разумеется, в таких случаях неявно предполагается, что всевозможные значения, возникающие в ходе вычислений, не приводят к переполнению разрядности. Хотя формально, даже для записи натурального числа из диапазона от 1 до $M$ требуется $O(\log M)$ памяти, но на практике почти всегда считают, что это $O(1)$.

Но тут могут быть нюансы, действительно существенные на практике.
Есть, например, такая задачка: дан массив из $N-1$ различных натуральных чисел, каждое из которых не превосходит $N$. Таким образом, в массиве есть все числа от 1 до $N$, кроме одного. Нужно его найти (разумеется, быстро, за $O(N)$ времени и за вот эту вашу $O(1)$ дополнительной памяти).
Решение: сумма всех $N$ чисел от 1 до $N$ известна, нужно из неё вычесть по очереди все числа массива, и то, что получится, и будет искомым числом.
Конечно же, здесь неявно подразумевается, что сумма ($N(N+1)/2$) умещается в диапазон представимых целых чисел.
Модифицируем задачу: теперь чисел $N-2$, и нужно найти два отсутствующих числа.
Возможное решение: рассчитаем произведение $N!$ и сумму $N(N+1)/2$ всех чисел от 1 до $N$, далее будем (делить на/вычитать из него) все числа массива последовательно, пока не получим произведение и сумму двух искомых чисел. Потом воспользуемся теоремой Виета, решим квадратное уравнение и получим сами числа.
Всё так же просто и красиво, но вот тут уже есть нюанс. $N!$ имеет разрядность $O(N)$, и тут уже нельзя подразумевать, что его результат влезет в диапазон представления машинного числа. Собственно, и вычислить $N!$ за время $O(N)$ никак не получится.

[мат-ламер]

Maxim19 в сообщении #1575430 писал(а):

Ну например записать куда то сумму всех положительных значений множества.

Что это за зверь такой?

-- Чт дек 29, 2022 15:13:55 --

Maxim19 в сообщении #1575430 писал(а):

Всем здравствуйте, возник вопрос: когда пишут О(1) дополнительной памяти в задачах на алгоритмы, имеют ввиду величину числа?

Я думаю, что имеют в виду объём дополнительной памяти в гигабайтах.

[mihaild]

Довольно часто в модели вычислений предполагается, что одна ячейка памяти способна хранить числа порядка максимального встречающегося в задаче (включая размеры массивов и т.д.), и что арифметика на таких числах занимает константное время.

мат-ламер в сообщении #1575476 писал(а):

Что это за зверь такой?

Есть множество чисел, в нём есть положительные числа, просуммировали их и записали куда-то сумму.

мат-ламер в сообщении #1575476 писал(а):

Я думаю, что имеют в виду объём дополнительной памяти в гигабайтах.

В гигабайтах или битах - на асимптотику не влияет.

[Maxim19]

Понятно теперь, спасибо. Но всё же в таких задачах разрешается например число делать таким, чтобы в нём был записан массив? По сути то это всё то же число

[worm2]

Конечно, нет, не разрешается.
Но если у вас O(1) памяти, вы не обязательно должны ограничиваться одним числом.
Можете завести два числа, три, десять, да хоть тысячу, но! Этой тысячи должно хватить на входные данные любого размера: миллиона, миллиарда, $10^{1000}$.

[Евгений Машеров]

Такие задачи ставятся всё же с расчётом на некое практическое применение. Соответственно "число" это "ячейка памяти реально возможной ЭВМ". Обойти условие адвокатскими приёмами "используем одно число, но произвольно большой длины, куда записываем все числа" - можно, но неспортивно и практически неприложимо.

[Maxim19]

Теперь понятно, спасибо