c# - 大 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)。