大O符号和算法

Question

我正在研究并试图实现一些算法.我正在尝试理解Big O表示法,我无法弄清楚下面算法的Big O复杂性:

while (a != 0 && b != 0)
{
    if (a > b)
        a %= b;
    else
        b %= a;
}

if (a == 0)
    common=b;
else
    common=a;

Answer 1

很容易看出,经过两次迭代后,最少的数字变得至少小两倍.如果它在开始时等于m,那么在2K迭代之后它将不超过m/2 ^ K. 如果我们在这里放置K = [log_2(m)] + 1,我们将看到在2K迭代之后,最少的数字变为零,并且循环终止.因此,迭代次数不超过2(log_2 m + 1)= O(log m).