我目前正在研究并尝试实现一些算法。我试图理解 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;
最佳答案
很容易看出,经过两次迭代后,最小的数字至少变小两倍。如果一开始等于m,那么经过2K次迭代后不会超过m/2^K。如果我们将 K = [log_2(m)] + 1 放在这里,我们将看到在 2K 次迭代之后,最小的数字变为零,循环终止。因此迭代次数不超过 2(log_2 m + 1) = O(log m)。
关于c# - 大 O 符号和算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4535434/