1

ウィキペディアの記事からの次の行の正当化に興味があります。

「このアルゴリズム [拡張ユークリッド アルゴリズム] は、|a| < m と仮定して O(log(m)^2) の時間で実行され、一般に累乗よりも効率的です。」 http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

これはなぜですか？誰かが私にこれを説明できますか? 私はアルゴリズムとすべての数学を完全に理解していますが、そのようなアルゴリズムの複雑さを判断する方法がわかりません。もっと一般的なヒントはありますか？

また、さらに: log は自然対数 (ln) または底 2 を意味しますか?

4

1 に答える 1

-1

人気のあるアルゴリズムの入門書 ( http://mitpress.mit.edu/books/introduction-algorithms ) には、アルゴリズムの複雑さの証明に関する章全体があります (ただし、トピックにはこの本よりもはるかに多くの内容があります)。この問題に一般的に興味がある場合は、それを読むことができます。

この論文の参考文献に従うこともできます: http://itee.uq.edu.au/~havas/cats03.pdf

于 2012-12-19T14:53:06.860 に答える