一个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. 所以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 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 决定，阶段 1 是对数的，因为它每次大约除以 2。