更改

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

In [[computer science]], the '''computational complexity''' or simply '''complexity''' of an [[algorithm]] is the amount of resources required to run it. Particular focus is given to [[time complexity|time]] and [[space complexity|memory]] requirements.

In [[computer science]], the '''computational complexity''' or simply '''complexity''' of an [[algorithm]] is the amount of resources required to run it. Particular focus is given to [[time complexity|time]] and [[space complexity|memory]] requirements.

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''^~(''n''⁴)}}]]。

对于许多算法，在计算过程中使用的整数大小是没有界限的，并且考虑算术运算占用一个常量时间是不现实的。因此，时间复杂度，在此上下文中通常称为 '''<font color="#ff8000">位复杂度 bit complexity</font>'''，可能远远大于算术复杂度。例如，根据通常的算法 '''<font color="#ff8000">高斯消去法 Gaussian elimination</font>''' 计算一个{{math|''n''×''n''}} <font color="#ff8000">整数矩阵</font><font color="#ff8000">行列式</font> 的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到[[soft O notation|{{math|''O''^~(''n''⁴)}}]]。

在'''<font color="#ff8000">排序 sorting</font>'''和'''<font color="#ff8000">搜索 searching</font>'''中，通常考虑的资源是需要做几次''比较大小''。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。

在'''<font color="#ff8000">排序 sorting</font>'''和'''<font color="#ff8000">搜索 searching</font>'''中，通常考虑的资源是需要做几次''比较大小''。如果数据组织得当，这通常是一个很好的时间复杂度测量方法。

==Complexity as a function of input size==

==复杂度：输入规模的函数==

复杂度作为关于输入长度的函数

复杂度作为关于输入长度的函数

:''For clarity, only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources.''  

:''For clarity, only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources.''