更改

计算复杂度 (查看源代码)

2021年1月26日 (二) 20:56的版本

添加33字节、 2021年1月26日 (二) 20:56

第278行：第278行：

A standard method for getting lower bounds of complexity consists of reducing a problem to another problem. More precisely, suppose that one may encode a problem of size into a subproblem of size of a problem , and that the complexity of is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function increases with and has an inverse function . Then the complexity of the problem is <math>\Omega(g(h(n))).</math> This is this method that is used for proving that, if P ≠ NP (an unsolved conjecture), the complexity of every NP-complete problem is <math>\Omega(n^k),</math> for every positive integer .

−

获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n)).</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''反函数 inverse function'''{{mvar|h}}，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n))).</math>。这个方法可以用来证明，若 P ≠ NP (一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''NP完全问题 NP-complete problem''' 的复杂度都是 <math>\Omega(n^k),</math>。

+

获得复杂度下限的标准方法包括将一个问题转化为另一个问题。更准确地说，假设一个大小为{{mvar|n}}的问题{{mvar|A}}可以编码成大小为{{math|''f''(''n'')}}的问题{{mvar|B}}，则问题{{mvar|A}}的复杂度为<math>\Omega(g(n)).</math>。不失一般性地，我们可以假设函数{{mvar|f}}随着{{mvar|n}}的增加而增加，并且有一个'''反函数 inverse function'''{{mvar|h}}，那么问题{{mvar|B}}的复杂度就是<math>\Omega(g(h(n))).</math>。这个方法可以用来证明，若'''P ≠ NP'''(一个未解决的猜想) ，对于每个正整数{{mvar|k}}，每个'''NP完全问题 NP-complete problem''' 的复杂度都是 <math>\Omega(n^k),</math>。

==Use in algorithm design==

小竹凉

307

个编辑