我对维基百科文章中以下行的理由感兴趣：
“这个算法 [扩展欧几里得算法] 在 O(log(m)^2) 时间内运行，假设 |a| < m，并且通常比指数更有效。” http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
为什么会这样？谁能给我解释一下？我完全理解算法和所有数学，只是我不知道如何确定这些算法的复杂性。还有更一般的提示吗？
此外，另外：log 是自然对数 (ln) 还是以 2 为底的对数？
问问题
4570 次
1 回答
-1
流行的算法简介书 ( http://mitpress.mit.edu/books/introduction-algorithms ) 有一整章是关于证明算法复杂性的（但是该主题的内容比本书要多得多）。如果您一般对此事感兴趣，可以阅读它。
您也可以尝试遵循本文的参考资料：http: //itee.uq.edu.au/~havas/cats03.pdf
于 2012-12-19T14:53:06.860 回答