Массив Пространственная сложность

Question

У меня вопрос:

У меня есть массив "S", в котором есть n объектов.также каждый объект имеет m полей.Я хочу сохранить некоторые из них в другом массиве, например "Q".Я хочу знать, что космическая сложность этого простого метода составляет O(|Q|)?

Answer 1

Сложность пространства - это количество места, необходимое для хранения Q. Пусть s будет размером одного элемента в Q, т.е. s = size of all m fields. Пространство сложность O(n*s). Если все поля имеют одинаковый постоянный размер, вы можете сказать O(n*m).

Answer 2

Размер S это n*sum(sizeofeach(m of n))

Тогда предположим, что вы сохранили объект r, где r<n

Размер q это r*(sum(sizeofeach(m of r))