Кіріспе
Алгоритмге қажетті компьютерлік жад. Алгоритмнің немесе деректер құрылымының кеңістіктік күрделілігі – есептеу мәселесінің бір мысалын шешу үшін қажетті жад мөлшері, бұл жад мөлшері кіріс деректерінің сипаттамаларына байланысты өзгереді. Бұл алгоритм толық орындалғанға дейін қажетті жадты білдіреді. Оған алгоритмнің кіріс деректері үшін пайдаланатын жад (кіріс кеңістігі) және орындалу барысында қосымша қолданылатын жад (қосалқы кеңістік) кіреді. Уақыт күрделілігі сияқты, кеңістіктік күрделілік көбінесе үлкен О нотациясы арқылы, мысалы, O(n) және т.б. түрінде көрсетіледі, мұнда 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.
LOGSPACE (Жоғары кеңістік)
L немесе LOGSPACE – кіріс мөлшеріне пропорционал жад кеңістігін пайдаланатын детерминистік Тьюринг машинасымен шешілетін мәселелер жиынтығы. Тіпті кірістің барлық біттерін индекстей алатын бір ғана санауыш та жадты қажет етеді, сондықтан LOGSPACE алгоритмдері тек тұрақты мөлшерде санауыштарды немесе осыған ұқсас күрделіліктегі басқа айнымалыларды сақтай алады. LOGSPACE және басқа да сызықтық емес жад күрделілігі компьютердің жедел жадына (RAM) сыймайтын үлкен деректерді өңдеу үшін пайдалы. Олар ағынды алгоритмдермен байланысты, бірақ жадты пайдалану шегімен ғана айналысады, ал ағынды алгоритмдерде деректерді алгоритмге қалай беруге қатысты қосымша шектеулер бар. Бұл класс псевдорандомдық және рандомдылықты жою салаларында да қолданылады, онда зерттеушілер L = RL деген ашық мәселені қарастырады. Сәйкес келетін детерминистік емес жад күрделілігі класы NL болып табылады.