307
个编辑
更改
跳到导航
跳到搜索
第108行：
第108行： + 第115行：
第116行： − 通常很难精确计算最坏情况和平均情况复杂度。此外，这些精确值提供了很少的实际应用，因为计算机或计算模型的任何变化都会稍微改变复杂性。此外，资源的使用对于小的值来说并不重要，这使得对于小的值来说，易于实现通常比好的复杂性更有趣。+ 第123行：
第124行： − 由于这些原因，人们通常把注意力集中在大复杂性的行为上，即它趋于无穷大时的渐近行为上。因此，复杂度通常用大 o 表示法来表示。+ 第131行：
第132行： − 例如，通常的整数乘法算法的复杂度是 < 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 ]。数学+ − −
→Asymptotic complexity
==Asymptotic complexity==
==Asymptotic complexity==
渐近复杂度
{{see also|Asymptotic computational complexity}}
{{see also|Asymptotic computational 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}}，操作上的便利通常比好的复杂度更令人感兴趣。
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>'''来表示。
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 > c _ u ]和[ math > c _ l ]。数学
==Models of computation==
==Models of computation==