performance - バビロニア法の時間計算量

Question

バビロニア法の時間計算量はどれくらいですか? log(n) で、n は平方根を求めたい数値ですか? もしそうなら、なぜそうなのですか？

Answer 1

バビロニア法のウィキペディアのセクションを見ると、ステップ k での相対誤差 e _kが式 e _k < 2 ^-f(k)を満たすことがわかります。ここで、f(k) は次のように再帰的に定義されます。

n > 1 の場合、f(1) = 2 および f(k+1) = 2 * f(k) + 1

帰納法により、f(k) = 3 * 2 ^k-1 - 1

n をアルゴリズムへの入力とします。合計エラーが定数 m 未満であることが確実になると、アルゴリズムは停止します。

ステップ k での誤差 E _{kは、方程式 E k} = e _k * nを満たします。

したがって、アルゴリズムは一度 e _k * n < m で終了します。

_{これは、f(k) > log 2} (n/m)と同等の2 ^{f(k) > n/m の場合に発生します。}

その方程式は、2 ^k-1 > (log ₂ (n/m) - 1)/3 の場合に真であり、k > log ₂ ((log ₂ (n/m) - 1)/3)+ 1の場合に真です。

したがって、アルゴリズムは O(log(log(n/m)+1)) ステップで終了します。

この対数総和式を使用すると、log(log(x)+c)) = O(log(log(x)) を示すことができます。

したがって、バビロニアの方法は O(log(log(n/m)) ステップかかります

Answer 2

ステップは O(log2(log to the base E0 (m/n)) になると思います。ここで、E0 はゼロ回目の反復でのエラーです。つまり、シード値を選択すると、m は ans で許容されるエラーであり、n はアルゴリズムへの入力です。エラーの再帰関数の完全な説明については、これを参照できます: http://www.math.harvard.edu/library/sternberg/slides/lec1.pdf