更改

The solution of some problems, typically in computer algebra and computational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a system of  polynomial equations of degree  in  indeterminates may have up to <math>d^n</math> complex solutions, if the number of solutions is finite (this is Bézout's theorem). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.

The solution of some problems, typically in computer algebra and computational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a system of  polynomial equations of degree  in  indeterminates may have up to <math>d^n</math> complex solutions, if the number of solutions is finite (this is Bézout's theorem). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.

一些问题的解答可能是非常大的，特别是'''<font color="#ff8000">计算机代数 computer algebra</font>'''和'''<font color="#ff8000">计算代数几何 computational algebraic geometry</font>'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，{{mvar|n}}个{{mvar|d}}次不确定多项式方程组可能有多达 <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>的算法，因此可以认为是渐近拟最优的。