algorithm - 这段代码可能进入无限循环的时间复杂度是多少？

Question

我正在尝试找出这段代码的时间复杂度。

 while(m!=4){
        if(m>n)
               m=m-n
        else
               n=n-m
    }

我试过 m 和 n 的随机值，这使它成为一个无限循环。不知道怎么找？

Answer 1

这个时间复杂度只有在算法终止时才有意义。必要条件是 gcd(m, n) | 4。但这还不够。

现在很容易看出最坏情况(下降最慢)发生在m = 1 或n = 1 时，因此复杂度为O (最大(m, n))。