割圓法和萊布尼茲級數式求解圓周率近似值的「計算量」誰大？此類計算量如何量化定義？

12-04

晚上和同事聊天對此問題有所爭執，注意不是討論誰收斂速度快，六邊形割圓10次已經6*1024邊型了。是類似於不做優化（就是說根號和三角函數值可能需要級數求解近似值），這樣是否有一個合理的計算量的比較方法？這種情況下（能不能或）怎麼應用大O來表示計算量？感謝。

題主要求的「計算量」相當於時間複雜度。
對於收斂到 $pi$ 的數列 $a_m$ ，類比「精確到小數點後第 $n$ 位」的概念，定義輸入規模為
$n=-log_{10}(frac{left|a_m-pi ight|}{pi})-1$
對於劉徽割圓術
$a_m=3cdot 2^mcdotsqrt{2-underbrace{sqrt{2+sqrt{2+...sqrt{2+1} } }}_{m} }$
對於Leibniz公式
$a_m=4sum_{i=0}^{m}{frac{(-1)^i}{2i+1} }$
兩種演算法的時間複雜度都與 $m$ 成線性關係（計算到 $a_m$ ，劉徽割圓術主要需要 $m$ 次開平方，Leibniz公式需要 $m$ 次除法和加減法）。
畫出 $m$ 與 $n$ 的關係，可以看到劉徽割圓術中 $m$ 與 $n$ 成線性關係；Leibniz公式中 $m$ 與 $n$ 成指數關係（考慮到該法中絕對值大於 $frac{1}{10^n}$ 的項有 $O(10^n)$ 個，容易理解）。
因此估計劉徽割圓術的時間複雜度為 $O(n)$ ，Leibniz公式的時間複雜度為 $O(10^n)$ 。