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

質問

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

Ｏ(logN)の

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

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

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

回答No.2

noname#20378 · ベストアンサー

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

で、計算量については以下ご覧ください
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/SoftTech/2005/note/2/Slide23.html

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

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

だそうです

回答No.3

Tacosan

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

回答No.1

BLUEPIXY

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