GCDアルゴリズムの実行時間？

Question

unsigned int gcd(unsigned int n, unsigned int m) 
{ 
if (n == 0) 
    return m; 
if (m == 0) 
    return n; 

while (m! = n) 
{ 
if (n > m) 
    n = n − m; 
else 
    m = m − n; 
} 
return n; 
} 

whileループを使用する反復GCDアルゴリズムのためのいくつかの擬似コード。私は2で割り切れる場所がないので、対数ではないと思います。 whileループはNに正比例する時間実行されるので、O（N）のように線形になりますか？

Answer 1

私はbig-Oがn対mの対称でなければならないので、アルゴリズムはO(max(n,m))だと言います。 @PaulHankinはこれをO(max(n,m)/gcd(n,m))に改善しました。