Связь сложности времени и сложности пространства

Question

Может ли алгоритм, имеющий временную сложность O ( n ), иметь пространственную сложность O ( n ² ) или более?

Answer 1

взгляните на группы DSPACE и DTIME , которые указывают, какой алгоритм может быть выполнен в какой временной / пространственной сложности, и на отношения между группами .

все алгоритмы, которые используют время O (n), входят в группу DTIME (n).
все алгоритмы, которые используют O (n ^ 2) пробел, находятся в группе DSPACE (n ^ 2).
, начиная с DTIME(n) <= NTIME(n) <= DSPACE(n) < DSPACE(n^2), поэтому каждый алгоритм, который является O (n) временем, также является O (n ^ 2) пробелом.

Answer 2

Сложность пространства не может быть больше, чем сложность времени, потому что запись X единиц пространства занимает время Омега (X).

Answer 3

Поскольку все функции O (n) имеют тривиальное значение O (n ² ) (см., Например, Википедия в формате Big O ), ответ «да».

Answer 4

Чтобы ответить на вопрос, который вы, вероятно, хотели задать: как правило, учет таков, что выделение определенного объема памяти занимает пропорциональное количество времени. Зачем? ну, практически говоря, что-то должно инициализировать память, прежде чем использовать ее.

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

На самом деле в анализе алгоритмов используются различные модели процессоров; если вы хотите, вы можете указать модель, которая говорит, что «предварительно обнуленная память свободна, и вам не нужно очищать себя», что привело бы к другой метрике для алгоритмов, которые редко используют память. Однако на практике распределение памяти и сборка мусора не являются свободными, поэтому этот показатель будет иметь ограниченное практическое значение.

Answer 5

Обозначение Big-O имеет дело с верхними границами, технически говоря, алгоритм - это O (g (n)) для всех без исключения g (n), которые асимптотически растут быстрее, чем f (n), поэтому, если алгоритм равен O (n) ) это должны быть O (n ^ 2) и O (n ^ 99).

Нотация Little-o имеет дело с верхними границами сегодня вечером, то есть наименее быстро растущим набором функций, которые растут быстрее, чем f (n). Следовательно, неверно говорить, что f (n) равно o (n ^ 2), если это o (n).

Редактировать (чтобы ответить на комментарий):

Если дан алгоритм A и надежно сказано, что A - это O (n ^ 2), то есть вероятность, что A - это O (n) (или что-то еще), но вам придется проанализировать A, чтобы выяснить это самостоятельно. И наоборот, если достоверно сказано, что A было o (n ^ 2), оно не может быть O (n).