以下函数的时间复杂度

Question

在下面的 C++ 函数中，令 n >= m。

int gcd(int n, int m) {
            if (n%m ==0) return m;
            if (n < m) swap(n, m);
            while (m > 0) {
                n = n%m;
                swap(n, m);
            }
            return n;
    }

假设 n > m，上述函数的时间复杂度是多少？这个问题的答案是 O(log n)，但我不明白它是如何计算的？

Answer 1

在每次迭代中，n 的值平均减少一个黄金比例因子。我建议尝试找出最坏的情况，它应该是 n

的对数基数 1.618

有关详细信息 https://en.wikipedia.org/wiki/Euclidean_algorithm 其中注释 "If the Euclidean algorithm requires N steps for a pair of natural numbers a > b > 0, the smallest values of a and b for which this is true are the Fibonacci numbers F(N+2) and F(N+1), respectively."

例如如果你从 Fib(n+2) 和 Fib(n+1) 开始，你将在下一次迭代中得到 Fib(n) 和 Fib(n+1)，直到你在 1 处停止。

Answer 2

首先考虑while循环的这两种可能性：

在下面给出的循环中，这个循环的复杂度是O(n) 因为算法的增长与其输入 n:
成比例
```
while (n > 0) {
    n = n-1;
    ...
}
```

而在下面给出的循环中，由于存在嵌套循环，时间将是 O(n^2).

while(n>0) {
    n = n-1;
    while(m>0) {
        m = m-1;
        ...
    }
}

但是，在您提供的算法中，您并没有为每个 m 或 n 遍历循环；相反，你只是使用分而治之的方法，你只探索部分整个 n 在你的循环中。在每次迭代中，n 的值不只是减少 1 的一个因素，而是一个更大的比率：
```
while (m > 0) {
    n = n%m;
    swap(n, m);
}
```

以下函数的时间复杂度

Time complexity of following function

c++

algorithm

big-o

time-complexity