更改

The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm.

The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm.

对一个有明确定义的算法的复杂度进行的研究叫做'''<font color="#ff8000">算法分析 analysis of algorithm</font>'''，而对'''<font color="#ff8000">问题 problem</font>'''的复杂度研究叫做'''<font color="#ff8000">计算复杂度理论 computation complexity theory</font>'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题（problem）；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>'6nlogn</math>。

对一个有明确定义的算法的复杂度进行的研究叫做'''<font color="#ff8000">算法分析 analysis of algorithm</font>'''，而对'''<font color="#ff8000">问题 problem</font>'''的复杂度研究叫做'''<font color="#ff8000">计算复杂度理论 computation complexity theory</font>'''分析。举个例子，怎样把一串数字从小到大进行排序，是一个问题（problem）；而针对这一问题，我们有多种明确定义的算法，如选择排序，归并排序等。假设我们有<math>n</math>个数字，那么排序问题的复杂度就是<math>nlogn</math>，而选择排序的复杂度是<math>n^2</math>，归并排序的复杂度是<math>6nlogn</math>。

这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''<font color="#ff8000">上限 upper bound</font>'''。

这两个领域是高度相关的，因为算法的复杂度一直是该算法所求解问题复杂度的'''<font color="#ff8000">上限 upper bound</font>'''。

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

在'''<font color="#ff8000">复杂度理论 complexity theory</font>'''中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过计数在计算过程中执行的基本操作数量来实现的。这些操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。

在'''<font color="#ff8000">复杂度理论 complexity theory</font>'''中不使用通常的时间单位(秒、分等)，因为它们过于依赖于特定计算机的选择和技术的演变。例如，今天的计算机执行算法的速度明显快于20世纪60年代的计算机; 然而，这不是算法的固有特征，而是计算机硬件技术进步的结果。复杂度理论旨在量化算法的内在时间需求，也就是算法对任何计算机的基本时间约束。这是通过统计在计算过程中执行的基本操作数量来实现的。这些基本操作假定在给定的机器上占用常量时间(即不受输入大小的影响) ，通常被称为步骤。

 

Another important resource is the size of [[computer memory]] that is needed for running algorithms.

Another important resource is the size of [[computer memory]] that is needed for running algorithms.

另一个重要的资源是运行算法所需的'''<font color="#ff8000">计算机内存 computer memory</font>'''大小。

另一个重要的资源是运行算法所需的'''<font color="#ff8000">计算机内存 computer memory</font>'''大小。

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

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">整数矩阵 integer matrix</font>''' '''<font color="#ff8000">行列式 determinant</font>''' 的算术复杂度是<math>O(n^3)</math>。因为系数的大小可能在计算过程中呈指数增长，相同算法的位复杂度是指数级的。另一方面，如果这些算法与多模运算相结合，位复杂度可以降低到[[soft O notation|{{math|''O''^~(''n''⁴)}}]]。

In sorting and searching, the resource that is generally considered is the number of entries comparisons. This is generally a good measure of the time complexity if data are suitably organized.

In sorting and searching, the resource that is generally considered is the number of entries comparisons. This is generally a good measure of the time complexity if data are suitably organized.

在'''<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==

==Complexity as a function of input size==