存储资源怎样计量
空间复杂度描述算法运行所需存储随输入长度增长的规律。对长度为n的输入，最坏情况空间界取所有这类输入中的最大需求。程序分析通常关心运行期间同时保留的存储峰值；在标准图灵机模型中，常以执行中访问过的工作带格子数计量，并在分析中复用已有工作区域。
这不是把每次读写的字节数全部相加。同一块缓冲区重复使用许多次，会增加工作量，却不按使用次数扩大存储需求。也不能只测最终输出或日志文件的大小，因为算法还可能保留中间数组、索引、缓存以及未返回的调用栈。
穷举也能节省空间
SAT的直接算法可依次生成各组布尔赋值，计算公式值，再覆盖当前赋值并尝试下一组。如果有n个变量，候选可达2^n组，但不必把所有赋值同时存起来。只需当前候选及求值工作区，就能在多项式空间内完成，尽管时间可能很长。
这一例子显示时间和空间不可混为一谈。每个计算步骤消耗的时间无法回收，但之前不再需要的内存可以再次利用。反过来，缓存所有子问题结果可能减少重复计算，却增加存储；是否值得这样做，取决于要优化的资源和输入结构。
递归栈也是算法的一部分
递归程序不能只计算单次函数调用的局部变量。尚未返回的每一层都可能保存参数、循环位置和中间结果，必须把整条活动调用链计入空间。若递归深度为d、每层保留b量级存储，栈空间通常达到O(db)，还须加上共享工作区。
深度优先搜索可以在处理完一个分支后复用其空间，不必保存整棵搜索树。量化布尔公式求值便利用这一点：对每个变量依次尝试真假，返回后再处理下一支。树的节点总数可能指数多，而任一时刻保留的根到叶路径只有多项式长度。
输入存储与小空间类
若把输入完整复制到可写工作区，单这一步就需要线性空间。研究对数空间等亚线性界时，通常设置只读输入带，允许反复扫描，但不把输入本身计入工作空间。于是算法可只保存少量位置指针或计数器，每个需要O(log n)比特，而不需要复制全部数据。
SPACE(s(n))是能在确定性O(s(n))空间内判定的语言类；多项式空间类PSPACE与对数空间类L是常见例子。它们的结论依赖明确的计费模型。若讨论实际软件，还应说明输入、输出缓冲和库分配是否计入，区分辅助空间与总内存，避免把不同口径的测量直接比较。