更改

添加80字节 、 2021年1月26日 (二) 20:29
第262行: 第262行:  
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>的算法,因此可以认为是渐近拟最优的。
     
307

个编辑