Euclidの互除法の時間計算量について

Euclidの互除法の時間計算量についてなんですが、
Euclidの互除法の時間計算量

Ｏ(logN)の

logN の　N　とは何を表しているのですか？

あと、なぜＯ(logN)になるのでしょうか？

至急知りたいんですが教えてください。

No.2 ベストアンサー 回答者： noname#20378 回答日時： 2006/05/01 01:38

入力サイズだそうです(多分aやbの2進数での桁数←勘)

で、計算量については以下ご覧ください
http://www.akita-pu.ac.jp/system/elect/comp1/kus …

んでもって
http://kent.parks.jp/59/otona/bbs.cgi
によると

>ちなみに計算量を示すラージオーの表記では、（底の変換公式により、どんな底に変換したとしても高々定数倍ですので）底は関係なく（記述せず）、通常 O(log n)と書きます。

だそうです

No.3 回答者： Tacosan 回答日時： 2006/05/01 13:43

互除法で処理する 2個の整数の値の大きい方 (ビット数じゃないです).

No.1 回答者： BLUEPIXY 回答日時： 2006/05/01 01:28

よくはわかりませんが、

調べる数値が例えば倍になったとしても、余りを求める計算が１回増えるだけということで、計算に要する手間の増え方は、対数的であるということではないでしょうか