307
个编辑
更改
→Complexity as a function of input size
==Complexity as a function of input size==
==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.''
The worst-case complexity is the maximum of the complexity over all inputs of size , and the average-case complexity is the average of the complexity over all inputs of size (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.
The worst-case complexity is the maximum of the complexity over all inputs of size , and the average-case complexity is the average of the complexity over all inputs of size (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.
'''<font color="#ff8000">最坏情况复杂度 worst-case complexity</font>'''是所有输入{{mvar|n}}长度的最大复杂度，'''<font color="#ff8000">平均情况复杂度 average-case complexity</font>'''是所有输入{{mvar|n}}长度的平均复杂度(这是有道理的，因为给定长度的可能输入的数量是有限的)。一般来说，如果使用“复杂度”且不进行进一步说明 ，即考虑最坏情况时间复杂度。
==Asymptotic complexity==
==Asymptotic complexity==