1,592
个编辑
更改
小第1行：
第1行： − 此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。+ 第17行：
第17行： − + − + − + − 对明确给定算法的复杂性的研究叫做算法分析，而对问题复杂性的研究叫做计算复杂性理论分析。显然，这两个领域是高度相关的，因为一个算法的复杂性总是一个上限问题的复杂性解决这个算法。+ 第73行：
第73行： − 对于许多算法，在计算过程中使用的整数的大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为位复杂度，可能远远大于算术复杂度。例如，计算整数矩阵行列式的算术复杂度是常用算法的数学 o (n ^ 3) / 数学(高斯消去法)。同一算法的比特复杂度在年是指数级的，因为系数的大小可能在计算过程中呈指数增长。另一方面，如果这些算法与多模运算相结合，比特复杂度可以降低到软 o 符号 | 。+ 第105行：
第105行： − 最坏情况复杂性是所有规模输入的最大复杂性，平均情况复杂性是所有规模输入的平均复杂性(这是有道理的，因为给定规模的可能输入数量是有限的)。通常，如果使用“复杂性”而没有进一步说明，这就是考虑的最坏情况下的时间复杂性。+ 第125行：
第125行： − 由于这些原因，人们通常把注意力集中在大复杂性的行为上，即它趋向于无穷大时的渐近行为上。因此，复杂度通常用大 o 表示法来表示。+ 第133行：
第133行： − 例如，通常的整数乘法算法的数学复杂度为 o (n ^ 2) ，/ math 这意味着存在一个常量数学 c u / math，这样两个最多数字的整数的乘法可以在比数学 c un ^ 2更短的时间内完成。 这个界限很尖锐，因为最坏情况下的复杂度和平均情况下的复杂度是 math Omega (n ^ 2) ，/ math 意味着有一个不变的数学 c / 数学，这些复杂度大于数学 c / ln ^ 2。 基数在这些复杂性中没有出现，因为基数的变化只改变数学常数、数学常数和数学常数。 数学+ 第161行：
第161行： − 当计算模型没有被指定时，通常假设它是一个多带图灵机。对于大多数算法，在多磁带图灵机上的时间复杂度与在 ram 机上的相同，尽管可能需要一些关注如何在内存中存储数据以获得这种等价性。+ 第171行：
第171行： − + 第179行：
第179行： − 即使在这样的计算模型还不现实的情况下，它仍然具有重要的理论意义，主要涉及到 p NP 问题，即以“多项式时间”和“非确定性多项式时间”为最小上界形成的复杂性类的一致性问题。在确定性计算机上模拟 np 算法通常需要“ EXPTIME”。如果一个问题可以在不确定机器上用多项式时间求解，则该问题属于复杂类 NP。如果一个问题是 NP 完全问题，粗略地说，它是 NP 问题，并不比任何其他 NP 问题简单。许多组合问题，例如背包问题、旅行推销员问题和布尔可满足性问题问题都是 np 完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个可以在确定性机器上在多项式时间内求解，那么所有 NP 问题也可以在多项式时间内求解，其中一个问题将具有 p NP。一般认为，伴随着实际意义，NP 问题的最坏情况本质上是难以解决的，也就是说，需要的时间比任何合理的时间跨度(几十年!)有趣的输入长度。+ 第191行：
第191行： − + 第217行：
第217行： − 量子计算机是一种计算模型基于量子力学的计算机。丘奇-图灵理论适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，有些问题在理论上可以用量子计算机而不是传统计算机来解决，而且时间复杂度要低得多。目前，这纯粹是理论上的，因为没有人知道如何建造一台高效的量子计算机。+ 第225行：
第225行： − 量子复杂性理论是为了研究用量子计算机解决的复杂问题而发展起来的。它用于后量子密码学，其中包括设计抗量子计算机攻击的密码协议。+ 第251行：
第251行： − 另一方面，一般难以获得问题复杂度的非平凡下界，而且获得这种下界的方法很少。+ 第259行：
第259行： − 为了解决大多数问题，需要读取所有输入数据，这通常需要与数据大小成比例的时间。因此，这些问题的复杂性至少是线性的，也就是说，使用大 Omega 符号，复杂性数学 Omega (n) . / math+ 第267行：
第267行： − 一些问题的解决方案，通常是在计算机代数和计算代数几何，可能是非常大的。在这种情况下，复杂度以输出的最大大小为界较低，因为输出必须被写入。例如，如果解的数目是有限的，一个不确定的多项式次方程组可能有多达数学 d ^ n / math 复解(这是 b zout 定理)。由于这些解必须写下来，所以这个问题的复杂性是 math Omega (d ^ n)。 对于这个问题，我们知道一个复杂数学 d ^ { o (n)} / 数学算法，因此可以认为这个算法是渐近最优的。+ 第275行：
第275行： − Math Omega (n log n) / math 的一个非线性下界是已知的一个排序算法所需的比较次数。因此，最好的排序算法是最优的，因为它们的复杂度是数学 o (n log n)。 / math 这个下限的结果来自于这样一个事实，即对象的排序是有方法的。由于每个比较被分成两部分，所以区分所有顺序所需的比较数量必须验证数学2 ^ n n！ ，/ math 意味着数学 n Omega (n log n) ，/ math 意味着斯特林公式。+ 第283行：
第283行： − 获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个人可以将一个大小问题编码为一个问题大小的子问题，并且其复杂性是 math Omega (g (n))。 / 数学不失一般性，你可以假设函数随着反函数的增加而增加。那么问题的复杂性是 math Omega (g (h (n)))。 这个方法是用来证明，如果 p ≠ NP (一个未解的猜想) ，每个 NP 完全问题的复杂性是 math Omega (n ^ k) ，即每个正整数的数学。+ 第295行：
第295行： − 评估算法的复杂性是算法设计的一个重要部分，因为这给出了关于可能预期的性能的有用信息。+ 第303行：
第303行： − + 第311行：
第311行： − 因此，对复杂性的评估可以在任何实现之前消除许多低效率的算法。这也可用于在不测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最昂贵的步骤，对复杂性的研究还可以将重点放在这些步骤上，从而提高实现的效率。+ 第329行：
第329行： − + 第335行：
第335行： − + 第341行：
第341行： − + 第347行：
第347行： − + 第353行：
第353行： − 剑桥出版社+ 第365行：
第365行： − [国际标准图书编号978-0-521-42426-4]+ 第385行：
第385行： − + 第391行：
第391行： − 首先是鼎珠+ 第397行：
第397行： − + 第409行：
第409行： − 出版商约翰威立+ 第421行：
第421行： − [国际标准图书馆编号978-0-471-34506-0]+ 第437行：
第437行： − + 第443行：
第443行： − 首先，Oded+ 第449行：
第449行： − 作者: Oded Goldreich+ 第461行：
第461行： − + 第467行：
第467行： − 出版商剑桥大学出版社+ 第493行：
第493行： − | 编辑1-1月1日+ 第505行：
第505行： − + 第511行：
第511行： − 出版商: MIT 出版社+ 第517行：
第517行： − [国际标准图书馆编号978-0-444-88071-0]+ 第537行：
第537行： − 最后的帕帕迪米特里欧+ 第543行：
第543行： − 第一个克里斯托+ 第549行：
第549行： − + 第555行：
第555行： − + 第561行：
第561行： − 第一版+ 第573行：
第573行： − 出版商 Addison Wesley+ 第579行：
第579行： − + 第593行：
第593行： − 最后一个诗人+ 第599行：
第599行： − 先是迈克尔+ 第605行：
第605行： − 作者: Michael Sipser+ 第611行：
第611行： − + 第617行：
第617行： − 第二版+ 第629行：
第629行： − 出版商 Thomson Course Technology+ 第635行：
第635行： − + 第641行：
第641行： − +
Moved page from wikipedia:en:Computational complexity (history)
此词条暂由彩云小译翻译，翻译字数共2546，未经人工整理和审校，带来阅读不便，请见谅。
{{Short description|amount of resources (usually time and/or memory) to perform an algorithm}}
{{Short description|amount of resources (usually time and/or memory) to perform an algorithm}}
As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function , where is the size of the input and is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size ) or the average-case complexity (the average of the amount of resources over all inputs of size ). Time complexity is generally expressed as the number of required elementary operations on an input of size , where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size .
As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function , where is the size of the input and is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size ) or the average-case complexity (the average of the amount of resources over all inputs of size ). Time complexity is generally expressed as the number of required elementary operations on an input of size , where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size .
由于运行一个算法所需的资源量通常随输入量的大小而变化，因此复杂性通常用函数表示，其中是输入量的大小，或者是最坏情况复杂性(所需资源量超过所有输入量的最大值) ，或者是平均情况复杂性(所有输入量超过所有输入量的资源量的平均值)。时间复杂度通常表示为对一个大小的输入所需的基本操作的数量，其中基本操作假定在给定的计算机上占用一个常量的时间，并且在不同的计算机上运行时只根据一个常量因子进行改变。空间复杂度通常表示为一个算法对一个大小的输入所需的内存量。
由于运行一个算法所需的资源量通常随输入量的大小而变化，因此复杂性通常用函数表示，其中是输入量的大小，或者是最坏情况复杂性(所需资源量超过所有输入量的最大值) ，或者是平均情况复杂性(所有输入量超过所有输入量的资源量的平均值)。时间复杂度通常表示为对一个大小的输入所需的基本操作的数量，其中基本操作假定在一个给定的计算机上占用一个常量的时间，并且当在另一台计算机上运行时，只根据一个常量因子进行改变。空间复杂度通常表示为一个算法对一个大小的输入所需的内存量。
The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of [[computational problem|problems]] is called [[computational complexity theory]]. Clearly, both areas are highly related, as the complexity of an algorithm is always an [[upper bound]] on the complexity of the problem solved by this algorithm.
The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of [[computational problem|problems]] is called [[computational complexity theory]]. Both areas are highly related, as the complexity of an algorithm is always an [[upper bound]] on the complexity of the problem solved by this algorithm.
The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Clearly, both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm.
The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm.
对明确给定算法的复杂性的研究叫做算法分析，而对问题复杂性的研究叫做计算复杂性理论分析。这两个领域是高度相关的，因为一个算法的复杂度总是一个上限问题的复杂性解决这一算法。
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|.
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|.
对于许多算法，在计算过程中使用的整数的大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为位复杂度，可能远远大于算术复杂度。例如，计算一个整数矩阵的行列式的算术复杂度是 < math > o (n ^ 3) </math > 对于通常的算法(高斯消去法)。同一算法的比特复杂度在年是指数级的，因为系数的大小可能在计算过程中呈指数增长。另一方面，如果这些算法与多模运算相结合，比特复杂度可以降低到软 o 符号 | 。
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.
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.
最坏情况复杂性是所有大小输入的最大复杂性，平均情况复杂性是所有大小输入的平均复杂性(这是有道理的，因为给定大小的可能输入的数量是有限的)。一般来说，如果不进一步说明就使用“复杂性” ，那么这就是考虑的最坏情况时间复杂性。
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.
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.
由于这些原因，人们通常把注意力集中在大复杂性的行为上，即它趋于无穷大时的渐近行为上。因此，复杂度通常用大 o 表示法来表示。
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>
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>
例如，通常的整数乘法算法的复杂度是 < math > o (n ^ 2) ，</math > 这意味着存在一个常量 < math > c _ u </math > ，这样两个整数的乘法最多可以在比 < math > c _ un ^ 2更短的时间内完成。这个界限是尖锐的，因为最坏情况的复杂度和平均情况的复杂度是 < math > Omega (n ^ 2) ，</math > 这意味着存在一个常数 < math > c _ l </math > ，这些复杂度比 < math > c _ ln ^ 2大。这些复杂性中没有出现基数，因为基数的变化只有常数[ math > c _ u ]和[ math > c _ l ]。数学
When the model of computation is not specified, it is generally assumed to be a multitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.
When the model of computation is not specified, it is generally assumed to be a multitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.
当计算模型没有被指定时，通常假设它是一个多带图灵机。对于大多数算法，在多带图灵机上的时间复杂度与在 ram 机上的相同，尽管可能需要在数据如何存储在内存中以获得这种等价性方面进行一些注意。
In a non-deterministic model of computation, such as non-deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to quantum computing via superposed entangled states in running specific quantum algorithms, like e.g. Shor's factorization of yet only small integers (: 21 = 3 × 7).
In a non-deterministic model of computation, such as non-deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to quantum computing via superposed entangled states in running specific quantum algorithms, like e.g. Shor's factorization of yet only small integers (: 21 = 3 × 7).
在非确定性的计算模型中，例如不确定的图灵机，在计算的某些步骤中可能会有一些选择。在复杂性理论中，一个人同时考虑所有可能的选择，而非确定性的时间复杂性是所需的时间，当最好的选择总是做出。换句话说，我们认为计算是在所需的多个(相同的)处理器上同时进行的，而不确定的计算时间是完成计算的第一个处理器所花费的时间。这种并行性在一定程度上可以通过运行特定量子算法的叠加纠缠态来适应量子计算。肖尔的因式分解只是小整数(: 2137)。
在非确定性的计算模型中，例如不确定的图灵机，在计算的某些步骤中可能会有一些选择。在复杂性理论中，一个人同时考虑所有可能的选择，而非确定性的时间复杂性是所需的时间，当最好的选择总是做出。换句话说，我们认为计算是在所需的多个(相同的)处理器上同时进行的，而不确定的计算时间是第一个处理器完成计算所花费的时间。这种并行性在一定程度上可以通过运行特定量子算法的叠加纠缠态来实现量子计算。Shor 的小整数因子分解(: 21 = 3 × 7)。
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.
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 问题，即以“多项式时间”和“非确定性多项式时间”为最小上界所形成的复杂性类的一致性问题。在确定性计算机上模拟 np 算法通常需要“ EXPTIME”。如果一个问题可以在多项式时间内在非确定性机器上求解，则该问题属于复杂类 NP。如果一个问题是 NP 完全问题，粗略地说，它是 NP 问题，并不比任何其他 NP 问题简单。许多组合问题，例如背包问题、旅行推销员问题和布尔可满足性问题问题都是 np 完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那么所有 NP 问题都可以在多项式时间内求解，其中一个问题就有 p = NP。一般认为，伴随着实际意义，NP 问题的最坏情况本质上是难以解决的，也就是说，需要的时间比任何合理的时间跨度(几十年!)有趣的输入长度。
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a network and is therefore much slower.
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a network and is therefore much slower.
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中，处理器之间的数据传输 / 数据传输非常快，而在并行计算中，数据传输通过网络完成，因此速度要慢得多。
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中，处理器之间的数据传输/数据传输非常快，而在并行计算中，数据传输通过网络完成，因此速度要慢得多。
A quantum computer is a computer whose model of computation is based on quantum mechanics. The Church–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower time complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.
A quantum computer is a computer whose model of computation is based on quantum mechanics. The Church–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower time complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.
量子计算机是一种计算机，其计算模型是基于量子力学的。丘奇-图灵理论适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，一些问题在理论上可以解决与一个更低的时间复杂性使用量子计算机而不是传统的计算机。目前，这纯粹是理论上的，因为没有人知道如何建造一台高效的量子计算机。
Quantum complexity theory has been developed to study the complexity classes of problems solved using quantum computers. It is used in post-quantum cryptography, which consists of designing cryptographic protocols that are resistant to attacks by quantum computers.
Quantum complexity theory has been developed to study the complexity classes of problems solved using quantum computers. It is used in post-quantum cryptography, which consists of designing cryptographic protocols that are resistant to attacks by quantum computers.
量子复杂性理论已经发展到研究用量子计算机解决的问题的复杂性类。它用于后量子密码学，其中包括设计抗量子计算机攻击的密码协议。
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
另一方面，问题复杂度的非平凡下界一般难以获得，而获得这种下界的方法很少。
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>
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>
为了解决大多数问题，它需要读取所有输入数据，这通常需要与数据大小成比例的时间。因此，这些问题的复杂性至少是线性的，也就是说，使用大的 Omega 符号，复杂性 < math > Omega (n)
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.
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.
一些问题的解决方案，特别是计算机代数和计算代数几何，可能是非常大的。在这种情况下，复杂度以输出的最大大小为界较低，因为输出必须被写入。例如，如果解的数目是有限的，一个不确定的次数的多项式方程组可能有多达 < math > d ^ n </math > 的复杂解(这是 b é zout 的定理)。由于这些解必须写下来，所以这个问题的复杂性是“ math” > “ Omega (d ^ n)”。对于这个问题，已知一个复杂度 < math > d ^ { o (n)} </math > 的算法，因此可以认为是渐近准最优的。
A nonlinear lower bound of <math>\Omega(n\log n)</math> is known for the number of comparisons needed for a sorting algorithm. Thus the best sorting algorithms are optimal, as their complexity is <math>O(n\log n).</math> This lower bound results from the fact that there are ways of ordering objects. As each comparison splits in two parts this set of orders, the number of of comparisons that are needed for distinguishing all orders must verify <math>2^N>n!,</math> which implies <math>N =\Omega(n\log n),</math> by Stirling's formula.
A nonlinear lower bound of <math>\Omega(n\log n)</math> is known for the number of comparisons needed for a sorting algorithm. Thus the best sorting algorithms are optimal, as their complexity is <math>O(n\log n).</math> This lower bound results from the fact that there are ways of ordering objects. As each comparison splits in two parts this set of orders, the number of of comparisons that are needed for distinguishing all orders must verify <math>2^N>n!,</math> which implies <math>N =\Omega(n\log n),</math> by Stirling's formula.
O < math > Omega (n log n) </math > 的一个非线性下界是已知的一个排序算法所需的比较次数。因此，最好的排序算法是最优的，因为它们的复杂度是 < math > o (n log n) 。</math > 这个下限是由于存在对象排序的方法这一事实造成的。当每个比较被分成两部分时，区分所有比较序列所需的比较数量必须验证 < math > 2 ^ n > n！，这意味着 < math > n = Omega (n log n) ，</math > 由 Stirling 的公式。
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 .
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 .
获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个人可以将一个大小问题编码为一个问题大小的子问题，并且这个问题的复杂性是 < math > Omega (g (n))。在不失一般性中，我们可以假设函数随着反函数的增加而增加。那么问题的复杂性就是“ math” > “ Omega”(g (h (n))) 。这个方法被用来证明，如果 p ≠ NP (一个未解的猜想) ，每个 NP 完全问题的复杂性是对于每个正整数都是 < math > Omega (n ^ k) ，</math > 。
Evaluating the complexity of an algorithm is an important part of algorithm design, as this gives useful information on the performance that may be expected.
Evaluating the complexity of an algorithm is an important part of algorithm design, as this gives useful information on the performance that may be expected.
评估算法的复杂性是算法设计的一个重要组成部分，因为这给出了关于可能预期的性能的有用信息。
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.
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.
这是一个常见的误解，认为由于摩尔定律，对算法复杂性的评估将变得不那么重要，摩尔定律假定了现代计算机的强大指数增长。这是错误的，因为这种功率的增加允许处理大输入数据(大数据)。例如，当一个人想要按字母顺序对几百个条目的列表进行排序，比如一本书的参考书目，任何算法都应该在不到一秒的时间内工作正常。另一方面，对于一个包含100万条目的列表(例如一个大城镇的电话号码) ，需要进行数学 o (n ^ 2) / 数学比较的基本算法必须进行一万亿次比较，以每秒1,000万次比较的速度，这需要大约3个小时。另一方面，快速排序和合并排序只需要数学 n log 2n / math 比较(前者的平均情况复杂度，后者的最坏情况复杂度)。因为，这给出了大约30,000,000次比较，在每秒10,000,000次比较中只需要3秒钟。
这是一个常见的误解，认为由于摩尔定律，对算法复杂性的评估将变得不那么重要，摩尔定律假定了现代计算机的强大指数增长。这是错误的，因为这种功率的增加允许处理大输入数据(大数据)。例如，当一个人想要按字母顺序对数百个条目的列表进行排序时，比如一本书的参考书目，任何算法都应该在不到一秒的时间内就能正常工作。另一方面，对于一个包含100万条目的列表(例如一个大城镇的电话号码) ，需要进行数学比较的基本算法需要进行一万亿次比较，以每秒1000万次比较的速度进行比较需要大约3个小时。另一方面，快速排序和合并排序只需要 < math > n log _ 2 n </math > 比较(前者的平均情况复杂度，后者的最坏情况复杂度)。因为，这给出了大约30,000,000次比较，在每秒10,000,000次比较的情况下只需要3秒钟。
Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.
Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.
因此，对复杂性的评估可能允许在任何实现之前消除许多低效率的算法。这也可用于在不测试所有变量的情况下调优复杂的算法。通过确定复杂算法中最昂贵的步骤，对复杂性的研究还可以将重点放在这些步骤上，从而提高实现的效率。
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
1 | last 1 Arora | first1 Sanjeev | authorlink1 Sanjeev Arora
1 = Arora | first1 = Sanjeev | authorlink1 = Sanjeev Arora
| last2=Barak | first2=Boaz
| last2=Barak | first2=Boaz
| last2=Barak | first2=Boaz
| last2=Barak | first2=Boaz
2 Barak | first2 Boaz
2 = Barak | first2 = Boaz
| title=Computational Complexity: A Modern Approach
| title=Computational Complexity: A Modern Approach
| title=Computational Complexity: A Modern Approach
| title=Computational Complexity: A Modern Approach
计算复杂性: 一种现代方法
| title = 计算复杂性: 一种现代方法
| url = http://www.cs.princeton.edu/theory/complexity/
| url = http://www.cs.princeton.edu/theory/complexity/
| url = http://www.cs.princeton.edu/theory/complexity/
| url = http://www.cs.princeton.edu/theory/complexity/
Http://www.cs.princeton.edu/theory/complexity/
Http://www.cs.princeton.edu/theory/complexity/
| publisher=[[Cambridge University Press|Cambridge]]
| publisher=[[Cambridge University Press|Cambridge]]
| publisher=Cambridge
| publisher=Cambridge
| publisher = Cambridge
| year=2009
| year=2009
| isbn=978-0-521-42426-4
| isbn=978-0-521-42426-4
| isbn = 978-0-521-42426-4
| zbl=1193.68112
| zbl=1193.68112
| last=Du
| last=Du
| last Du
| last = Du
| first=Ding-Zhu
| first=Ding-Zhu
| first=Ding-Zhu
| first=Ding-Zhu
| 第一 = 鼎柱
| author2=Ko, Ker-I
| author2=Ko, Ker-I
| author2=Ko, Ker-I
| author2=Ko, Ker-I
| author2 Ko，ker
| author2 = Ko，Ker-I
| title=Theory of Computational Complexity
| title=Theory of Computational Complexity
| publisher=John Wiley & Sons
| publisher=John Wiley & Sons
2012年3月24日 | publisher = 约翰威立
| year=2000
| year=2000
| isbn=978-0-471-34506-0
| isbn=978-0-471-34506-0
| isbn = 978-0-471-34506-0
}}
}}
| last=Goldreich
| last=Goldreich
| last Goldreich
| last = Goldreich
| first=Oded
| first=Oded
| first=Oded
| first=Oded
第一个 = Oded
| authorlink=Oded Goldreich
| authorlink=Oded Goldreich
| authorlink=Oded Goldreich
| authorlink=Oded Goldreich
| authorlink = 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
计算复杂性: 一个概念性的视角
| title = 计算复杂性: 一个概念性的视角
| publisher = Cambridge University Press
| publisher = Cambridge University Press
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| year = 2008
| year = 2008
| editor1-first=Jan
| editor1-first=Jan
1-first = Jan
| editor1-link = Jan van Leeuwen
| 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
理论计算机科学手册。A)算法和复杂性
| title = 理论计算机科学手册。A)算法和复杂性
| publisher=[[MIT Press]]
| publisher=[[MIT Press]]
| publisher=MIT Press
| publisher=MIT Press
| publisher = MIT Press
| isbn=978-0-444-88071-0
| isbn=978-0-444-88071-0
| isbn=978-0-444-88071-0
| isbn=978-0-444-88071-0
| isbn = 978-0-444-88071-0
| year=1990
| year=1990
| last = Papadimitriou
| last = Papadimitriou
| last = Papadimitriou
| first = Christos
| first = Christos
| first = Christos
| first = Christos
第一季，克里斯托
| authorlink = Christos Papadimitriou
| authorlink = Christos Papadimitriou
| authorlink = Christos Papadimitriou
| authorlink = Christos Papadimitriou
作者 / 链接赫里斯托斯·帕帕季米特里乌
作者/链接 = 赫里斯托斯·帕帕季米特里乌
| title = Computational Complexity
| title = Computational Complexity
| title = Computational Complexity
| title = Computational Complexity
计算复杂性
| title = 计算复杂性
| edition = 1st
| edition = 1st
| edition = 1st
| edition = 1st
1st
| year = 1994
| year = 1994
| publisher = Addison Wesley
| publisher = Addison Wesley
艾迪生 · 韦斯利
| isbn = 0-201-53082-1
| isbn = 0-201-53082-1
| isbn = 0-201-53082-1
| isbn = 0-201-53082-1
| isbn 0-201-53082-1
| isbn = 0-201-53082-1
}}
}}
|last=Sipser
|last=Sipser
最后 = Sipser
|first=Michael
|first=Michael
|first=Michael
|first=Michael
迈克尔
|authorlink=Michael Sipser
|authorlink=Michael Sipser
|authorlink=Michael Sipser
|authorlink=Michael Sipser
| authorlink = Michael Sipser
|title=[[Introduction to the Theory of Computation]]
|title=[[Introduction to the Theory of Computation]]
|title=Introduction to the Theory of Computation
|title=Introduction to the Theory of Computation
美国计算理论学会简介
| title = 美国计算理论学会简介
|edition=2nd
|edition=2nd
|edition=2nd
|edition=2nd
2nd
|year=2006
|year=2006
|publisher=Thomson Course Technology
|publisher=Thomson Course Technology
| publisher = Thomson Course Technology
|location=USA
|location=USA
|location=USA
|location=USA
| 位置美国
| location = USA
|isbn=0-534-95097-3
|isbn=0-534-95097-3
|isbn=0-534-95097-3
|isbn=0-534-95097-3
| isbn 0-534-95097-3
| isbn = 0-534-95097-3
}}
}}