更改

===时间===

===时间===

The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity.

The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity.

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

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

The usual units of time (seconds, minutes etc.) are not used in [[computational complexity theory|complexity theory]] because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in [[computer hardware]]. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on ''any'' computer. This is achieved by counting the number of ''elementary operations'' that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called ''steps''.

The usual units of time (seconds, minutes etc.) are not used in [[computational complexity theory|complexity theory]] because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in [[computer hardware]]. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on ''any'' computer. This is achieved by counting the number of ''elementary operations'' that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called ''steps''.

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.

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''}}长度(以'''<font color="#ff8000">比特 bit</font>'''为单位)的函数，因此，复杂度是一个关于{{math|''n''}}的函数。然而，对于同样长度的不同输入，算法的复杂度可能会大不相同。因此，一些复杂度函数被广泛使用。

计算一个算法对于所有可能输入的所需要的步骤数是不可能的。由于复杂度通常随着输入的规模而增加，复杂度通常表示为输入值 {{math|''n''}} 长度（以'''<font color="#ff8000">比特 bit</font>'''为单位）的函数。因此，复杂度是一个关于 {{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 {{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.

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.

'''<font color="#ff8000">最坏情况复杂度 worst-case complexity</font>'''是所有输入{{mvar|n}}长度的最大复杂度，'''<font color="#ff8000">平均情况复杂度 average-case complexity</font>'''是所有输入{{mvar|n}}长度的平均复杂度(这是有道理的，因为给定长度的可能输入的数量是有限的)。一般来说，如果使用“复杂度”且不进行进一步说明 ，即考虑最坏情况时间复杂度。

'''<font color="#ff8000">最坏情况复杂度 worst-case complexity</font>'''是对所有输入{{mvar|n}}长度中的最大复杂度，'''<font color="#ff8000">平均情况复杂度 average-case complexity</font>'''是对所有输入{{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 {{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.

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

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}}的复杂度行为上，即它趋于无穷大的'''<font color="#ff8000">渐近行为 asymptotic behavior</font>'''上。因此，复杂度通常用'''<font color="#ff8000">大O符号 big O notation</font>'''来表示。

由于这些原因，人们通常把注意力集中在大{{mvar|n}}的复杂度上，即输入规模趋于无穷大的'''<font color="#ff8000">渐近行为 asymptotic behavior</font>'''上。因此，复杂度通常用'''<font color="#ff8000">大O符号 big O notation</font>'''来表示。