计算复杂度

在计算机科学 computer science中，一个算法 algorithm的计算复杂度或简单的复杂度就是运行这个算法所需要的资源量，特别是时间（CPU占用时间）和空间（内存占用空间）需求。

由于运行一个算法所需的资源量通常随输入规模的大小而变化，因此复杂度通常用函数 $f (n)$ 表示，其中 $n$ 是输入量的大小， $f (n)$ 是最坏情况复杂度 worst-case complexity(输入大小为 $n$ 时所需的资源量的最大值) ，或是平均情况复杂度 average-case complexity(资源总量相对于 $n$ 的所有占用的平均值)。时间复杂度 Time complexity通常表示为对一个输入值长度所需基本操作（通常是加法操作或者乘法操作）的数量。我们假设基本操作在一台计算机上只占用一个不变的时间量（比如1纳秒），而在另一台计算机上运行时，只根据一个常量因子进行改变（比如k*1纳秒）。空间复杂度 space complexity通常表示为算法对一个输入值长度所需的内存量。

对一个有明确定义的算法的复杂度进行的研究叫做算法分析 analysis of algorithm，而对问题的复杂度研究叫做计算复杂度理论 computation complexity theory分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有[math]\displaystyle{ n }[/math]个数字，那么排序问题的复杂度就是[math]\displaystyle{ nlogn }[/math]，而选择排序的复杂度是[math]\displaystyle{ n^2 }[/math]，归并排序的复杂度是[math]\displaystyle{ 6nlogn }[/math]。

这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的上限 upper bound。

资源

时间

最常被考虑的资源是时间。当没有明确说明时，“复杂度”通常意味着时间复杂度而非空间复杂度。

在复杂度理论 complexity theory中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过统计在计算过程中执行的基本操作数量来实现的。这些基本操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。

空间

另一个重要的资源是运行算法所需的计算机内存 computer memory大小。

其他

算术运算 arithmetic operations的数量是另一种常用的资源。在这种情况下，人们会谈到算术复杂度。如果已知一个计算过程中出现的数的二进制表示 binary representation长度的上限 upper bound，时间复杂度通常是该算术复杂度乘以一个常数因子。

对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 位复杂度 bit complexity，可能远远大于算术复杂度。例如，根据通常的算法 高斯消去法 Gaussian elimination 计算一个 $n \times n$ 整数矩阵行列式的算术复杂度是[math]\displaystyle{ O(n^3) }[/math]。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到 $O ~ (n 4)$ 。

在排序 sorting和搜索 searching中，通常考虑的资源是需要做几次比较大小。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。

复杂度：输入规模的函数

复杂度作为关于输入长度的函数

为了清晰起见，本节只考虑时间复杂度，不过所有内容(稍加修改)也都适用于其他资源的复杂度。

计算一个算法对于所有可能输入的所需要的步骤数是不可能的。由于复杂度通常随着输入的规模而增加，复杂度通常表示为输入值 $n$ 长度（以比特 bit为单位）的函数。因此，复杂度是一个关于 $n$ 的函数。然而，对于同样长度的不同输入，算法的复杂度可能会大不相同。因此，有多种不同的复杂度函数被广泛使用。

最坏情况复杂度 worst-case complexity是对所有输入 $n$ 长度中的最大复杂度，平均情况复杂度 average-case complexity是对所有输入 $n$ 长度中的平均复杂度。一般来说，如果使用“复杂度”一词且不进行进一步说明，即考虑最坏情况时间复杂度。

渐近复杂度

通常很难精确计算最坏情况和平均情况复杂度。此外，由于计算机或计算模型的任何变化都会改变复杂度，精确的复杂度值没多少实际意义。更多地，对于较小的 $n$ 值，资源的使用并不是关键。因此对于小 $n$ ，人们通常更在乎一个算法的简单性和易实现性，而非复杂度。

由于这些原因，人们通常把注意力集中在大 $n$ 的复杂度上，即输入规模趋于无穷大的渐近行为 asymptotic behavior上。因此，复杂度通常用大O符号 big O notation来表示。

例如，通常整数乘法 multiplication的复杂度是[math]\displaystyle{ O(n^2), }[/math]，这意味着存在一个常数[math]\displaystyle{ c_u }[/math]，使得两个最多 $n$ 位的整数乘法可以在小于[math]\displaystyle{ c_un^2 }[/math]的时间内完成。这个界限是尖锐的，因为最坏情况复杂度和平均情况复杂度是[math]\displaystyle{ \Omega(n^2), }[/math]，意味着存在一个常数[math]\displaystyle{ c_l }[/math]，使得这些复杂度比[math]\displaystyle{ c_ln^2 }[/math]大。

计算模型

复杂度的评估依赖于计算模型 model of computation的选择，包括定义在一个时间单位内完成的基本操作。当没有明确指定时，默认使用的计算模型是多带图灵机 multitape Turing machine。

确定性模型

一个确定性模型 deterministic model 的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是递归函数 recursive functions、 lambda 演算 lambda calculus和图灵机 Turing machines。随机存取机器 Random access machine (也称 RAM-machines)的模型也被广泛使用，更接近真实的计算机 computer。

当计算模型没有被指定时，通常假设它是一个多带图灵机 multitape Turing machine。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.

非确定性计算

在非确定性计算模型 non-deterministic model of computation中，例如不确定的图灵机 non-deterministic Turing machine，在计算的某些步骤中可能会进行一些选择。在复杂度理论中，非确定性时间复杂度即为，同时考虑所有可能的选择且做出最佳选择时所需的时间。换句话说，我们认为计算是多个（相同的）处理器上同时进行的，而不确定计算时间是第一个完成计算的处理器所花费的时间。这种并行性在一定程度上可以通过运行特定量子算法 quantum algorithm的叠加纠缠态 entangled state来实现量子计算 quantum computing。例如小整数上的肖尔因式分解 Shor's factorization。

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及P = NP? 问题。如果一个问题可以在确定性图灵机上以多项式时间 polynomial time求解，则该问题属于 P 类问题。如果一个问题可以在非确定性机器上以多项式时间 polynomial time求解，则该问题属于 NP 类问题。我们知道所有P类问题都属于NP类问题，但是否所有NP类问题也属于P类问题？亦即，是否P类问题和NP类问题是等价的？这就是所谓的 P=NP? 问题

如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为 NP完全问题 NP-complete。许多组合 combinatorial问题，例如背包问题 Knapsack problem、旅行推销员问题 travelling salesman problem和布尔可满足性问题 Boolean satisfiability problem都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 [math]\displaystyle{ P \neq NP }[/math]。

并行和分布式计算

并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过网络完成，因此速度要慢得多。

在 $N$ 个处理器上进行计算所需的时间至少是单个处理器所需时间的 $N$ 的商。但实际上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。

因此，主要的复杂度问题是如何设计算法，使得计算时间与处理器数量的乘积尽可能接近在单个处理器上进行同一计算所需的时间。

量子计算

量子计算机 quantum computer是一种基于量子力学 quantum mechanics的计算机。丘奇-图灵理论 Church–Turing thesis适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，有些问题理论上可以用量子计算机以极低的时间复杂度 time complexity解决，而用传统图灵机则无法解决。由于没有人知道如何建造一台高效的量子计算机，目前这纯粹只是理论上可行的。

量子复杂度理论 Quantum complexity theory研究用量子计算机解决的问题的复杂度类。它主要用于后量子密码学 post-quantum cryptography，包括设计能抵御量子计算机攻击的安全协议 cryptographic protocol。

问题复杂度(下限)

问题的复杂度是解决问题算法(包括未知算法)复杂度的下确界 infimum，即解决这个问题所需的最少时间。因此，问题的复杂度比任何解决该问题的算法的复杂度都要小。

用大O符号 big O notation表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。

另一方面，问题复杂度的非平凡（nontrivial）下界一般难以获得，并且获得这种下界的方法很少。

为了解决大多数问题，往往需要与数据大小成比例的时间来读取所有输入数据。因此，这些问题的复杂度至少是线性的 linear，使用大欧米茄符号 big omega notation，记为复杂度[math]\displaystyle{ \Omega(n). }[/math]

一些问题的解可能是非常大的，特别是计算机代数 computer algebra和计算代数几何 computational algebraic geometry。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的， $n$ 个 $d$ 次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates 可能有多达 [math]\displaystyle{ d^n }[/math]个复解(这是贝佐定理 Bézout's theorem)。由于这些解必须被写入，所以这个问题的复杂度是[math]\displaystyle{ \Omega(d^n) }[/math]。对于这个问题，已知一个复杂度为[math]\displaystyle{ d^{O(n)} }[/math]的算法，因此可以认为是渐近拟最优的。

获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为 $n$ 的问题 $A$ 可以编码成大小为 $f (n)$ 的问题 $B$ ，则问题 $A$ 的复杂度为[math]\displaystyle{ \Omega(g(n)) }[/math]。不失一般性地，我们可以假设函数 $f$ 随着 $n$ 的增加而增加，并且有一个反函数 inverse function，那么问题 $B$ 的复杂度就是[math]\displaystyle{ \Omega(g(h(n))) }[/math]。这个方法可以用来证明，若P ≠ NP(一个未解决的猜想) ，对于每个正整数 $k$ ，每个NP完全问题 NP-complete problem的复杂度都是 [math]\displaystyle{ \Omega(n^k) }[/math]。

在算法设计中的应用

评估算法的复杂度是算法设计 algorithm design的一个重要组成部分，因为这给出了一个算法关于预期性能的有用信息。

有一个常见的误解，由于摩尔定律 Moore's law假定了现代计算机功率的指数增长 exponential growth，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据(大数据 big data)成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的参考书目 bibliography，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要[math]\displaystyle{ O(n^2) }[/math]次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，快速排序 quicksort和合并排序 merge sort只需要[math]\displaystyle{ n\log_2 n }[/math]次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。

因此，对复杂度的评估允许在编程实现之前就消除许多低效率的算法。这也可用于在不用测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最复杂的步骤，对复杂度的研究还可以将重点放在这些步骤上，从而提高实现的效率。

引用

Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge
Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons
Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press
van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press
Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley
Sipser, Michael (2006), Introduction to the Theory of Computation (2nd ed.), USA: Thomson Course Technology

编者推荐

集智文章推荐

找到你混乱生活中的秩序——Kolmogorov复杂度

如何判断一段话信息量是大是小？在香农那里，可以用“克服了多少不确定性”来描述。而在柯尔莫哥洛夫那里，要看“用多长的代码能生成这句话”。

本中文词条由小竹凉翻译，Ricky审校，糖糖编辑，如有问题，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。