分割の複雑さ

Question

記事Computational complexity of mathematical operationsには、O(M(n))の除算の複雑さと、以下の「M(n)は、選択した乗算アルゴリズムの複雑さを表す」と記載されています。

しかし、M(n)はO(M(n))に埋め込まれています。それは、除算が乗算と同じ複雑さを持っているということですか？

私がKaratsubaの乗算アルゴリズムを使用すると、除算もO(n^1.585)になりますか？

Answer 1

これは、除算が乗算と同じ複雑さを持つことを意味しますか？

正式には、除算は乗算よりも複雑ではありません。しかし実際には、表記法はしばしば同じ複雑さを持っていると言うために使用されます。

私がKaratsubaの乗算アルゴリズムを使用すると、除算もO(n^1.585)になりますか？

声明によると、はい。

ただし、この文が正しいかどうかはわかりません。確かにニュートン・ラフソン法を見てみると、これは反復的なプロセスであることがわかりました。これは、正確には特定の回数繰り返さなければならず、log(n)の順番です（Shereの説明を参照）。 その場合、複雑さはO(log(n)M(n))になります。

ただし、オペランドのサイズに関係なく、固定精度（つまり正しい数字の桁数）しか持たない場合は、一定の反復回数を設定して、O(M(n))複雑。