一个while循环时间复杂度

Question

我有兴趣确定以下内容的大 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。不过，我似乎无法写下更明确的推导。有什么帮助吗？

Answer 1

这是赫伦（或巴比伦）计算数字平方根的方法。https://en.wikipedia.org/wiki/Methods_of_computing_square_roots为此，大 O 表示法需要数值分析方法。有关分析的更多详细信息，您可以查看列出的维基百科页面或查找 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.&nbsp;所以log_2(d) = b这样2^b = d。假设 d < 2，则n = floor(log_2(d))可行。所以就d而言，它是O(log(d))。编辑：关于定点迭代错误分析的更多信息http://www.maths.lth.se/na/courses/FMN050/media/material/part3_1.pdf

Answer 2

我相信你是正确的，它是 O(log n)。r在这里您可以看到when的连续值x = 100000：1 500002 250013 125024 62555 31366 15847 8238 4729 34210 31711 31612 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 5000002 2500013 1250024 625055 312616 156467 78558 39919 212110 129611 103412 100113 100014 1000这次在阶段 1 中有 10 次迭代，然后我们在阶段 2 中再次进行 4 次迭代。算法的复杂性由阶段 1 决定，阶段 1 是对数的，因为它每次大约除以 2。