更改

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 and 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 and memory requirements.

在'''<font color="#ff8000">计算机科学 computer science</font>'''中，一个'''<font color="#ff8000">算法 algorithm</font>'''的'''计算复杂度'''或简单的'''复杂度'''就是运行它所需要的资源量。特别关注'''<font color="#ff8000">时间 time</font>'''和'''<font color="#ff8000">内存 memory</font>'''需求。

在'''<font color="#ff8000">计算机科学 computer science</font>'''中，一个'''<font color="#ff8000">算法 algorithm</font>'''的'''计算复杂度'''或简单的'''复杂度'''就是运行这个算法所需要的资源量，特别是'''时间'''（CPU占用时间）和'''空间'''（内存占用空间）需求。

As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function , where  is the size of the input and  is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size ) or the average-case complexity (the average of the amount of resources over all inputs of size ). Time complexity is generally expressed as the number of required elementary operations on an input of size , where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size .

As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function , where  is the size of the input and  is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size ) or the average-case complexity (the average of the amount of resources over all inputs of size ). Time complexity is generally expressed as the number of required elementary operations on an input of size , where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size .

由于运行一个算法所需的资源量通常随输入量的大小而变化，因此复杂度通常用函数{{math|''n'' → ''f''(''n'')}}表示，其中{{math|''n''}}是输入量的大小，{{math|''f''(''n'')}}是'''<font color="#ff8000">最坏情况复杂度 worst-case complexity</font>'''(所有输入大小为 {{math|''n''}}时所需的资源量的最大值) ，或是'''<font color="#ff8000">平均情况复杂度 average-case complexity</font>'''(资源总量相对于{{math|''n''}}大小的所有投入的平均值)。'''<font color="#ff8000">时间复杂度 Time complexity</font>'''通常表示为对一个输入值长度所需基本操作的数量，其中基本操作假定在一个给定的计算机上占用一个常量的时间，并且当在另一台计算机上运行时，只根据一个常量因子进行改变。'''<font color="#ff8000">空间复杂度 space complexity</font>'''通常表示为算法对一个输入值长度所需的'''<font color="#ff8000">内存 memory</font>'''量。

由于运行一个算法所需的资源量通常随输入规模的大小而变化，因此复杂度通常用函数{{math| ''f''(''n'')}}表示，其中{{math|''n''}}是输入量的大小，{{math|''f''(''n'')}}是'''<font color="#ff8000">最坏情况复杂度 worst-case complexity</font>'''(输入大小为 {{math|''n''}}时所需的资源量的最大值) ，或是'''<font color="#ff8000">平均情况复杂度 average-case complexity</font>'''(资源总量相对于{{math|''n''}}的所有占用的平均值)。'''<font color="#ff8000">时间复杂度 Time complexity</font>'''通常表示为对一个输入值长度所需基本操作（通常是加法操作或者乘法操作）的数量。我们假设基本操作在一台计算机上只占用一个不变的时间量（比如1纳秒），而在另一台计算机上运行时，只根据一个常量因子进行改变（比如k*1纳秒）。'''<font color="#ff8000">空间复杂度 space complexity</font>'''通常表示为算法对一个输入值长度所需的内存量。

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>'''分析。这两个领域是高度相关的，因为算法的复杂度一直是该算法数学求解问题复杂度的'''<font color="#ff8000">上限 upper bound</font>'''。

对一个有明确定义的算法的复杂度进行的研究叫做'''<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>。

时间

 

===时间===

 

 

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.