algorithm - 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

我会说它是 O(max(n,m)) 因为它的 big-O 应该是 n vs m 对称的，因为算法是。@PaulHankin 将其改进为 O(max(n,m)/gcd(n,m))。