kch*_*hoi 10 algorithm performance big-o time-complexity
巴比伦方法的时间复杂度是多少？是log(n)其中n是我们想要找到平方根的数字吗？如果是这样,为什么会这样呢？
lau*_*rie 13
查看维基百科方面的巴比伦方法,我们可以看到步骤k,e k的相对误差满足方程e k <2 -f(k),其中f(k)递归地定义如下:
对于n> 1,f(1)= 2并且f(k + 1)= 2*f(k)+ 1
通过归纳,f(k)= 3*2k- 1-1
设n是我们算法的输入,当我们确定总误差小于常数m时停止
步骤k,E k的误差满足等式E k = e k*n
因此,算法将在e k*n <m时终止
当2 f(k) > n/m(相当于f(k)> log 2(n/m)时会发生这种情况
当k> log 2((log 2(n/m)-1)/ 3)+ 1 时,2 k-1 >(log 2(n/m)-1)/ 3 时该方程为真
因此,算法将以O(log(log(n/m)+1))步骤终止.
使用此对数求和公式,您可以显示log(log(x)+ c))= O(log(log(x)).
因此,巴比伦方法采用O(log(log(n/m))步