370
个编辑
更改
跳到导航
跳到搜索
第222行：
第222行： − − − − A nonlinear lower bound of <math>\Omega(n\log n)</math> is known for the number of comparisons needed for a [[sorting algorithm]]. Thus the best sorting algorithms are optimal, as their complexity is <math>O(n\log n).</math> This lower bound results from the fact that there are {{math|''n''!}} ways of ordering {{mvar|n}} objects. As each comparison splits in two parts this set of {{math|''n''!}} orders, the number of {{mvar|N}} of comparisons that are needed for distinguishing all orders must verify <math>2^N>n!,</math> which implies <math>N =\Omega(n\log n),</math> by [[Stirling's formula]]. − − A nonlinear lower bound of <math>\Omega(n\log n)</math> is known for the number of comparisons needed for a sorting algorithm. Thus the best sorting algorithms are optimal, as their complexity is <math>O(n\log n).</math> This lower bound results from the fact that there are ways of ordering objects. As each comparison splits in two parts this set of orders, the number of of comparisons that are needed for distinguishing all orders must verify <math>2^N>n!,</math> which implies <math>N =\Omega(n\log n),</math> by Stirling's formula. − − <math>\Omega(n\log n)</math>的一个非线性下界是已知的'''<font color="#ff8000">排序算法 sorting algorithm</font>'''所需的比较次数。由于{{mvar|n}}个对象有{{math|''n''!}}种排序方式，当它们的复杂度是<math>O(n\log n).</math>时，最好的排序算法都是最优的。由于每次比较结果都会被分成两部分，即一组{{math|''n''!}}次序，则区分所有比较序列所需的比较次数{{mvar|N}}必须满足<math>2^N>n!,</math> ，这意味着<math>N =\Omega(n\log n),</math>，由 Stirling 公式得出。 −
→问题复杂度(下限)
一些问题的解可能是非常大的，特别是'''<font color="#ff8000">计算机代数 computer algebra</font>'''和'''<font color="#ff8000">计算代数几何 computational algebraic geometry</font>'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，'''<font color="#ff8000">{{mvar|n}}个{{mvar|d}}次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates </font>'''可能有多达 <math>d^n</math>个复解(这是'''<font color="#ff8000">贝佐定理 Bézout's theorem</font>''')。由于这些解必须被写入，所以这个问题的复杂度是<math>\Omega(d^n).</math>。对于这个问题，已知一个复杂度为<math>d^{O(n)}</math>的算法，因此可以认为是渐近拟最优的。
一些问题的解可能是非常大的，特别是'''<font color="#ff8000">计算机代数 computer algebra</font>'''和'''<font color="#ff8000">计算代数几何 computational algebraic geometry</font>'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，'''<font color="#ff8000">{{mvar|n}}个{{mvar|d}}次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates </font>'''可能有多达 <math>d^n</math>个复解(这是'''<font color="#ff8000">贝佐定理 Bézout's theorem</font>''')。由于这些解必须被写入，所以这个问题的复杂度是<math>\Omega(d^n).</math>。对于这个问题，已知一个复杂度为<math>d^{O(n)}</math>的算法，因此可以认为是渐近拟最优的。