计算复杂性是计算机科学和数学的一个分支，研究解决计算问题所需的资源。它主要关注运行时间和内存，并将这些资源的用量表示为输入规模的函数。算法分析考察某个具体的计算过程，而复杂性理论研究问题本身：解决问题需要多少资源，以及任何可能的解法都至少需要多少资源。因此，它区分了实现方式低效与问题固有的计算困难。(introcs.cs.princeton.edu)
计算模型与输入规模
关于复杂性的论断依赖于指定的计算模型。图灵机提供了一种标准的数学模型，计算通过在带有符号的纸带上执行离散步骤来进行。其他模型包括随机存取机和布尔电路。许多常见的顺序计算模型可以相互模拟，且只引入多项式级别的额外开销，因此，相比精确的运行时间界，多项式时间的分类更为稳健。(claymath.org)
输入规模通常指编码的长度，而非输入数值的大小，且常以比特为单位计量。一个用二进制表示的整数 (W) 大约需要 (\log_2 W) 个比特。因此，运行时间关于 (W) 为多项式的计算过程，其运行时间未必关于编码长度也是多项式。在研究背包问题以及其他采用伪多项式时间算法的数值问题时，这一区别十分重要。(cs.yale.edu)
区分计算困难与无法计算同样重要。复杂性理论主要关注资源受限的计算，而可计算性理论则研究哪些问题能够通过算法求解。例如，停机问题不存在能够正确判定所有实例的算法；这与一个可以判定、但需要消耗大量资源的问题不同。(cs.cmu.edu)
时间、空间与渐近界
时间复杂度衡量计算步骤的数量，空间复杂度则衡量内存消耗。对于某个算法和输入长度 (n)，最坏情况时间是该算法在所有长度为 (n) 的输入上的最大运行时间。平均情况分析则需要指定输入的概率分布。对于随机化算法，期望运行时间可能是对算法内部的随机选择取期望，而不是对输入分布取期望。(aofa.cs.princeton.edu)
大O记号用于表示渐近上界，忽略常数因子和低阶项。与之相关的符号 (\Omega) 和 (\Theta) 分别表示渐近下界和渐近紧确界。这些符号本身并不代表最坏、最好或平均情况：它们都可以用于描述所定义的任何资源用量函数。常见的增长率包括对数、线性、(n\log n)、二次和指数增长。(algs4.cs.princeton.edu)
例如，二分查找在有序数组上所需的比较次数呈对数增长，而基于比较的排序在最坏情况下有 (n\log n) 量级的下界。这些结果取决于允许使用哪些操作：比较模型中的下界，并不自动适用于利用输入其他性质的算法。(algs4.cs.princeton.edu)
复杂性类
复杂性类根据资源限制和计算模型对问题进行分类。复杂性类通常用判定问题来定义，这类问题的输出为“是”或“否”。搜索问题和数学优化问题有与之相关但不同的表述方式。标准的复杂性类包括：
- **P：**能够由确定性算法在多项式时间内求解的判定问题。
- **NP：**对于答案为“是”的实例，存在长度为多项式的证书，且该证书可在确定性多项式时间内验证的判定问题；等价地，能够在非确定性多项式时间内判定的问题。
- **PSPACE：**能够使用多项式空间求解的判定问题。
- **EXPTIME：**能够在确定性时间 (2^{n^{O(1)}}) 内求解的判定问题。(claymath.org)
这些类之间已知的关系为 [ \mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}\subseteq\mathrm{EXPTIME}. ] 时间层次定理表明，P 是 EXPTIME 的真子集，但它并未确定上述包含链中哪一对相邻类之间存在严格包含关系。更一般地，层次定理表明，在资源界满足一定技术条件的前提下，适当增加可用资源，就能求解更多问题。(cs.cmu.edu)
多项式时间是一项理论基准，并不保证实际运行速度足够快。高次多项式或极大的常数可能使计算难以实施，而指数时间算法在规模较小或受到限制的实例上，可能仍能取得可接受的表现。(cs.princeton.edu)
归约、完全性与 P 与 NP 问题
多项式时间归约在多项式时间内将一个问题的实例转换为另一个问题的实例，同时保持答案不变。如果问题 (A) 可以归约到问题 (B)，那么 (B) 的高效算法就能导出 (A) 的高效算法。因此，归约既可以将一个问题的算法用于另一个问题，也可以确立问题之间的相对难度。(cs.yale.edu)
在多项式时间多对一归约下，如果 NP 中的每个问题都能归约到某个问题，那么该问题就是NP 难的。如果一个问题既是 NP 难的，又属于 NP，那么它就是NP 完全的。库克–莱文定理证明了布尔可满足性问题是 NP 完全的，为证明其他完全性结果奠定了基础。NP 难问题本身不一定属于 NP。(claymath.org)
P 与 NP 问题问的是 P 是否等于 NP，至今仍未解决。任何一个 NP 完全问题若存在多项式时间算法，就意味着 P = NP。反过来，仅凭 NP 完全性并不能证明指数时间是必需的：即使 P ≠ NP，也只能排除多项式时间算法，而不能自动排除所有次指数时间算法。(claymath.org)
随机性与更广泛的应用
随机化计算引入了 BPP 等复杂性类：BPP 中的问题可以在多项式时间内判定，并且对每个输入，出错概率都不超过三分之一。通过独立重复运行，可以降低这一错误概率。基于量子计算机的量子计算也有类似的有界错误多项式时间类 BQP，其定义采用量子计算而非经典计算。(cs.yale.edu)
复杂性研究还涉及电路的规模与深度、通信、并行计算以及对解进行计数的难度。在密码学中，安全性需要适当的困难性假设，这些假设往往涉及典型实例，而不只是最坏情况实例。因此，单凭一个 NP 难性结果，并不能确立密码学安全性。(cs.princeton.edu)