307
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由彩云小译翻译，翻译字数共2546，未经人工整理和审校，带来阅读不便，请见谅。+ 第9行：
第9行： − 在计算机科学中，一个算法的计算复杂度或简单的复杂度就是运行它所需要的资源量。特别关注时间和内存需求。+ 第17行：
第17行： − 由于运行一个算法所需的资源量通常随输入量的大小而变化，因此复杂性通常用函数表示，其中是输入量的大小，或者是最坏情况复杂性(所需资源量超过所有输入量的最大值) ，或者是平均情况复杂性(所有输入量超过所有输入量的资源量的平均值)。时间复杂度通常表示为对一个大小的输入所需的基本操作的数量，其中基本操作假定在一个给定的计算机上占用一个常量的时间，并且当在另一台计算机上运行时，只根据一个常量因子进行改变。空间复杂度通常表示为一个算法对一个大小的输入所需的内存量。+
无编辑摘要
此词条暂由小竹凉翻译，翻译字数共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>'''量。