performance - 巴比伦方法的时间复杂度

Question

巴比伦方法的时间复杂度是多少？是 log(n)，其中 n 是我们要为其求平方根的数字吗？如果是这样，为什么会这样？

Answer 1

查看the wikipedia section for the Babylonian method我们可以看到在第 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 * 2^k-1 - 1

让 n 成为我们算法的输入，当我们确定总误差小于常数 m 时算法停止

第 k 步的误差 E_k 满足方程 E_k = e_k * n

因此算法将终止一次 e_k * n < m

这将发生在 2^f(k)> n/m 相当于 f(k) > log₂(n/m)

当 2^k-1> (log₂(n/m) - 1)/3 时该等式成立，当 k > log _{时该等式成立2}((log₂(n/m) - 1)/3)+ 1

因此算法将在 O(log(log(n/m)+1)) 步后终止。

使用 this logarithmic summation formula你可以证明 log(log(x)+c)) = O(log(log(x)).

因此巴比伦方法需要 O(log(log(n/m)) 步