题目

一个函数f(n)=3+1/n^2,它的算法复杂度是0吗?
还是1

提问时间：2021-04-01

答案

是O(1),算法复杂度逼近常数3 -> O(3 + 1/n^2) -> O(3) -> O(1)
看错题目了,原来是要计算这个函数,上面的分析是错的,之前以为是计算复杂度为3+1/n^2
不过不太赞同iicup的想法,算法复杂度考量的是算法时间空间与输入规模之间的比例,n的位数N正比于log(n),那么输入是N而不是1,则普通高精度乘法的算法复杂度应为O(N^2 / N) = O(N).用FFT实现高精度乘法复杂度应为O(Nlog(N)/N)=O(log(N))=O(logN) 空间复杂度均为O(N/N)=O(1)