本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢! 目录 在计算机科学 computer science中,一个算法 algorithm的计算复杂度或简单的复杂度就是运行这个算法所需要的资源量,特别是时间(CPU占用时间)和空间(内存占用空间)需求。
这两个领域是高度相关的,因为算法的复杂度一直是该算法所求解问题复杂度的上限 upper bound。 资源 时间最常被考虑的资源是时间。当没有明确说明时,“复杂度”通常意味着时间复杂度而非空间复杂度。
空间另一个重要的资源是运行算法所需的计算机内存 computer memory大小。 其他算术运算 arithmetic operations的数量是另一种常用的资源。在这种情况下,人们会谈到算术复杂度。如果已知一个计算过程中出现的数的二进制表示 binary representation长度的上限 upper bound,时间复杂度通常是该算术复杂度乘以一个常数因子。
在排序 sorting和搜索 searching中,通常考虑的资源是需要做几次比较大小。如果数据组织得当,这通常是一个很好的时间复杂度测量方法。 复杂度:输入规模的函数 为了清晰起见,本节只考虑时间复杂度,不过所有内容(稍加修改)也都适用于其他资源的复杂度。最坏情况复杂度 worst-case complexity是对所有输入n长度中的最大复杂度,平均情况复杂度 average-case complexity是对所有输入n长度中的平均复杂度。一般来说,如果使用“复杂度”一词且不进行进一步说明 ,即考虑最坏情况时间复杂度。 渐近复杂度 通常很难精确计算最坏情况和平均情况复杂度。此外,由于计算机或计算模型的任何变化都会改变复杂度,精确的复杂度值没多少实际意义。更多地,对于较小的n值,资源的使用并不是关键。因此对于小 n,人们通常更在乎一个算法的简单性和易实现性,而非复杂度。由于这些原因,人们通常把注意力集中在大n的复杂度上,即输入规模趋于无穷大的渐近行为 asymptotic behavior上。因此,复杂度通常用大O符号 big O notation来表示。 例如,通常整数乘法 multiplication的复杂度是O(n^2),这意味着存在一个常数Cu,使得两个最多n位的整数乘法可以在小于Cun^2的时间内完成。这个界限是尖锐的,因为最坏情况复杂度和平均情况复杂度是Ω(n^2)。意味着存在一个常数Cl,使得这些复杂度比Cln^2大。 计算模型 复杂度的评估依赖于计算模型 model of computation的选择,包括定义在一个时间单位内完成的基本操作。当没有明确指定时,默认使用的计算模型是多带图灵机 multitape Turing machine。确定性模型当计算模型没有被指定时,通常假设它是一个多带图灵机 multitape Turing machine。对于大多数算法,在多带图灵机上的时间复杂度与在RAM-machines上的相同,尽管可能需要注意如何将数据存储在内存中,以确保这种等价性。 非确定性计算即使这样的计算模型还不现实,它仍然具有重要的理论意义,主要涉及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 问题的最坏情况本质上是难以解决的,即P≠NP。 并行和分布式计算在N个处理器上进行计算所需的时间至少是单个处理器所需时间的N的商。但实际上,这个理论上的最优界限永远不可能达到,由于有些子任务不能并行化,部分处理器不得不先等待另一个处理器的结果。 因此,主要的复杂度问题是如何设计算法,使得计算时间与处理器数量的乘积尽可能接近在单个处理器上进行同一计算所需的时间。 量子计算量子复杂度理论 Quantum complexity theory研究用量子计算机解决的问题的复杂度类。它主要用于后量子密码学 post-quantum cryptography,包括设计能抵御量子计算机攻击的安全协议 cryptographic protocol。 问题复杂度(下限) 问题的复杂度是解决问题算法(包括未知算法)复杂度的下确界 infimum,即解决这个问题所需的最少时间。因此,问题的复杂度比任何解决该问题的算法的复杂度都要小。用大O符号 big O notation表示的每一个复杂度都是算法的复杂度,也是相应问题的复杂度。 另一方面,问题复杂度的非平凡(nontrivial)下界一般难以获得,并且获得这种下界的方法很少。 为了解决大多数问题,往往需要与数据大小成比例的时间来读取所有输入数据。因此,这些问题的复杂度至少是线性的 linear,使用大欧米茄符号 big omega notation,记为复杂度Ω(n)。 一些问题的解可能是非常大的,特别是计算机代数 computer algebra和计算代数几何 computational algebraic geometry。在这种情况下,复杂度以输出的最大长度为下界,因此输出必须被写入。例如,如果解的个数是有限的,n个d次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates 可能有多达d^n个复解(这是贝佐定理 Bézout's theorem)。由于这些解必须被写入,所以这个问题的复杂度是Ω(d^n)。对于这个问题,已知一个复杂度为d^(O(n))的算法,因此可以认为是渐近拟最优的。 在算法设计中的应用 评估算法的复杂度是算法设计 algorithm design的一个重要组成部分,因为这给出了一个算法关于预期性能的有用信息。有一个常见的误解,由于摩尔定律 Moore's law假定了现代计算机功率的指数增长 exponential growth,对算法复杂度的评估将变得不那么重要。这是错误的,因为这种功率增加同样也会容使得处理较大的输入数据(大数据)成为可能。例如,当一个人想要按字母顺序对数百个条目的列表进行排序时,比如一本书的参考书目,任何算法都应该在不到一秒的时间内就能正常工作。另一方面,对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ,需要O(n^2)次比较的基本算法,须进行1万亿次比较运算,即以每秒1000万次的速度进行比较需要大约3个小时。另一方面,快速排序和合并排序 只需要nlog2n次比较(前者为平均情况复杂度,后者为最坏情况复杂度)。这大约是3000万次比较,以每秒1000万次比较计算,只需要3秒钟。 |
|
来自: taotao_2016 > 《计算机》