c-这个平方根计算的时间复杂度是多少

Question

我需要C中的平方根近似，所以我查阅了这篇文章，得到了以下实现：

float squareroot(float n)
{
float x = n;
float y = 1;
float e = 0.001; // Accuracy level
if (n == 0)
return 0;
while ((x - y) > e)
{
x = (x + y) / 2;
if (n == 0 || x == 0)
return 0;
y = n / x;
}
return x; 
}

这件事的时间复杂性是什么？

Answer 1

提示：

观察

(x[k+1] - √n)/(x[k+1] + √n) = (x[k] + n/x[k] - 2√n)/(x[k] + n/x[k] + 2√n) 
= (x[k] - √n)²/(x[k] + √n)².

因此，通过诱导，

(x[k] - √n)/(x[k] + √n) = (x[0] - √n)^(2^k)/(x[0] + √n)^(2^k)
= (√n - 1)^(2^k)/(√n + 1)^(2^k).

从中我们可以找到误差为e:的迭代次数

k = lg(lg(e / (2√n - e)) / lg((√n - 1)/(√n + 1)).

(以2为底对数(