307
个编辑
更改
跳到导航
跳到搜索
第64行：
第64行： − 算术运算的数量是另一种常用的资源。在这种情况下，人们会谈到算术复杂性。如果一个人知道一个计算过程中出现的数字的二进制表示的大小的上限，时间复杂度通常是算术复杂度乘以一个常数因子。+ 第72行：
第72行： − 对于许多算法，在计算过程中使用的整数的大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为位复杂度，可能远远大于算术复杂度。例如，计算一个整数矩阵的行列式的算术复杂度是 < math > o (n ^ 3) </math > 对于通常的算法(高斯消去法)。同一算法的比特复杂度在年是指数级的，因为系数的大小可能在计算过程中呈指数增长。另一方面，如果这些算法与多模运算相结合，比特复杂度可以降低到软 o 符号 | 。+
→Others
The number of arithmetic operations is another resource that is commonly used. In this case, one talks of arithmetic complexity. If one knows an upper bound on the size of the binary representation of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.
The number of arithmetic operations is another resource that is commonly used. In this case, one talks of arithmetic complexity. If one knows an upper bound on the size of the binary representation of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.
'''<font color="#ff8000">算术运算 arithmetic operations</font>'''的数量是另一种常用的资源。在这种情况下，人们会谈到'''算术复杂度'''。如果已知一个计算过程中出现的数的'''<font color="#ff8000">二进制表示 binary representation</font>'''长度的'''<font color="#ff8000">上限 upper bound</font>'''，时间复杂度通常是该算术复杂度乘以一个常数因子。
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|.
对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为'''<font color="#ff8000">位复杂度 bit complexity</font>'''，可能远远大于算术复杂度。例如，根据通常的算法('''<font color="#ff8000">高斯消去法 Gaussian elimination</font>''')计算一个{{math|''n''×''n''}}'''<font color="#ff8000">整数矩阵 integer matrix</font>''''''<font color="#ff8000">行列式 determinant</font>'''的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到[[soft O notation|{{math|''O''<sup>~</sup>(''n''<sup>4</sup>)}}]]。