我有興趣確定以下內容的大 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。不過，我似乎無法寫下更明確的推導。有什么幫助嗎？
2 回答
阿波羅的戰車
TA貢獻1862條經驗 獲得超6個贊
這是赫倫（或巴比倫）計算數字平方根的方法。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
眼眸繁星
TA貢獻1873條經驗 獲得超9個贊
我相信你是正確的，它是 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。
添加回答
舉報
0/150
提交
取消