数学运算的计算复杂性

数学运算的计算复杂性
算术函数（Arithmetic functions）
Schnorr and Stumpf conjectured that no fastest algorithm for multiplication exists.
乘法没有最快的算法。

代数函数
特殊功能
基本功能
The elementary functions are constructed by composing arithmetic operations, the exponential function (exp), the natural logarithm (log), trigonometric functions (sin, cos), and their inverses.（初等函数是由指数函数；自然对数；三角函数，以及他们的反函数）The complexity of an elementary function is equivalent to that of its inverse,（初等函数的复杂度与其反函数是一样的）since all elementary functions are analytic and hence invertible（可逆的）by means of Newton's method. In particular, if either exp or log can be computed with some complexity, then that complexity is attainable for all other elementary functions.
Below, the size n refers to the number of digits of precision at which the function is to be evaluated. （n涉及到对函数进行评估的精度）
It is not known whether O(log n M ( n )) is the optimal complexity for elementary functions. The best known lower bound is the trivial bound Ω( M ( n )).
(并不能确定O(log n M ( n )) 是不是初等函数的最佳复杂度，最公认的下界是非渐近紧确的Ω( M ( n )))
非初等函数Non-elementary functions
This table gives the complexity of computing approximations to the given constants to n correct digits.（
这个表格给出了近似计算n的复杂度）
数论
矩阵代数。