1
我感兴趣的从维基百科文章下面的行的理由：扩展欧几里得算法运行在时间为O（log（M）^ 2）
“该算法[扩展欧几里得算法]在时间为O（ log（m）^ 2），假设| a | < m，并且通常比幂指数更有效。“ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
为什么会这样呢？任何人都可以向我解释这个吗？我完全理解算法和所有数学，只是我没有看到如何确定这些算法的复杂性。任何更多的一般提示？
此外，额外的：是log意味着是自然对数（LN）或所述一个与底座2？
“的算法称取数时间，如果T（N）= O（log n）的由于计算机使用二进制数字系统。 ，对数常常以2为底（即log2 n，有时写成lg n），然而，通过基数方程对于对数的变化，loga n和logb n只有一个常数乘数的差别，这在大O符号中是丢弃;因此O（log n）是对数时间算法的标准表示法，而不考虑对数的基数“，所以对数基数并不重要，它实际上是一个常数基数。 – CBredlow