Так же как со временной сложностью - количеством операций. Только считайте количество используемых байт.
Грубо говоря, смотрите на все созданые в худшем случае переменные (не забыть, что локальные переменные и аргументы функций на стеке и считаются отдельно для каждого вызова функции по всей глубене вызовов).
Получаете какую-то формулу типа 10*n+16*m+n*m/2 + 100500*log n. Дальше применяете ассимптотический анализ.
Например, алгоритм DFS. есть граф с n вершинами и m ребрами. Пусть задан в виде списков инцидентности.
Тогда у вас есть n списков, которые все вместе содержат m элементов. Т.е. ваши входные данные занимают n*8+m(4+8) байт. n указателей на начало списка и m элементов - каждый содержит значение и указатель. Но не надо так считать досканально каждый байт, можно просто прикинуть n+m.
Сам алгоритм еще требует массива для пометок пройденных вершин: +n к потреблению памяти.
Функция требует сколько-то локальных переменных и параметров. Их несколько и от n или m это не зависит. В рекурсии функция может выть вызвана n раз, если вы все вершины пройдете вглубь. Итого на стеке эти функции съедят n*C, где С - какая-то константа.
Суммарная пространственная сложность n+m+n*C. Или O(n+m).
Локальные переменные, если это не массивы, обычно можно вообще не считать, потому что это или множители перед количеством вызова функций или просто константная надбавка, которая ассимптотикой игнорируется.
Средний
Простой
