数值估算复杂度探讨

目录：

• 基础运算

$\newcommand{\abs}[1]{|#1|}$ 我们假定被考虑的数全部是n位小数.

基础运算

四则运算的复杂度, 加减应该是$O(n)$的, 考虑到傅里叶变换(SSA算法)因此乘除应该是$O(n \log n \log\log n)$. (维基百科说可以做到$O(n \log n)$!!! 我不知道怎么做到的?! 以下假定乘法复杂度$M(n)$.) 假定$f(x)$的计算时间复杂度是$A(n) \geq \Omega(n)$, 解附近$\min \abs{f’} > C$, 那么牛顿法解方程$f(x)=0$的时间复杂度为$A(n)$ (因为中间过程无需求解到$n$位). 自然指数考虑前$\log n$项的泰勒展开故应该是$O(M(n) \log n)$, 自然对数考虑为对指数函数解方程, 故也为$O(M(n) \log n)$. 求幂/开根/三角均可看作指对数的复合, 因此复杂度均为$O(M(n) \log n)$.

(未完待续)