更改

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>

例如，通常整数'''<font color="#ff8000">乘法 multiplication</font>'''的复杂度是<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>大。这些复杂度中没有出现'''<font color="#ff8000">基数 radix</font>'''，因为基数只改变常数<math>c_u</math>和<math>c_l.</math>

例如，通常整数'''<font color="#ff8000">乘法 multiplication</font>'''的复杂度是<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>大。

 

The evaluation of the complexity relies on the choice of a [[model of computation]], which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being [[multitape Turing machine]].

The evaluation of the complexity relies on the choice of a [[model of computation]], which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being [[multitape Turing machine]].

The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being multitape Turing machine.

The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being multitape Turing machine.

复杂度的评估依赖于'''<font color="#ff8000">计算模型 model of computation</font>'''的选择，包括定义在一个时间单位内完成的基本操作。当计算模型没有被明确指定时，它通常被认为是'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。

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

 

 

===Deterministic models===

===Deterministic models===

A deterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were recursive functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers.

A deterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were recursive functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers.

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

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

 

 

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.

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.

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

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

===Non-deterministic computation===

===Non-deterministic computation===

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).

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

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

 

 

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 (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.

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.

即使这样的计算模型还不现实，它仍然具有重要的理论意义，主要涉及'''<font color="#ff8000">P = NP</font>'''问题，即以“多项式时间”和“非确定性多项式时间”为最小上界所形成的复杂度类的一致性问题。在确定性计算机上模拟 NP算法通常需要“指数时间”。如果一个问题可以在在非确定性机器上'''<font color="#ff8000">多项式时间 polynomial time</font>'''内求解，则该问题属于复杂类 '''<font color="#ff8000">NP</font>'''。如果一个问题是'''<font color="#ff8000"> NP完全问题  NP-complete</font>'''，粗略地说，该问题属于 NP 问题，不比其他任何 NP 问题简单。许多'''<font color="#ff8000">组合 combinatorial</font>'''问题，例如'''<font color="#ff8000">背包问题 Knapsack problem</font>'''、'''<font color="#ff8000">旅行推销员问题 travelling salesman problem</font>'''和'''<font color="#ff8000">布尔可满足性问题 Boolean satisfiability problem</font>'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那么所有 NP 问题都可以在多项式时间内求解，其中一个问题就有P = NP。一般认为，伴随着实际意义，NP 问题的最坏情况本质上是难以解决的，也就是说，比任何合理的时间跨度(几十年!)都要长。

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

 

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

===Parallel and distributed computation===

===Parallel and distributed computation===