用于描述单个算法的复杂性，即为：
- 算法需要的计算时间
- 运行算法所需的内存空间
计算复杂度理论研究的是算法的复杂性。一个可计算问题，在利用算法解决时，究竟需要多少资源？如果所需资源过多，一个问题就会在工程上不可解，那么这样一来，原本可计算的问题也就变得不可计算了。
算法分析：大 O 表示
由高德纳提出的“大O表示法”是一种算法分析方法，目的是忽略计算模型中的常数因子，而关注对算法影响最大的指数部分。
其本质是“抓大放小”。
例如，n 表示输入的长度，T(n) 表示算法运行的时间长度。如果算法可在常熟时间内运行完毕，算法的时间复杂度即为 O(n)
计算问题的集合
不同的计算问题有不同的复杂性，根据问题的等价关系，可以将问题按照复杂度打包成集合。
- P-NP问题
- L 问题：n 为输入长度，在确定性图灵机上所需空间不超过 O(logn) 算法问题的集合。一般认为这样的算法是比较快的
其中两个重要概念：
- 确定性图灵机和不确定性图灵机：确定性图灵机每次只能做一次计算，不确定性图灵机每次可以对不同的分支同时计算，可以对每个步骤中的分支同时计算。用现代计算机来类比，确定性图灵机类似于单核计算机，而不确定性图灵机类似于多核计算机，能够并行计算。参见：不确定性图灵机
- 多项式计算时间：算法执行的步骤总数是一个多项式，例如 而不存在例如 这样的因子。
一般认为『有效算法』即为多项式步骤的算法。