| 第39行： |
第39行： |
| | | | |
| | | | |
| − | | + | 对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 '''位复杂度 bit complexity'''，可能远远大于算术复杂度。例如，根据通常的算法 '''高斯消去法 Gaussian elimination''' 计算一个{{math|''n''×''n''}} 整数矩阵行列式 的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到{{math|''O''<sup>~</sup>(''n''<sup>4</sup>)}}。 |
| − | For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called [[bit complexity]] in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the [[determinant]] of a {{math|''n''×''n''}} [[integer matrix]] is <math>O(n^3)</math> for the usual algorithms ([[Gaussian elimination]]). The bit complexity of the same algorithms is [[exponential function|exponential]] in {{mvar|n}}, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with [[modular arithmetic|multi-modular arithmetic]], the bit complexity may be reduced to [[soft O notation|{{math|''O''<sup>~</sup>(''n''<sup>4</sup>)}}]].
| |
| − | | |
| − | For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called bit complexity in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the determinant of a integer matrix is <math>O(n^3)</math> for the usual algorithms (Gaussian elimination). The bit complexity of the same algorithms is exponential in , because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with multi-modular arithmetic, the bit complexity may be reduced to soft O notation|.
| |
| − | | |
| − | 对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 '''位复杂度 bit complexity'''，可能远远大于算术复杂度。例如，根据通常的算法 '''高斯消去法 Gaussian elimination''' 计算一个{{math|''n''×''n''}} 整数矩阵行列式 的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到soft O notation|{{math|''O''<sup>~</sup>(''n''<sup>4</sup>)}}。 | |
| | | | |
| | | | |
| 第54行： |
第49行： |
| | :''为了清晰起见，本节只考虑时间复杂度，不过所有内容(稍加修改)也都适用于其他资源的复杂度。'' | | :''为了清晰起见，本节只考虑时间复杂度，不过所有内容(稍加修改)也都适用于其他资源的复杂度。'' |
| | | | |
| − | It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size {{math|''n''}} (in [[bit]]s) of the input, and therefore, the complexity is a function of {{math|''n''}}. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.
| |
| − |
| |
| − | It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size (in bits) of the input, and therefore, the complexity is a function of . However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.
| |
| | | | |
| | 计算一个算法对于所有可能输入的所需要的步骤数是不可能的。由于复杂度通常随着输入的规模而增加，复杂度通常表示为输入值 {{math|''n''}} 长度（以'''比特 bit'''为单位）的函数。因此，复杂度是一个关于 {{math|''n''}} 的函数。然而，对于同样长度的不同输入，算法的复杂度可能会大不相同。因此，有多种不同的复杂度函数被广泛使用。 | | 计算一个算法对于所有可能输入的所需要的步骤数是不可能的。由于复杂度通常随着输入的规模而增加，复杂度通常表示为输入值 {{math|''n''}} 长度（以'''比特 bit'''为单位）的函数。因此，复杂度是一个关于 {{math|''n''}} 的函数。然而，对于同样长度的不同输入，算法的复杂度可能会大不相同。因此，有多种不同的复杂度函数被广泛使用。 |
| | | | |
| − | The [[worst-case complexity]] is the maximum of the complexity over all inputs of size {{mvar|n}}, and the [[average-case complexity]] is the average of the complexity over all inputs of size {{mvar|n}} (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.
| |
| − |
| |
| − | The worst-case complexity is the maximum of the complexity over all inputs of size , and the average-case complexity is the average of the complexity over all inputs of size (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.
| |
| | | | |
| | '''最坏情况复杂度 worst-case complexity'''是对所有输入{{mvar|n}}长度中的最大复杂度，'''平均情况复杂度 average-case complexity'''是对所有输入{{mvar|n}}长度中的平均复杂度。一般来说，如果使用“复杂度”一词且不进行进一步说明 ，即考虑最坏情况时间复杂度。 | | '''最坏情况复杂度 worst-case complexity'''是对所有输入{{mvar|n}}长度中的最大复杂度，'''平均情况复杂度 average-case complexity'''是对所有输入{{mvar|n}}长度中的平均复杂度。一般来说，如果使用“复杂度”一词且不进行进一步说明 ，即考虑最坏情况时间复杂度。 |
| | | | |
| | ==渐近复杂度== | | ==渐近复杂度== |
| − | It is generally difficult to compute precisely the worst-case and the average-case complexity. In addition, these exact values provide little practical application, as any change of computer or of model of computation would change the complexity somewhat. Moreover, the resource use is not critical for small values of {{mvar|n}}, and this makes that, for small {{mvar|n}}, the ease of implementation is generally more interesting than a good complexity.
| |
| − |
| |
| − | It is generally difficult to compute precisely the worst-case and the average-case complexity. In addition, these exact values provide little practical application, as any change of computer or of model of computation would change the complexity somewhat. Moreover, the resource use is not critical for small values of , and this makes that, for small , the ease of implementation is generally more interesting than a good complexity.
| |
| | | | |
| | 通常很难精确计算最坏情况和平均情况复杂度。此外，由于计算机或计算模型的任何变化都会改变复杂度，精确的复杂度值没多少实际意义。更多地，对于较小的{{mvar|n}}值，资源的使用并不是关键。因此对于小 {{mvar|n}}，人们通常更在乎一个算法的简单性和易实现性，而非复杂度。 | | 通常很难精确计算最坏情况和平均情况复杂度。此外，由于计算机或计算模型的任何变化都会改变复杂度，精确的复杂度值没多少实际意义。更多地，对于较小的{{mvar|n}}值，资源的使用并不是关键。因此对于小 {{mvar|n}}，人们通常更在乎一个算法的简单性和易实现性，而非复杂度。 |
| − |
| |
| − | For these reasons, one generally focuses on the behavior of the complexity for large {{mvar|n}}, that is on its [[asymptotic analysis|asymptotic behavior]] when {{mvar|n}} tends to the infinity. Therefore, the complexity is generally expressed by using [[big O notation]].
| |
| − |
| |
| − | For these reasons, one generally focuses on the behavior of the complexity for large , that is on its asymptotic behavior when tends to the infinity. Therefore, the complexity is generally expressed by using big O notation.
| |
| | | | |
| | 由于这些原因，人们通常把注意力集中在大{{mvar|n}}的复杂度上，即输入规模趋于无穷大的'''渐近行为 asymptotic behavior'''上。因此，复杂度通常用'''大O符号 big O notation'''来表示。 | | 由于这些原因，人们通常把注意力集中在大{{mvar|n}}的复杂度上，即输入规模趋于无穷大的'''渐近行为 asymptotic behavior'''上。因此，复杂度通常用'''大O符号 big O notation'''来表示。 |
| | | | |
| | | | |
| − |
| |
| − | For example, the usual algorithm for integer [[multiplication]] has a complexity of <math>O(n^2),</math> this means that there is a constant <math>c_u</math> such that the multiplication of two integers of at most {{mvar|n}} digits may be done in a time less than <math>c_un^2.</math> This bound is ''sharp'' in the sense that the worst-case complexity and the average-case complexity are <math>\Omega(n^2),</math> which means that there is a constant <math>c_l</math> such that these complexities are larger than <math>c_ln^2.</math> The [[radix]] does not appear in these complexity, as changing of radix changes only the constants <math>c_u</math> and <math>c_l.</math>
| |
| − |
| |
| − | For example, the usual algorithm for integer multiplication has a complexity of <math>O(n^2),</math> this means that there is a constant <math>c_u</math> such that the multiplication of two integers of at most digits may be done in a time less than <math>c_un^2.</math> This bound is sharp in the sense that the worst-case complexity and the average-case complexity are <math>\Omega(n^2),</math> which means that there is a constant <math>c_l</math> such that these complexities are larger than <math>c_ln^2.</math> The radix does not appear in these complexity, as changing of radix changes only the constants <math>c_u</math> and <math>c_l.</math>
| |
| | | | |
| | 例如，通常整数'''乘法 multiplication'''的复杂度是<math>O(n^2),</math>，这意味着存在一个常数<math>c_u</math>，使得两个最多{{mvar|n}}位的整数乘法可以在小于<math>c_un^2</math>的时间内完成。这个界限是尖锐的，因为最坏情况复杂度和平均情况复杂度是<math>\Omega(n^2),</math>，意味着存在一个常数<math>c_l</math>，使得这些复杂度比<math>c_ln^2</math>大。 | | 例如，通常整数'''乘法 multiplication'''的复杂度是<math>O(n^2),</math>，这意味着存在一个常数<math>c_u</math>，使得两个最多{{mvar|n}}位的整数乘法可以在小于<math>c_un^2</math>的时间内完成。这个界限是尖锐的，因为最坏情况复杂度和平均情况复杂度是<math>\Omega(n^2),</math>，意味着存在一个常数<math>c_l</math>，使得这些复杂度比<math>c_ln^2</math>大。 |
| 第101行： |
第79行： |
| | | | |
| | 在'''非确定性计算模型 non-deterministic model of computation'''中，例如'''不确定的图灵机 non-deterministic Turing machine'''，在计算的某些步骤中可能会进行一些选择。在复杂度理论中，非确定性时间复杂度即为，同时考虑所有可能的选择且做出最佳选择时所需的时间。换句话说，我们认为计算是多个（相同的）处理器上同时进行的，而不确定计算时间是第一个完成计算的处理器所花费的时间。这种并行性在一定程度上可以通过运行特定'''[[量子算法]] quantum algorithm'''的叠加'''纠缠态 entangled state'''来实现'''[[量子计算]] quantum computing'''。例如小整数上的'''肖尔因式分解 Shor's factorization'''。 | | 在'''非确定性计算模型 non-deterministic model of computation'''中，例如'''不确定的图灵机 non-deterministic Turing machine'''，在计算的某些步骤中可能会进行一些选择。在复杂度理论中，非确定性时间复杂度即为，同时考虑所有可能的选择且做出最佳选择时所需的时间。换句话说，我们认为计算是多个（相同的）处理器上同时进行的，而不确定计算时间是第一个完成计算的处理器所花费的时间。这种并行性在一定程度上可以通过运行特定'''[[量子算法]] quantum algorithm'''的叠加'''纠缠态 entangled state'''来实现'''[[量子计算]] quantum computing'''。例如小整数上的'''肖尔因式分解 Shor's factorization'''。 |
| − |
| |
| − | Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the [[P = NP]] problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class [[NP (complexity)|NP]], if it may be solved in [[polynomial time]] on a non-deterministic machine. A problem is [[NP-complete]] if, roughly speaking, it is in NP and is not easier than any other NP problem. Many [[combinatorics|combinatorial]] problems, such as the [[Knapsack problem]], the [[travelling salesman problem]], and the [[Boolean satisfiability problem]] are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. {{As of|2017}} it is generally conjectured that {{nowrap|P ≠ NP,}} with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.
| |
| − |
| |
| − | Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the P = NP problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class NP, if it may be solved in polynomial time on a non-deterministic machine. A problem is NP-complete if, roughly speaking, it is in NP and is not easier than any other NP problem. Many combinatorial problems, such as the Knapsack problem, the travelling salesman problem, and the Boolean satisfiability problem are NP-complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. it is generally conjectured that with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i.e., take longer than any reasonable time span (decades!) for interesting lengths of input.
| |
| | | | |
| | 即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''P = NP?''' 问题。如果一个问题可以在确定性图灵机上以'''多项式时间 polynomial time'''求解，则该问题属于 '''P 类问题'''。如果一个问题可以在非确定性机器上以'''多项式时间 polynomial time'''求解，则该问题属于 '''NP 类问题'''。我们知道所有P类问题都属于NP类问题，但是否所有NP类问题也属于P类问题？亦即，是否P类问题和NP类问题是等价的？这就是所谓的 P=NP? 问题 | | 即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''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>P \neq NP</math>。 | + | 如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为''' NP完全问题 NP-complete'''。许多'''组合 combinatorial'''问题，例如'''背包问题 Knapsack problem'''、'''旅行推销员问题 travelling salesman problem'''和'''布尔可满足性问题 Boolean satisfiability problem'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 <math>P \neq NP</math>。 |
| | | | |
| | ===并行和分布式计算=== | | ===并行和分布式计算=== |
| | | | |
| | 并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''网络'''完成，因此速度要慢得多。 | | 并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''网络'''完成，因此速度要慢得多。 |
| − |
| |
| − | The time needed for a computation on {{mvar|N}} processors is at least the quotient by {{mvar|N}} of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.
| |
| − |
| |
| − | The time needed for a computation on processors is at least the quotient by of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.
| |
| | | | |
| | 在{{mvar|N}}个处理器上进行计算所需的时间至少是单个处理器所需时间的{{mvar|N}}的商。但实际上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。 | | 在{{mvar|N}}个处理器上进行计算所需的时间至少是单个处理器所需时间的{{mvar|N}}的商。但实际上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。 |
| 第137行： |
第107行： |
| | 另一方面，问题复杂度的非平凡（nontrivial）下界一般难以获得，并且获得这种下界的方法很少。 | | 另一方面，问题复杂度的非平凡（nontrivial）下界一般难以获得，并且获得这种下界的方法很少。 |
| | | | |
| − | For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least [[linear time|linear]], that is, using [[big omega notation]], a complexity <math>\Omega(n).</math>
| |
| − |
| |
| − | For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least linear, that is, using big omega notation, a complexity <math>\Omega(n).</math>
| |
| | | | |
| | 为了解决大多数问题，往往需要与数据大小成比例的时间来读取所有输入数据。因此，这些问题的复杂度至少是'''线性的 linear'''，使用'''大欧米茄符号 big omega notation'''，记为复杂度<math>\Omega(n).</math> | | 为了解决大多数问题，往往需要与数据大小成比例的时间来读取所有输入数据。因此，这些问题的复杂度至少是'''线性的 linear'''，使用'''大欧米茄符号 big omega notation'''，记为复杂度<math>\Omega(n).</math> |
| | | | |
| | | | |
| − | The solution of some problems, typically in [[computer algebra]] and [[computational algebraic geometry]], may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a [[system of polynomial equations|system of {{mvar|n}} polynomial equations of degree {{mvar|d}} in {{mvar|n}} indeterminates]] may have up to <math>d^n</math> [[complex number|complex]] solutions, if the number of solutions is finite (this is [[Bézout's theorem]]). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.
| + | 一些问题的解可能是非常大的，特别是'''计算机代数 computer algebra'''和'''计算代数几何 computational algebraic geometry'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，'''{{mvar|n}}个{{mvar|d}}次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates '''可能有多达 <math>d^n</math>个复解(这是'''贝佐定理 Bézout's theorem''')。由于这些解必须被写入，所以这个问题的复杂度是<math>\Omega(d^n)</math>。对于这个问题，已知一个复杂度为<math>d^{O(n)}</math>的算法，因此可以认为是渐近拟最优的。 |
| − | | |
| − | The solution of some problems, typically in computer algebra and computational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a system of polynomial equations of degree in indeterminates may have up to <math>d^n</math> complex solutions, if the number of solutions is finite (this is Bézout's theorem). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.
| |
| | | | |
| − | 一些问题的解可能是非常大的，特别是'''计算机代数 computer algebra'''和'''计算代数几何 computational algebraic geometry'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，'''{{mvar|n}}个{{mvar|d}}次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates '''可能有多达 <math>d^n</math>个复解(这是'''贝佐定理 Bézout's theorem''')。由于这些解必须被写入，所以这个问题的复杂度是<math>\Omega(d^n).</math>。对于这个问题，已知一个复杂度为<math>d^{O(n)}</math>的算法，因此可以认为是渐近拟最优的。
| |
| | | | |
| − | | + | 获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n))</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''反函数 inverse function'''，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n)))</math>。这个方法可以用来证明，若'''P ≠ NP'''(一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''NP完全问题 NP-complete problem'''的复杂度都是 <math>\Omega(n^k)</math>。 |
| − | A standard method for getting lower bounds of complexity consists of ''reducing'' a problem to another problem. More precisely, suppose that one may encode a problem {{mvar|A}} of size {{mvar|n}} into a subproblem of size {{math|''f''(''n'')}} of a problem {{mvar|B}}, and that the complexity of {{mvar|A}} is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function {{mvar|f}} increases with {{mvar|n}} and has an [[inverse function]] {{mvar|h}}. Then the complexity of the problem {{mvar|B}} is <math>\Omega(g(h(n))).</math> This is this method that is used for proving that, if [[P ≠ NP]] (an unsolved conjecture), the complexity of every [[NP-complete problem]] is <math>\Omega(n^k),</math> for every positive integer {{mvar|k}}.
| |
| − | | |
| − | A standard method for getting lower bounds of complexity consists of reducing a problem to another problem. More precisely, suppose that one may encode a problem of size into a subproblem of size of a problem , and that the complexity of is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function increases with and has an inverse function . Then the complexity of the problem is <math>\Omega(g(h(n))).</math> This is this method that is used for proving that, if P ≠ NP (an unsolved conjecture), the complexity of every NP-complete problem is <math>\Omega(n^k),</math> for every positive integer .
| |
| − | | |
| − | 获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n)).</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''反函数 inverse function'''{{mvar|h}}，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n))).</math>。这个方法可以用来证明，若'''P ≠ NP'''(一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''NP完全问题 NP-complete problem''' 的复杂度都是 <math>\Omega(n^k),</math>。 | |
| | | | |
| | ==在算法设计中的应用== | | ==在算法设计中的应用== |
| 第161行： |
第120行： |
| | | | |
| | 评估算法的复杂度是'''算法设计 algorithm design'''的一个重要组成部分，因为这给出了一个算法关于预期性能的有用信息。 | | 评估算法的复杂度是'''算法设计 algorithm design'''的一个重要组成部分，因为这给出了一个算法关于预期性能的有用信息。 |
| − |
| |
| − | It is a common misconception that the evaluation of the complexity of algorithms will become less important as a result of [[Moore's law]], which posits the [[exponential growth]] of the power of modern [[computer]]s. This is wrong because this power increase allows working with large input data ([[big data]]). For example, when one wants to sort alphabetically a list of a few hundreds of entries, such as the [[bibliography]] of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require <math>O(n^2)</math> comparisons would have to do a trillion of comparisons, which would need around three hours at the speed of 10 million of comparisons per second. On the other hand, the [[quicksort]] and [[merge sort]] require only <math>n\log_2 n</math> comparisons (as average-case complexity for the former, as worst-case complexity for the latter). For {{math|1=''n'' = 1,000,000}}, this gives approximately 30,000,000 comparisons, which would only take 3 seconds at 10 million comparisons per second.
| |
| − |
| |
| − | It is a common misconception that the evaluation of the complexity of algorithms will become less important as a result of Moore's law, which posits the exponential growth of the power of modern computers. This is wrong because this power increase allows working with large input data (big data). For example, when one wants to sort alphabetically a list of a few hundreds of entries, such as the bibliography of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require <math>O(n^2)</math> comparisons would have to do a trillion of comparisons, which would need around three hours at the speed of 10 million of comparisons per second. On the other hand, the quicksort and merge sort require only <math>n\log_2 n</math> comparisons (as average-case complexity for the former, as worst-case complexity for the latter). For , this gives approximately 30,000,000 comparisons, which would only take 3 seconds at 10 million comparisons per second.
| |
| | | | |
| | 有一个常见的误解，由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth'''，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据('''大数据 big data''')成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的'''参考书目 bibliography'''，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要<math>O(n^2)</math>次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，'''快速排序 quicksort'''和'''合并排序 merge sort'''只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。 | | 有一个常见的误解，由于'''摩尔定律 Moore's law'''假定了现代计算机功率的'''指数增长 exponential growth'''，对算法复杂度的评估将变得不那么重要。这是错误的，因为这种功率增加同样也会容使得处理较大的输入数据('''大数据 big data''')成为可能。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的'''参考书目 bibliography'''，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万个条目的列表(例如一个大城镇的电话号码) ，需要<math>O(n^2)</math>次比较的基本算法，须进行1万亿次比较运算，即以每秒1000万次的速度进行比较需要大约3个小时。另一方面，'''快速排序 quicksort'''和'''合并排序 merge sort'''只需要<math>n\log_2 n</math>次比较(前者为平均情况复杂度，后者为最坏情况复杂度)。这大约是3000万次比较，以每秒1000万次比较计算，只需要3秒钟。 |
| 第172行： |
第127行： |
| | ==更多资料== | | ==更多资料== |
| | | | |
| − | * [[Computational complexity of mathematical operations]] 数学运算的计算复杂性 | + | * Computational complexity of mathematical operations 数学运算的计算复杂性 |
| | + | |
| | + | |
| | ==引用== | | ==引用== |
| | *{{Citation | | *{{Citation |
| − | | last1=Arora | first1=Sanjeev | author-link1=Sanjeev Arora | + | | last1=Arora | first1=Sanjeev |
| | | last2=Barak | first2=Boaz | | | last2=Barak | first2=Boaz |
| | | title=Computational Complexity: A Modern Approach | | | title=Computational Complexity: A Modern Approach |
| | | url = http://www.cs.princeton.edu/theory/complexity/ | | | url = http://www.cs.princeton.edu/theory/complexity/ |
| − | | publisher=[[Cambridge University Press|Cambridge]] | + | | publisher=Cambridge |
| | | year=2009 | | | year=2009 |
| − | | isbn=978-0-521-42426-4
| |
| − | | zbl=1193.68112
| |
| | }} | | }} |
| | * {{citation | | * {{citation |
| 第191行： |
第146行： |
| | | publisher=[[John Wiley & Sons]] | | | publisher=[[John Wiley & Sons]] |
| | | year=2000 | | | year=2000 |
| − | | isbn=978-0-471-34506-0
| |
| | }} | | }} |
| − | * {{Garey-Johnson}}
| |
| | * {{Citation | | * {{Citation |
| | | last=Goldreich | | | last=Goldreich |
| | | first=Oded | | | first=Oded |
| − | | author-link=Oded Goldreich
| |
| | | url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html | | | url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html |
| | | title = Computational Complexity: A Conceptual Perspective | | | title = Computational Complexity: A Conceptual Perspective |
| 第206行： |
第158行： |
| | | editor1-last=van Leeuwen | | | editor1-last=van Leeuwen |
| | | editor1-first=Jan | | | editor1-first=Jan |
| − | | editor1-link = Jan van Leeuwen
| |
| | | title=Handbook of theoretical computer science (vol. A): algorithms and complexity | | | title=Handbook of theoretical computer science (vol. A): algorithms and complexity |
| − | | publisher=[[MIT Press]] | + | | publisher=MIT Press |
| − | | isbn=978-0-444-88071-0
| |
| | | year=1990 | | | year=1990 |
| | }} | | }} |
| 第215行： |
第165行： |
| | | last = Papadimitriou | | | last = Papadimitriou |
| | | first = Christos | | | first = Christos |
| − | | author-link = Christos Papadimitriou
| |
| | | title = Computational Complexity | | | title = Computational Complexity |
| | | edition = 1st | | | edition = 1st |
| | | year = 1994 | | | year = 1994 |
| | | publisher = Addison Wesley | | | publisher = Addison Wesley |
| − | | isbn = 0-201-53082-1
| |
| | }} | | }} |
| | * {{Citation | | * {{Citation |
| | |last=Sipser | | |last=Sipser |
| | |first=Michael | | |first=Michael |
| − | |author-link=Michael Sipser
| + | |title=Introduction to the Theory of Computation |
| − | |title=[[Introduction to the Theory of Computation]] | |
| | |edition=2nd | | |edition=2nd |
| | |year=2006 | | |year=2006 |
| − | |publisher=[[Thomson Learning|Thomson Course Technology]] | + | |publisher=Thomson Course Technology |
| | |location=USA | | |location=USA |
| − | |isbn=0-534-95097-3
| |
| | }} | | }} |
| | | | |