561
个编辑
更改
→Upper and lower bounds on the complexity of problems问题复杂性的上下界
To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n). However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).
To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n). However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).
对计算时间或类似的资源进行分类时，演示最有效算法解决给定问题所需的最大时间的上下界是很有帮助的。一个算法的复杂性通常被认为是其最坏情况的复杂性，除非另有说明。分析一个特定的算法属于'''<font color="#ff8000"> 算法分析Analysis of algorithms</font>'''的范畴。为了给出问题时间复杂度的上界 T(n) ，只需要给出一个运行时间最多为 T(n)的特定算法。然而，证明下界要困难得多，因为下界表明了解决给定问题的所有可能的算法。“所有可能的算法”这个短语不仅包括今天已知的算法，还包括将来可能发现的任何算法。为了给出问题T(n)的下界，需要证明任何算法的时间复杂度都不能低于 T(n)。
上下界通常使用大 O 符号来表示，它隐藏了常数因子和较小的项。这使得边界独立于使用的计算模型的具体细节。例如，如果 T(n) = 7n<sup>2</sup> + 15n + 40,在大O表示法中，人们会写T(n) = O(n<sup>2</sup>)。
上下界通常使用大 O 符号来表示，它隐藏了常数因子和较小的项。这使得边界独立于使用的计算模型的具体细节。例如，如果 T(n) = 7n<sup>2</sup> + 15n + 40,在大O表示法中，人们会写T(n) = O(n<sup>2</sup>)。
==Complexity classes复杂性类==
==Complexity classes复杂性类==