我有兴趣确定以下各项的大O时间复杂度：
def f(x):
r = x / 2
d = 1e-10
while abs(x - r**2) > d:
r = (r + x/r) / 2
return r
我相信这是O（log n）。为此，我仅通过timeit模块收集了经验数据并绘制了结果图，并看到使用以下代码对数图看起来是对数的：
ns = np.linspace(1, 50_000, 100, dtype=int)
ts = [timeit.timeit('f({})'.format(n),
number=100,
globals=globals())
for n in ns]
plt.plot(ns, ts, 'or')
但是这似乎是解决这个问题的老方法。凭直觉，我知道while循环的主体涉及将表达式除以2一定数目k次，直到while表达式等于d。这种重复的2分除会得到类似1/2 ^ k的值，从中我可以看到涉及对数求解k的位置。不过，我似乎无法写下更明确的推导。有什么帮助吗？
我相信您是对的，它是O（log n）。
[r时，您可以在这里看到x = 100000的连续值：
1 50000
2 25001
3 12502
4 6255
5 3136
6 1584
7 823
8 472
9 342
10 317
11 316
12 316
（（由于分数没意思，我将它们四舍五入）。
您可以看到它是否经历了两个阶段。
阶段1是r大时。在这最初的几次迭代中，与x/r相比，r很小。结果，r + x/r接近r，因此(r + x/r) / 2近似为r/2。您可以在前8次迭代中看到这一点。
阶段2是接近最终结果的时间。在最后几次迭代中，x/r接近r，因此r + x/r接近2 * r，因此(r + x/r) / 2接近r。在这一点上，我们只是少量地提高了近似值。这些迭代实际上并不是非常依赖x的大小。
这里是x = 1000000的继承权（是上面的10倍：
1 500000
2 250001
3 125002
4 62505
5 31261
6 15646
7 7855
8 3991
9 2121
10 1296
11 1034
12 1001
13 1000
14 1000
这一次在阶段1中进行了10次迭代，然后在阶段2中又进行了4次迭代。
[算法的复杂度由阶段1决定，该阶段是对数的，因为它每次大约被2除。
这是Heron（或巴比伦的）方法，用于计算数字的平方根。 https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
Big O表示法需要一种数值分析方法。有关分析的更多详细信息，您可以查看列出的Wikipedia页面，或查找Heron的错误收敛或定点迭代。 （或在此处查看https://mathcirclesofchicago.org/wp-content/uploads/2015/08/johnson.pdf）
粗笔，如果我们可以将错误e_n = (x-r_n**2)本身写到e_n = (e_n**2)/(2*(e_n+1))的位置，>
然后我们可以看到e_n+1 <= min{(e_n**2)/2,e_n/2}，因此误差平方减小。准确度使每次迭代有效地加倍。
此分析与Big-O之间的不同之处在于，花费的时间并不取决于输入的大小，而是取决于所需的精度。因此，就输入而言，此while循环为O（1），因为其迭代次数受输入精度的限制，而不是输入的精度。
就准确度而言，误差的上限是e_n < 2**(-n)，因此我们需要找到-n使得2**(-n) < d。所以log_2(d) = b这样2^b = d。假设d <2，则n = floor(log_2(d))将起作用。因此，就d而言，它是O（log（d））。
编辑：有关定点迭代maths.lth.se/na/courses/FMN050/media/material/part3_1.pdf的错误分析的更多信息>