algorithm - gcd 算法在大 theta 符号方面的时间复杂度。

Question

这里 n>m。我分析了最坏的情况，当 n = fibonacci Nth term 和 m = fiboncci (N-1)th term.In this case total work will be proportinal to N or time complexity will O(N).但我有兴趣找到以 n 表示的时间复杂度(theta 表示法)。但我不知道如何找到 n 和 N 之间的关系，或者以 n 表示的上限和下限。

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;
}

请帮忙。

Answer 1

我会尝试分析两次循环后 m 的变化情况。一次迭代可能对 n 的改变很小，例如 (1001, 1000) -> (1000, 1)。 m 也可能变化很小，例如 (1999, 1000) -> (1000, 999)。因此，分析单次迭代中的任何一种变化对您的帮助都非常小。然而，如果你有两次迭代，那么你总是会有很大的变化。

所以分析一下:如果 r = n/m，在算法两次迭代后 m 如何变化，取决于 r？它至少减少了哪个因素？ (顺便说一句，斐波那契数的 r 是多少？这是否解释了最坏的情况？)