307
个编辑
更改
跳到导航
跳到搜索
第223行：
第223行： + + 第228行：
第230行： − 问题的复杂性是解决问题的算法(包括未知算法)复杂性的下确界。因此，问题的复杂性并不比任何解决问题的算法的复杂性大。+ 第236行：
第238行： − 由此可见，用大 o 符号表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。+ 第244行：
第246行： − 另一方面，问题复杂度的非平凡下界一般难以获得，而获得这种下界的方法很少。+ 第252行：
第254行： − 为了解决大多数问题，它需要读取所有输入数据，这通常需要与数据大小成比例的时间。因此，这些问题的复杂性至少是线性的，也就是说，使用大的 Omega 符号，复杂性 < math > Omega (n)+ 第277行：
第279行： − −
→Problem complexity (lower bounds)
==Problem complexity (lower bounds)==
==Problem complexity (lower bounds)==
问题复杂度(下限)
The complexity of a problem is the [[infimum]] of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
The complexity of a problem is the [[infimum]] of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
问题的复杂度是解决问题算法(包括未知算法)复杂度的'''<font color="#ff8000">下确界 infimum</font>'''。因此，问题的复杂度比任何解决该问题的算法的复杂度都要小。
It follows that every complexity that is expressed with big O notation is a complexity of the algorithm as well as of the corresponding problem.
It follows that every complexity that is expressed with big O notation is a complexity of the algorithm as well as of the corresponding problem.
由此可见，用'''<font color="#ff8000">大O符号 big O notation</font>'''表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
另一方面，问题复杂度的非平凡下界一般难以获得，并且获得这种下界的方法很少。
For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least linear, that is, using big omega notation, a complexity <math>\Omega(n).</math>
For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least linear, that is, using big omega notation, a complexity <math>\Omega(n).</math>
为了解决大多数问题，往往需要与数据大小成比例的时间来读取所有输入数据。因此，这些问题的复杂度至少是'''<font color="#ff8000">线性的 linear</font>'''，使用'''<font color="#ff8000">大欧米茄符号 big omega notation</font>'''，记为复杂度<math>\Omega(n).</math>
获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个人可以将一个大小问题编码为一个问题大小的子问题，并且这个问题的复杂性是 < math > Omega (g (n))。在不失一般性中，我们可以假设函数随着反函数的增加而增加。那么问题的复杂性就是“ math” > “ Omega”(g (h (n))) 。这个方法被用来证明，如果 p ≠ NP (一个未解的猜想) ，每个 NP 完全问题的复杂性是对于每个正整数都是 < math > Omega (n ^ k) ，</math > 。
获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个人可以将一个大小问题编码为一个问题大小的子问题，并且这个问题的复杂性是 < math > Omega (g (n))。在不失一般性中，我们可以假设函数随着反函数的增加而增加。那么问题的复杂性就是“ math” > “ Omega”(g (h (n))) 。这个方法被用来证明，如果 p ≠ NP (一个未解的猜想) ，每个 NP 完全问题的复杂性是对于每个正整数都是 < math > Omega (n ^ k) ，</math > 。
==Use in algorithm design==
==Use in algorithm design==