Сложность пространства big-O описывает, как использование памяти масштабируется с количеством или размером заданных c входов.
Например, если у вас есть алгоритм для обработки матрицы с R строками и C столбцов, а объем памяти, необходимый для обработки, был постоянным, даже если R и C увеличились, тогда ваш алгоритм будет иметь сложность пространства O (1).
Когда используемая память выделяется динамически или нет является ортогональным, хотя время жизни распределения имеет значение. Рассмотрим:
, если вы посещаете каждую ячейку в матрице и выделяете фиксированный (т.е. не увеличивается с R и C) объем памяти, обработайте ячейку , затем освободите память до , переходя к следующей ячейке, тогда ваше пиковое использование памяти не будет зависеть от R и C, поэтому сложность пространства O (1), но
, если вы выделили фиксированный объем памяти при посещении каждой ячейки и освободили ее только после обработки последней ячейки, тогда использование памяти будет масштабироваться с количеством ячеек - O (R *C) сложность пространства
если вы посещаете каждую ячейку и выделяете объем памяти, который имеет тенденцию расти со значениями R и / или C, тогда ваш сложность пространства не будет O (1)