Если алгоритму требуется целое число, которое может содержать число n (например, для подсчета размера входного массива), это целое число должно иметь порядок log(n) пробела (правильно?).
Если это единственное пространство, масштабируемое с n, то является ли пространственная сложность алгоритма O(logn)?
Формально это зависит от используемой модели вычислений. В классической модели машины с произвольным доступом с фиксированным размером слова просто сохраняется длина n входных данных действительно требует O(log n) места (а простая арифметика с такими числами занимает O(log n) времени). С другой стороны, в трансдихотомической модели предполагается, что размер слова логарифмически растет с размер ввода n, требуется только O(1) пространства (и времени). Другие модели могут дать еще и другие ответы.
На практике большинство анализа алгоритмов предполагает, что простая арифметика над целыми числами среднего размера (т. е. пропорциональными входная длина) может быть выполнено за постоянное время и пространство. Практическая причина этого, помимо того факта, что это упрощает анализ, заключается в том, что на практике логарифм входной длины не может стать очень большим даже на компьютере, способном считать от нуля до, скажем, 2< sup>256, не говоря уже о чтении такого количества входных данных, вероятно, навсегда за пределами возможностей человечества построить с использованием известной физики. Таким образом, для любых мыслимых реалистичных входных данных вы можете просто предположить, что машина с размером слова 256 бит может хранить длину входных данных в одном слове (и что машины с меньшим размером слова по-прежнему нужно только небольшое постоянное количество слов).
Здесь n ограничено, т.е. n будет 32-битным целым числом со знаком, поскольку размер массива имеет определенные ограничения. Итак, log(32) ограничено и его O(1)
nограничено, и в этом случае это O (1). - person Mark Ransom schedule 18.08.2016