307
个编辑
更改
无编辑摘要
此词条暂由小竹凉翻译，翻译字数共2546，未经人工整理和审校，带来阅读不便，请见谅。
{{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 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>'''需求。
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>'''量。