一个函数f(n)=3+1/n^2,它的算法复杂度是0吗?
还是1
人气:152 ℃ 时间:2020-10-02 00:08:24
解答
是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)
推荐
- 写出对x=1,2,3...,10,求函数f(x)=x^2的函数值的算法
- 算法设计与分析 已知某个算法的时间复杂度T(n)=O(f(n)),f(n)是什么函数?T(n)和f(n)是什么关系?
- 计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做:T(n)=O(f(n))
- 求函数f(x)=--x^3-2x+1零点所在的大致区间,注明详细方法
- 如已知函数y=f(n),满足f(0)=1,且f(n)=nf(n-1),n∈N+,求f(1),f(2),f(3)
- 宇宙中没有空气阻力 那飞船是靠什么来完成加速 或者是-减速的
- 赞美老师的词 诗 句各四句
- 硫酸铝25度时的溶解度是多少
猜你喜欢