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