Фиксированный размер массива O (n) или O (1) в пространстве?

Question

Массив объявлен так:
int array[M], O(1) в космосе или O(n)? где М - некоторое фиксированное значение. Для меня O(n) имеет смысл, потому что это не просто одна переменная, а целый массив. Но тогда я думаю, что это может быть O(1), так как у нас фиксированный размер, и он не меняется!

Answer 1

Если ваш массив имеет фиксированный размер и не изменяется в зависимости от размера ввода, он равен O(1), поскольку он может быть выражен как c * O(1) = O(1), с c, являющимся некоторой константой.Примером может быть, если вам нужен массив размера 5 для хранения состояния в вашем алгоритме, который запускает более миллиона (или другого произвольного числа) целых чисел.Важно то, что M и N независимы.

Если, однако, M представляет размер вашего ввода или значение, которое напрямую зависит от размера ввода (то есть N/2 или какой-либо другойлинейная функция), то действительно M растет вместе с N, входным размером, поэтому он будет O(N).Примером может служить массив, содержащий все входные числа, для которых вы хотите запустить алгоритм (т. Е. Определить сумму квадратов).

Answer 2

Я бы сказал, O (1), когда М является константой. Если это O (n), его размер должен быть линейной функцией от M, что в данном случае не равно.

Answer 3

Другие ответы, которые вам дали, верны, формально это O (1) .

Но подумайте очень внимательно о значении «константа». Нотация O (...) предназначена не для измерения производительности реальной компьютерной программы, а для классификации алгоритмов по сложности.

Если вы реализуете алгоритм, который работает с массивом объектов, считывающих каждый из них только один раз (например), вы можете сказать: «Хорошо, давайте установим число элементов в N», но это не сместит Алгоритм в класс сложности O (1), алгоритм по-прежнему O (n), но вы ограничиваете свои тестовые случаи до n = N, где N фиксировано.