更改

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.

一些问题的解决方案，特别是计算机代数和计算代数几何，可能是非常大的。在这种情况下，复杂度以输出的最大大小为界较低，因为输出必须被写入。例如，如果解的数目是有限的，一个不确定的次数的多项式方程组可能有多达 < math > d ^ n </math > 的复杂解(这是 b é zout 的定理)。由于这些解必须写下来，所以这个问题的复杂性是“ math” > “ Omega (d ^ n)”。对于这个问题，已知一个复杂度 < math > d ^ { o (n)} </math > 的算法，因此可以认为是渐近准最优的。

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