Введение
Компьютерная память, необходимая алгоритму.
Пространственная сложность алгоритма или структуры данных — это объем памяти, требуемый для решения экземпляра вычислительной задачи как функция от характеристик входных данных. Это объем памяти, необходимый алгоритму до полного завершения его работы. Он включает в себя память, используемую входными данными (входное пространство), и любую другую (вспомогательную) память, используемую во время выполнения (вспомогательное пространство). Подобно временной сложности, пространственная сложность часто выражается асимптотически в нотации «большое О», например, и т.д., где n — характеристика входных данных, влияющая на пространственную сложность.
The space complexity of an algorithm or a data structure is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely. This includes the memory space used by its inputs, called input space, and any other (auxiliary) memory it uses during execution, which is called auxiliary space. Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as
etc., where n is a characteristic of the input influencing space complexity.
Логпространство
L или LOGSPACE — это класс задач, которые могут быть решены детерминированной машиной Тьюринга, используя пространство памяти, зависящее от размера входных данных. Даже один счетчик, способный индексировать весь входной бит, требует памяти, поэтому алгоритмы LOGSPACE могут поддерживать только постоянное число счетчиков или других переменных сопоставимой битовой сложности. LOGSPACE и другие классы с подлинейной сложностью по памяти полезны при обработке больших объемов данных, которые не помещаются в оперативную память компьютера. Они связаны с потоковыми алгоритмами, но ограничивают лишь объем используемой памяти, в то время как потоковые алгоритмы накладывают дополнительные ограничения на способ подачи входных данных в алгоритм. Этот класс также находит применение в области псевдослучайности и дерандомизации, где исследователи рассматривают открытую проблему о том, верно ли, что L = RL. Соответствующий класс недетерминированной сложности по памяти — NL.